Biorąc pod uwagę BST ( B inary S ucho T ree), który może być niezrównoważony, przekształć go w zrównoważony BST o minimalnej możliwej wysokości.
Przykłady:
Input: 30 / 20 / 10 Output: 20 / 10 30 Input: 4 / 3 / 2 / 1 Output: 3 3 2 / / / 1 4 OR 2 4 OR 1 3 OR .. / 2 1 4 Input: 4 / 3 5 / 2 6 / 1 7 Output: 4 / 2 6 / / 1 3 5 7>Zalecana praktyka Od normalnego BST do zrównoważonego BST Wypróbuj!
A Proste rozwiązanie polega na przemierzaniu węzłów w Inorder i wstawianiu jeden po drugim do samobalansującego BST, takiego jak drzewo AVL. Złożoność czasowa tego rozwiązania wynosi O(n Log n) i to rozwiązanie nie gwarantuje minimalnej możliwej wysokości, ponieważ w najgorszym przypadku wysokość drzewa AVL może wynosić 1,44*log 2 N .
Jakiś Wydajne rozwiązanie może polegać na skonstruowaniu zrównoważonego BST w czasie O(n) przy minimalnej możliwej wysokości. Poniżej znajdują się kroki.
- Przemierzaj podany BST w kolejności i zapisz wynik w tablicy. Ten krok zajmuje czas O(n). Należy zauważyć, że ta tablica zostanie posortowana, ponieważ przechodzenie BST w kolejności zawsze daje posortowaną sekwencję.
- Zbuduj zrównoważony BST z utworzonej powyżej posortowanej tablicy, stosując omówione podejście rekurencyjne Tutaj . Ten krok również zajmuje czas O(n), ponieważ przechodzimy przez każdy element dokładnie raz, a przetwarzanie elementu zajmuje czas O(1).
Poniżej znajduje się realizacja powyższych kroków.
C++
// C++ program to convert a left unbalanced BST to> // a balanced BST> #include> using> namespace> std;> struct> Node> {> >int> data;> >Node* left, *right;> };> /* This function traverse the skewed binary tree and> >stores its nodes pointers in vector nodes[] */> void> storeBSTNodes(Node* root, vector &nodes)> {> >// Base case> >if> (root==NULL)> >return>;> >// Store nodes in Inorder (which is sorted> >// order for BST)> >storeBSTNodes(root->po lewej, węzły);> >nodes.push_back(root);> >storeBSTNodes(root->tak, węzły);> }> /* Recursive function to construct binary tree */> Node* buildTreeUtil(vector &nodes,>int> start,> >int> end)> {> >// base case> >if> (start>koniec)> >return> NULL;> >/* Get the middle element and make it root */> >int> mid = (start + end)/2;> >Node *root = nodes[mid];> >/* Using index in Inorder traversal, construct> >left and right subtress */> >root->left = buildTreeUtil(węzły, początek, środek 1);> >root->prawo = buildTreeUtil(węzły, środek+1, koniec);> >return> root;> }> // This functions converts an unbalanced BST to> // a balanced BST> Node* buildTree(Node* root)> {> >// Store nodes of given BST in sorted order> >vector nodes;> >storeBSTNodes(root, nodes);> >// Constructs BST from nodes[]> >int> n = nodes.size();> >return> buildTreeUtil(nodes, 0, n-1);> }> // Utility function to create a new node> Node* newNode(>int> data)> {> >Node* node =>new> Node;> >node->dane = dane;> >node->lewy = węzeł->prawy = NULL;> >return> (node);> }> /* Function to do preorder traversal of tree */> void> preOrder(Node* node)> {> >if> (node == NULL)> >return>;> >printf>(>'%d '>, node->dane);> >preOrder(node->lewo);> >preOrder(node->prawda);> }> // Driver program> int> main()> {> >/* Constructed skewed binary tree is> >10> >/> >8> >/> >7> >/> >6> >/> >5 */> >Node* root = newNode(10);> >root->lewy = nowyWęzeł(8);> >root->lewy->lewy = nowyWęzeł(7);> >root->lewy->lewy->lewy = newNode(6);> >root->lewy->lewy->lewy->lewy = newNode(5);> >root = buildTree(root);> >printf>(>'Preorder traversal of balanced '> >'BST is :
'>);> >preOrder(root);> >return> 0;> }> |
>
silnia w Javie
>
Jawa
metody listy Java
// Java program to convert a left unbalanced BST to a balanced BST> import> java.util.*;> /* A binary tree node has data, pointer to left child> >and a pointer to right child */> class> Node> {> >int> data;> >Node left, right;> >public> Node(>int> data)> >{> >this>.data = data;> >left = right =>null>;> >}> }> class> BinaryTree> {> >Node root;> >/* This function traverse the skewed binary tree and> >stores its nodes pointers in vector nodes[] */> >void> storeBSTNodes(Node root, Vector nodes)> >{> >// Base case> >if> (root ==>null>)> >return>;> >// Store nodes in Inorder (which is sorted> >// order for BST)> >storeBSTNodes(root.left, nodes);> >nodes.add(root);> >storeBSTNodes(root.right, nodes);> >}> >/* Recursive function to construct binary tree */> >Node buildTreeUtil(Vector nodes,>int> start,> >int> end)> >{> >// base case> >if> (start>koniec)> >return> null>;> >/* Get the middle element and make it root */> >int> mid = (start + end) />2>;> >Node node = nodes.get(mid);> >/* Using index in Inorder traversal, construct> >left and right subtress */> >node.left = buildTreeUtil(nodes, start, mid ->1>);> >node.right = buildTreeUtil(nodes, mid +>1>, end);> >return> node;> >}> >// This functions converts an unbalanced BST to> >// a balanced BST> >Node buildTree(Node root)> >{> >// Store nodes of given BST in sorted order> >Vector nodes =>new> Vector();> >storeBSTNodes(root, nodes);> >// Constructs BST from nodes[]> >int> n = nodes.size();> >return> buildTreeUtil(nodes,>0>, n ->1>);> >}> >/* Function to do preorder traversal of tree */> >void> preOrder(Node node)> >{> >if> (node ==>null>)> >return>;> >System.out.print(node.data +>' '>);> >preOrder(node.left);> >preOrder(node.right);> >}> >// Driver program to test the above functions> >public> static> void> main(String[] args)> >{> >/* Constructed skewed binary tree is> >10> >/> >8> >/> >7> >/> >6> >/> >5 */> >BinaryTree tree =>new> BinaryTree();> >tree.root =>new> Node(>10>);> >tree.root.left =>new> Node(>8>);> >tree.root.left.left =>new> Node(>7>);> >tree.root.left.left.left =>new> Node(>6>);> >tree.root.left.left.left.left =>new> Node(>5>);> >tree.root = tree.buildTree(tree.root);> >System.out.println(>'Preorder traversal of balanced BST is :'>);> >tree.preOrder(tree.root);> >}> }> // This code has been contributed by Mayank Jaiswal(mayank_24)> |
>
>
Python3
# Python3 program to convert a left> # unbalanced BST to a balanced BST> import> sys> import> math> # A binary tree node has data, pointer to left child> # and a pointer to right child> class> Node:> >def> __init__(>self>,data):> >self>.data>=>data> >self>.left>=>None> >self>.right>=>None> # This function traverse the skewed binary tree and> # stores its nodes pointers in vector nodes[]> def> storeBSTNodes(root,nodes):> > ># Base case> >if> not> root:> >return> > ># Store nodes in Inorder (which is sorted> ># order for BST)> >storeBSTNodes(root.left,nodes)> >nodes.append(root)> >storeBSTNodes(root.right,nodes)> # Recursive function to construct binary tree> def> buildTreeUtil(nodes,start,end):> > ># base case> >if> start>koniec:> >return> None> ># Get the middle element and make it root> >mid>=>(start>+>end)>/>/>2> >node>=>nodes[mid]> ># Using index in Inorder traversal, construct> ># left and right subtress> >node.left>=>buildTreeUtil(nodes,start,mid>->1>)> >node.right>=>buildTreeUtil(nodes,mid>+>1>,end)> >return> node> # This functions converts an unbalanced BST to> # a balanced BST> def> buildTree(root):> > ># Store nodes of given BST in sorted order> >nodes>=>[]> >storeBSTNodes(root,nodes)> ># Constructs BST from nodes[]> >n>=>len>(nodes)> >return> buildTreeUtil(nodes,>0>,n>->1>)> # Function to do preorder traversal of tree> def> preOrder(root):> >if> not> root:> >return> >print>(>'{} '>.>format>(root.data),end>=>'')> >preOrder(root.left)> >preOrder(root.right)> # Driver code> if> __name__>=>=>'__main__'>:> ># Constructed skewed binary tree is> ># 10> ># /> ># 8> ># /> ># 7> ># /> ># 6> ># /> ># 5> >root>=> Node(>10>)> >root.left>=> Node(>8>)> >root.left.left>=> Node(>7>)> >root.left.left.left>=> Node(>6>)> >root.left.left.left.left>=> Node(>5>)> >root>=> buildTree(root)> >print>(>'Preorder traversal of balanced BST is :'>)> >preOrder(root)> > # This code has been contributed by Vikash Kumar 37> |
szakal kontra wilk
>
>
C#
using> System;> using> System.Collections.Generic;> // C# program to convert a left unbalanced BST to a balanced BST> /* A binary tree node has data, pointer to left child> >and a pointer to right child */> public> class> Node> {> >public> int> data;> >public> Node left, right;> >public> Node(>int> data)> >{> >this>.data = data;> >left = right =>null>;> >}> }> public> class> BinaryTree> {> >public> Node root;> >/* This function traverse the skewed binary tree and> >stores its nodes pointers in vector nodes[] */> >public> virtual> void> storeBSTNodes(Node root, List nodes)> >{> >// Base case> >if> (root ==>null>)> >{> >return>;> >}> >// Store nodes in Inorder (which is sorted> >// order for BST)> >storeBSTNodes(root.left, nodes);> >nodes.Add(root);> >storeBSTNodes(root.right, nodes);> >}> >/* Recursive function to construct binary tree */> >public> virtual> Node buildTreeUtil(List nodes,>int> start,>int> end)> >{> >// base case> >if> (start>koniec)> >{> >return> null>;> >}> >/* Get the middle element and make it root */> >int> mid = (start + end) / 2;> >Node node = nodes[mid];> >/* Using index in Inorder traversal, construct> >left and right subtress */> >node.left = buildTreeUtil(nodes, start, mid - 1);> >node.right = buildTreeUtil(nodes, mid + 1, end);> >return> node;> >}> >// This functions converts an unbalanced BST to> >// a balanced BST> >public> virtual> Node buildTree(Node root)> >{> >// Store nodes of given BST in sorted order> >List nodes =>new> List();> >storeBSTNodes(root, nodes);> >// Constructs BST from nodes[]> >int> n = nodes.Count;> >return> buildTreeUtil(nodes, 0, n - 1);> >}> >/* Function to do preorder traversal of tree */> >public> virtual> void> preOrder(Node node)> >{> >if> (node ==>null>)> >{> >return>;> >}> >Console.Write(node.data +>' '>);> >preOrder(node.left);> >preOrder(node.right);> >}> >// Driver program to test the above functions> >public> static> void> Main(>string>[] args)> >{> >/* Constructed skewed binary tree is> >10> >/> >8> >/> >7> >/> >6> >/> >5 */> >BinaryTree tree =>new> BinaryTree();> >tree.root =>new> Node(10);> >tree.root.left =>new> Node(8);> >tree.root.left.left =>new> Node(7);> >tree.root.left.left.left =>new> Node(6);> >tree.root.left.left.left.left =>new> Node(5);> >tree.root = tree.buildTree(tree.root);> >Console.WriteLine(>'Preorder traversal of balanced BST is :'>);> >tree.preOrder(tree.root);> >}> }> >// This code is contributed by Shrikant13> |
>
>
JavaScript
ciąg znaków Java Indexof
> >// JavaScript program to convert a left> >// unbalanced BST to a balanced BST> > >class Node> >{> >constructor(data) {> >this>.left =>null>;> >this>.right =>null>;> >this>.data = data;> >}> >}> > >let root;> > >/* This function traverse the skewed binary tree and> >stores its nodes pointers in vector nodes[] */> >function> storeBSTNodes(root, nodes)> >{> >// Base case> >if> (root ==>null>)> >return>;> > >// Store nodes in Inorder (which is sorted> >// order for BST)> >storeBSTNodes(root.left, nodes);> >nodes.push(root);> >storeBSTNodes(root.right, nodes);> >}> > >/* Recursive function to construct binary tree */> >function> buildTreeUtil(nodes, start, end)> >{> >// base case> >if> (start>koniec)> >return> null>;> > >/* Get the middle element and make it root */> >let mid = parseInt((start + end) / 2, 10);> >let node = nodes[mid];> > >/* Using index in Inorder traversal, construct> >left and right subtress */> >node.left = buildTreeUtil(nodes, start, mid - 1);> >node.right = buildTreeUtil(nodes, mid + 1, end);> > >return> node;> >}> > >// This functions converts an unbalanced BST to> >// a balanced BST> >function> buildTree(root)> >{> >// Store nodes of given BST in sorted order> >let nodes = [];> >storeBSTNodes(root, nodes);> > >// Constructs BST from nodes[]> >let n = nodes.length;> >return> buildTreeUtil(nodes, 0, n - 1);> >}> > >/* Function to do preorder traversal of tree */> >function> preOrder(node)> >{> >if> (node ==>null>)> >return>;> >document.write(node.data +>' '>);> >preOrder(node.left);> >preOrder(node.right);> >}> > >/* Constructed skewed binary tree is> >10> >/> >8> >/> >7> >/> >6> >/> >5 */> >root =>new> Node(10);> >root.left =>new> Node(8);> >root.left.left =>new> Node(7);> >root.left.left.left =>new> Node(6);> >root.left.left.left.left =>new> Node(5);> >root = buildTree(root);> >document.write(>'Preorder traversal of balanced BST is :'> +>''>);> >preOrder(root);> > > |
>
>Wyjście
Preorder traversal of balanced BST is : 7 5 6 8 10>
Złożoność czasowa: O(n), Ponieważ właśnie przechodzimy przez drzewo dwa razy. Raz w przejściu wewnętrznym, a następnie w konstrukcji zrównoważonego drzewa.
Przestrzeń pomocnicza: O(n), Dodatkowa przestrzeń jest używana do przechowywania węzłów przejścia w wektorze. Również dodatkowa przestrzeń zajmowana przez stos wywołań rekurencji to O(h), gdzie h jest wysokością drzewa.
Ten artykuł został napisany Aditya Goel . Jeśli podoba Ci się techcodeview.com i chciałbyś wnieść swój wkład, możesz również napisać artykuł i wysłać go na adres [email protected]