Dado un árbol de búsqueda binario (BST) desequilibrado, la tarea es convertirlo en un BST equilibrado en tiempo lineal y sin usar espacio auxiliar.
Ejemplos:
Entrada: 5
/ \
1 10
\
20
\
35
Salida: 20
/ \
5 35
/ \
1 10Entrada: 10
/
5
/
2
/
1
Salida: 5
/ \
2 10
/
1
Enfoque: El algoritmo utilizado en este escenario es el algoritmo Day-Stout-Warren . El árbol balanceado formado será un árbol binario completo . Siga los pasos a continuación para la implementación del algoritmo.
- Paso 1 : Convierta el BST dado en una lista enlazada (lista enlazada del lado derecho) usando el concepto de rotaciones a la derecha por medio del recorrido en orden. Esta forma de BST se conoce como columna vertebral o vid . el tiempo de ejecución de esta fase es lineal y no se requiere espacio adicional.
La función está codificada de tal manera que realiza toda la rotación correcta requerida para aplanar el BST y al final devuelve el número de Nodes en BST. - Paso 2 : Calcule la altura de BST en la que todos los niveles se llenarán por completo utilizando la fórmula h = log2(N+1) [N es el número total de Nodes]. Y usando la altura calcule el número de Nodes que se pueden colocar en esa altura m = pow(2, h)-1 . [h es la altura hasta la cual todos los niveles están completamente llenos de Nodes]
La diferencia (diff) de N y m es la cantidad de Nodes que habrá en el último nivel del árbol binario completo balanceado. - La vid obtenida en el primer paso se deja luego rotar una cantidad diferente de tiempo desde su raíz. El árbol modificado anterior se gira a la izquierda m/2, m/4, m/8. . . veces hasta que m sea mayor que 0 según el algoritmo
Ilustraciones:
Ilustración-1: Aquí el árbol dado es un BST sesgado a la izquierda
Ilustración-2: Aquí es un BST no sesgado pero desequilibrado
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to balance BST using DSW algorithm. #include <bits/stdc++.h> using namespace std; // Defining the structure for TreeNode. struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode() : val(0) , left(NULL) , right(NULL) { } TreeNode(int x) : val(x) , left(NULL) , right(NULL) { } TreeNode(int x, TreeNode* left, TreeNode* right) : val(x) , left(left) , right(right) { } }; // Function to convert input BST // to right linked list // known as vine or backbone. int bstToVine(TreeNode* grand) { int count = 0; // Make tmp pointer to traverse // and right flatten the given BST. TreeNode* tmp = grand->right; // Traverse until tmp becomes NULL while (tmp) { // If left exist for node // pointed by tmp then // right rotate it. if (tmp->left) { TreeNode* oldTmp = tmp; tmp = tmp->left; oldTmp->left = tmp->right; tmp->right = oldTmp; grand->right = tmp; } // If left dont exists // add 1 to count and // traverse further right to // flatten remaining BST. else { count++; grand = tmp; tmp = tmp->right; } } return count; } // Function to compress given tree // with its root as grand->right. void compress(TreeNode* grand, int m) { // Make tmp pointer to traverse // and compress the given BST. TreeNode* tmp = grand->right; // Traverse and left-rotate root m times // to compress given vine form of BST. for (int i = 0; i < m; i++) { TreeNode* oldTmp = tmp; tmp = tmp->right; grand->right = tmp; oldTmp->right = tmp->left; tmp->left = oldTmp; grand = tmp; tmp = tmp->right; } } // Function to implement the algorithm TreeNode* balanceBST(TreeNode* root) { // create dummy node with value 0 TreeNode* grand = new TreeNode(0); // assign the right of dummy node as our input BST grand->right = root; // get the number of nodes in input BST and // simultaneously convert it into right linked list. int count = bstToVine(grand); // gets the height of tree in which all levels // are completely filled. int h = log2(count + 1); // get number of nodes until second last level int m = pow(2, h) - 1; // Left rotate for excess nodes at last level compress(grand, count - m); // Left rotation till m becomes 0 // Step is done as mentioned in algo to // make BST balanced. for (m = m / 2; m > 0; m /= 2) { compress(grand, m); } // return the balanced tree return grand->right; } // Function to print preorder traversal // of Binary tree. void preorderTraversal(TreeNode* root) { if (!root) return; cout << root->val << " "; preorderTraversal(root->left); preorderTraversal(root->right); return; } // Driver code int main() { TreeNode* root = new TreeNode(10); root->left = new TreeNode(5); root->left->left = new TreeNode(2); root->left->left->left = new TreeNode(1); // Function call to implement // Day-Stout-Warren algorithm root = balanceBST(root); // To print the preorder traversal of BST preorderTraversal(root); return 0; }
Java
// Java code to balance BST using DSW algorithm. public class DayStout { // Defining the structure for TreeNode. static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; } } // Function to convert input BST // to right linked list // known as vine or backbone. static int bstToVine(TreeNode grand) { int count = 0; // Make tmp pointer to traverse // and right flatten the given BST. TreeNode tmp = grand.right; // Traverse until tmp becomes NULL while (tmp != null) { // If left exist for node // pointed by tmp then // right rotate it. if (tmp.left != null) { TreeNode oldTmp = tmp; tmp = tmp.left; oldTmp.left = tmp.right; tmp.right = oldTmp; grand.right = tmp; } // If left dont exists // add 1 to count and // traverse further right to // flatten remaining BST. else { count++; grand = tmp; tmp = tmp.right; } } return count; } // Function to compress given tree // with its root as grand.right. static void compress(TreeNode grand, int m) { // Make tmp pointer to traverse // and compress the given BST. TreeNode tmp = grand.right; // Traverse and left-rotate root m times // to compress given vine form of BST. for (int i = 0; i < m; i++) { TreeNode oldTmp = tmp; tmp = tmp.right; grand.right = tmp; oldTmp.right = tmp.left; tmp.left = oldTmp; grand = tmp; tmp = tmp.right; } } // Function to calculate the // log base 2 of an integer static public int log2(int N) { // calculate log2 N indirectly // using log() method int result = (int)(Math.log(N) / Math.log(2)); return result; } // Function to implement the algorithm static TreeNode balanceBST(TreeNode root) { // create dummy node with value 0 TreeNode grand = new TreeNode(0); // assign the right of dummy node as our input BST grand.right = root; // get the number of nodes in input BST and // simultaneously convert it into right linked list. int count = bstToVine(grand); // gets the height of tree in which all levels // are completely filled. int h = log2(count + 1); // get number of nodes until second last level int m = (int)Math.pow(2, h) - 1; // Left rotate for excess nodes at last level compress(grand, count - m); // Left rotation till m becomes 0 // Step is done as mentioned in algo to // make BST balanced. for (m = m / 2; m > 0; m /= 2) { compress(grand, m); } // return the balanced tree return grand.right; } // Function to print preorder traversal // of Binary tree. static void preorderTraversal(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); return; } // Driver code public static void main(String[] args) { TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.left.left = new TreeNode(2); root.left.left.left = new TreeNode(1); // Function call to implement // Day-Stout-Warren algorithm root = balanceBST(root); // To print the preorder traversal of BST preorderTraversal(root); } } // This code is contributed by Lovely Jain
C#
// C# code to balance BST using DSW algorithm using System; public class GFG { // Defining the structure for TreeNode. class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; left = right = null; } } // Function to convert input BST // to right linked list // known as vine or backbone. static int bstToVine(TreeNode grand) { int count = 0; // Make tmp pointer to traverse // and right flatten the given BST. TreeNode tmp = grand.right; // Traverse until tmp becomes NULL while (tmp != null) { // If left exist for node // pointed by tmp then // right rotate it. if (tmp.left != null) { TreeNode oldTmp = tmp; tmp = tmp.left; oldTmp.left = tmp.right; tmp.right = oldTmp; grand.right = tmp; } // If left dont exists // add 1 to count and // traverse further right to // flatten remaining BST. else { count++; grand = tmp; tmp = tmp.right; } } return count; } // Function to compress given tree // with its root as grand.right. static void compress(TreeNode grand, int m) { // Make tmp pointer to traverse // and compress the given BST. TreeNode tmp = grand.right; // Traverse and left-rotate root m times // to compress given vine form of BST. for (int i = 0; i < m; i++) { TreeNode oldTmp = tmp; tmp = tmp.right; grand.right = tmp; oldTmp.right = tmp.left; tmp.left = oldTmp; grand = tmp; tmp = tmp.right; } } // Function to calculate the // log base 2 of an integer static public int log2(int N) { // calculate log2 N indirectly // using log() method int result = (int)(Math.Log(N) / Math.Log(2)); return result; } // Function to implement the algorithm static TreeNode balanceBST(TreeNode root) { // create dummy node with value 0 TreeNode grand = new TreeNode(0); // assign the right of dummy node as our input BST grand.right = root; // get the number of nodes in input BST and // simultaneously convert it into right linked list. int count = bstToVine(grand); // gets the height of tree in which all levels // are completely filled. int h = log2(count + 1); // get number of nodes until second last level int m = (int)Math.Pow(2, h) - 1; // Left rotate for excess nodes at last level compress(grand, count - m); // Left rotation till m becomes 0 // Step is done as mentioned in algo to // make BST balanced. for (m = m / 2; m > 0; m /= 2) { compress(grand, m); } // return the balanced tree return grand.right; } // Function to print preorder traversal // of Binary tree. static void preorderTraversal(TreeNode root) { if (root == null) return; Console.Write(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); return; } static public void Main() { // Code TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.left.left = new TreeNode(2); root.left.left.left = new TreeNode(1); // Function call to implement // Day-Stout-Warren algorithm root = balanceBST(root); // To print the preorder traversal of BST preorderTraversal(root); } } // This code is contributed by lokesh(lokeshmvs21).
Javascript
<script> // Javascript code to balance BST using DSW algorithm. // Defining the structure for TreeNode. class TreeNode { constructor(x = 0, left = null, right = null){ this.val = x this.left = left this.right = right } } // Function to convert input BST // to right linked list // known as vine or backbone. function bstToVine(grand) { let count = 0; // Make tmp pointer to traverse // and right flatten the given BST. let tmp = grand.right; // Traverse until tmp becomes NULL while (tmp) { // If left exist for node // pointed by tmp then // right rotate it. if (tmp.left) { let oldTmp = tmp; tmp = tmp.left; oldTmp.left = tmp.right; tmp.right = oldTmp; grand.right = tmp; } // If left dont exists // add 1 to count and // traverse further right to // flatten remaining BST. else { count++; grand = tmp; tmp = tmp.right; } } return count; } // Function to compress given tree // with its root as grand.right. function compress(grand, m) { // Make tmp pointer to traverse // and compress the given BST. let tmp = grand.right; // Traverse and left-rotate root m times // to compress given vine form of BST. for (let i = 0; i < m; i++) { let oldTmp = tmp; tmp = tmp.right; grand.right = tmp; oldTmp.right = tmp.left; tmp.left = oldTmp; grand = tmp; tmp = tmp.right; } } // Function to implement the algorithm function balanceBST(root) { // create dummy node with value 0 let grand = new TreeNode(0); // assign the right of dummy node as our input BST grand.right = root; // get the number of nodes in input BST and // simultaneously convert it into right linked list. let count = bstToVine(grand); // gets the height of tree in which all levels // are completely filled. let h = Math.log2(count + 1); // get number of nodes until second last level let m = Math.pow(2, h) - 1; // Left rotate for excess nodes at last level compress(grand, count - m); // Left rotation till m becomes 0 // Step is done as mentioned in algo to // make BST balanced. for (m = Math.floor(m / 2); m > 0; m = Math.floor(m / 2)) { compress(grand, m); } // return the balanced tree return grand.right; } // Function to print preorder traversal // of Binary tree. function preorderTraversal(root) { if (!root) return; document.write(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); return; } // Driver code let root = new TreeNode(10); root.left = new TreeNode(5); root.left.left = new TreeNode(2); root.left.left.left = new TreeNode(1); // Function call to implement // Day-Stout-Warren algorithm root = balanceBST(root); // To print the preorder traversal of BST preorderTraversal(root); // This code is contributed by saurabh_jaiswal. </script>
5 2 1 10
Complejidad de tiempo: O(N) donde N es el número total de Nodes en el
espacio auxiliar BST: O(1)
Publicación traducida automáticamente
Artículo escrito por jayshilbuddhadev y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA