Dada la representación de array del árbol binario completo, es decir, si el índice i es el padre, el índice 2*i + 1 es el hijo izquierdo y el índice 2*i + 2 es el hijo derecho. La tarea es encontrar el número mínimo de intercambio necesario para convertirlo en un árbol de búsqueda binario.
Ejemplos:
Input : arr[] = { 5, 6, 7, 8, 9, 10, 11 } Output : 3 Binary tree of the given array:
Swap 1: Swap node 8 with node 5. Swap 2: Swap node 9 with node 10. Swap 3: Swap node 10 with node 7.
So, minimum 3 swaps are required. Input : arr[] = { 1, 2, 3 } Output : 1 Binary tree of the given array:
After swapping node 1 with node 2.
So, only 1 swap required.
Recomendado: Resuelva primero en «PRÁCTICA», antes de pasar a la solución.
La idea es utilizar el hecho de que el recorrido en orden del árbol de búsqueda binaria es en orden creciente de su valor.
Por lo tanto, encuentre el recorrido en orden del árbol binario y guárdelo en la array e intente ordenar la array. El número mínimo de intercambio requerido para ordenar la array será la respuesta. Consulte la publicación a continuación para encontrar la cantidad mínima de intercambios necesarios para ordenar la array.
Número mínimo de intercambios necesarios para ordenar una array
Complejidad temporal: O(n log n).
Implementación:
C++
// C++ program for Minimum swap required // to convert binary tree to binary search tree #include<bits/stdc++.h> using namespace std; // Inorder Traversal of Binary Tree void inorder(int a[], std::vector<int> &v, int n, int index) { // if index is greater or equal to vector size if(index >= n) return; inorder(a, v, n, 2 * index + 1); // push elements in vector v.push_back(a[index]); inorder(a, v, n, 2 * index + 2); } // Function to find minimum swaps to sort an array int minSwaps(std::vector<int> &v) { std::vector<pair<int,int> > t(v.size()); int ans = 0; for(int i = 0; i < v.size(); i++) t[i].first = v[i], t[i].second = i; sort(t.begin(), t.end()); for(int i = 0; i < t.size(); i++) { // second element is equal to i if(i == t[i].second) continue; else { // swapping of elements swap(t[i].first, t[t[i].second].first); swap(t[i].second, t[t[i].second].second); } // Second is not equal to i if(i != t[i].second) --i; ans++; } return ans; } // Driver code int main() { int a[] = { 5, 6, 7, 8, 9, 10, 11 }; int n = sizeof(a) / sizeof(a[0]); std::vector<int> v; inorder(a, v, n, 0); cout << minSwaps(v) << endl; } // This code is contributed by code_freak
Java
// Java program for Minimum swap required // to convert binary tree to binary search tree import java.util.*; public class GFG{ // Pair class static class Pair{ int first, second; Pair(int a, int b){ first = a; second = b; } } // Inorder Traversal of Binary Tree static void inorder(int a[], Vector<Integer> v, int n, int index) { // if index is greater or equal to vector size if(index >= n) return; inorder(a, v, n, 2 * index + 1); // push elements in vector v.add(a[index]); inorder(a, v, n, 2 * index + 2); } // Function returns the // minimum number of swaps // required to sort the array // Refer : // https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/ public static int minSwaps(Vector<Integer> arr) { int n = arr.size(); ArrayList < Pair > arrpos = new ArrayList < Pair > (); for (int i = 0; i < n; i++) arrpos.add(new Pair(arr.get(i), i)); // Sort the array by array element values to // get right position of every element as the // elements of second array. arrpos.sort(new Comparator<Pair>() { @Override public int compare(Pair o1, Pair o2) { return o1.first - o2.first; } }); // To keep track of visited elements. Initialize // all elements as not visited or false. Boolean[] vis = new Boolean[n]; Arrays.fill(vis, false); // Initialize result int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // already swapped and corrected or // already present at correct pos if (vis[i] || arrpos.get(i).first == i) continue; // find out the number of node in // this cycle and add in ans int cycle_size = 0; int j = i; while (!vis[j]) { vis[j] = true; // move to next node j = arrpos.get(j).second; cycle_size++; } // Update answer by adding current cycle. if(cycle_size > 0) { ans += (cycle_size - 1); } } // Return result return ans; } // Driver code public static void main(String args[]) { int a[] = { 5, 6, 7, 8, 9, 10, 11 }; int n = a.length; Vector<Integer> v = new Vector<Integer>(); inorder(a, v, n, 0); System.out.println(minSwaps(v)); } }
Python3
# Python3 program for Minimum swap required # to convert binary tree to binary search tree # Inorder Traversal of Binary Tree def inorder(a, n, index): global v # If index is greater or equal to # vector size if (index >= n): return inorder(a, n, 2 * index + 1) # Push elements in vector v.append(a[index]) inorder(a, n, 2 * index + 2) # Function to find minimum swaps # to sort an array def minSwaps(): global v t = [[0, 0] for i in range(len(v))] ans = -2 for i in range(len(v)): t[i][0], t[i][1] = v[i], i t, i = sorted(t), 0 while i < len(t): # break # second element is equal to i if (i == t[i][1]): i += 1 continue else: # Swapping of elements t[i][0], t[t[i][1]][0] = t[t[i][1]][0], t[i][0] t[i][1], t[t[i][1]][1] = t[t[i][1]][1], t[i][1] # Second is not equal to i if (i == t[i][1]): i -= 1 i += 1 ans += 1 return ans # Driver Code if __name__ == '__main__': v = [] a = [ 5, 6, 7, 8, 9, 10, 11 ] n = len(a) inorder(a, n, 0) print(minSwaps()) # This code is contributed by mohit kumar 29
C#
// C# program for Minimum swap required // to convert binary tree to binary search tree using System; using System.Collections.Generic; using System.Linq; class GFG { // Pair class public class Pair { public int first, second; public Pair(int a, int b) { first = a; second = b; } } // Inorder Traversal of Binary Tree public static void inorder(int[] a, List<int> v, int n, int index) { // if index is greater or equal to vector size if (index >= n) return; inorder(a, v, n, 2 * index + 1); // push elements in vector v.Add(a[index]); inorder(a, v, n, 2 * index + 2); } // Function returns the // minimum number of swaps // required to sort the array // Refer : // https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/ public static int minSwaps(List<int> arr) { int n = arr.Count(); List<Pair> arrpos = new List<Pair>(); for (int i = 0; i < n; i++) arrpos.Add(new Pair(arr[i], i)); // Sort the array by array element values to // get right position of every element as the // elements of second array. arrpos.Sort((x, y) => x.first - y.first); // To keep track of visited elements. Initialize // all elements as not visited or false. bool[] vis = new bool[n]; for (int i = 0; i < n; i++) vis[i] = false; // Initialize result int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // already swapped and corrected or // already present at correct pos if (vis[i] || arrpos[i].first == i) continue; // find out the number of node in // this cycle and add in ans int cycle_size = 0; int j = i; while (!vis[j]) { vis[j] = true; // move to next node j = arrpos[j].second; cycle_size++; } // Update answer by adding current cycle. if (cycle_size > 0) ans += (cycle_size - 1); } // Return result return ans; } // Driver code public static void Main(string[] args) { int[] a = { 5, 6, 7, 8, 9, 10, 11 }; int n = a.Length; List<int> v = new List<int>(); inorder(a, v, n, 0); Console.WriteLine(minSwaps(v)); } } // This Code is contributed by Tapesh(tapeshdua420)
Javascript
<script> // Javascript program for Minimum swap required // to convert binary tree to binary search tree // Inorder Traversal of Binary Tree function inorder(a, n, index) { // If index is greater or equal to // vector size if (index >= n) return inorder(a, n, 2 * index + 1) // Push elements in vector v.push(a[index]) inorder(a, n, 2 * index + 2) } // Function to find minimum swaps to sort an array function minSwaps() { let t=new Array(v.length); let ans = -2 for(let i=0;i<v.length;i++) { t[i]=new Array(2); for(let j=0;j<2;j++) { t[i][j]=0; } } for(let i=0;i<v.length;i++) { t[i][0]=v[i]; t[i][1]=i; } t.sort(function(a,b){return a[0] - b[0];}); let i=0; while(i<t.length) { // break // second element is equal to i if (i == t[i][1]) { i += 1; continue; } else{ // Swapping of elements t[i][0], t[t[i][1]][0] = t[t[i][1]][0], t[i][0]; t[i][1], t[t[i][1]][1] = t[t[i][1]][1], t[i][1]; } // Second is not equal to i if (i == t[i][1]) i -= 1; i += 1; ans += 1; } return ans; } // Driver code let v=[]; let a=[ 5, 6, 7, 8, 9, 10, 11]; let n=a.length; inorder(a, n, 0); document.write(minSwaps()); // This code is contributed by patel2127 </script>
3
Ejercicio: ¿Podemos extender esto a un árbol binario normal, es decir, un árbol binario representado usando punteros izquierdo y derecho, y no necesariamente completo?
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA