Алгоритм Дей-Стаута-Уоррена для балансировки данного двоичного дерева поиска
Опубликовано: 20 Сентября, 2022
Учитывая несбалансированное бинарное дерево поиска (BST), задача состоит в том, чтобы преобразовать его в сбалансированное BST за линейное время и без использования вспомогательного пространства.
Примеры:
Input: 5
/
1 10
20
35
Output: 20
/
5 35
/
1 10Input: 10
/
5
/
2
/
1
Output: 5
/
2 10
/
1
Подход. В этом сценарии используется алгоритм Дей-Стаут-Уоррен . Сформированное сбалансированное дерево будет полным бинарным деревом. Следуйте приведенным ниже шагам для реализации алгоритма.
- Шаг 1 : Преобразуйте данный BST в связанный список (правосторонний связанный список), используя концепцию правого вращения посредством неупорядоченного обхода. Эта форма BST известна как основа или лоза . Время выполнения этого этапа является линейным и не требует дополнительного места.
Функция закодирована таким образом, что она выполняет все необходимые повороты вправо, чтобы сгладить BST, и в конце возвращает количество узлов в BST. - Шаг 2 : Рассчитайте высоту BST , при которой все уровни будут полностью заполнены , используя формулу h = log2(N+1) [N — общее количество узлов]. И, используя высоту, вычислите количество узлов, которые можно разместить на этой высоте m = pow(2, h)-1 . [h — высота, до которой все уровни полностью заполнены узлами]
Разница (diff) N и m — это количество узлов, которые будут на последнем уровне сбалансированного полного бинарного дерева. - Виноградную лозу, полученную на первом этапе, затем оставляют вращать на разное время от ее корня. Вышеупомянутое модифицированное дерево затем поворачивается влево m/2, m/4, m/8 . . . раз, пока m не станет больше 0 в соответствии с алгоритмом
Иллюстрации:
Illustration-1: Here the given tree is a left skewed BST
Example-1
Illustration-2: Here it is a non-skewed but unbalanced BST
Example-2
Ниже приведена реализация описанного выше подхода.
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 algorithmTreeNode* 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 codeint 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 algorithmusing 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;
|