Givet en BST ( B inär S öra T ree) som kan vara obalanserad, konvertera den till en balanserad BST som har minsta möjliga höjd.
Exempel:
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>Rekommenderad övning Normal BST till Balanserad BST Prova det!
A Enkel lösning är att korsa noder i Inorder och en efter en infoga i ett självbalanserande BST-liknande AVL-träd. Tidskomplexiteten för denna lösning är O(n Log n) och den här lösningen garanterar inte minsta möjliga höjd eftersom höjden på AVL-trädet i värsta fall kan vara 1,44*log 2 n .
En Effektiv lösning kan vara att konstruera en balanserad BST i O(n) tid med minsta möjliga höjd. Nedan följer steg.
- Traversera given BST i inordnad ordning och lagra resultat i en array. Detta steg tar O(n) tid. Notera att denna matris skulle sorteras eftersom inordnad genomgång av BST alltid producerar sorterad sekvens.
- Bygg en balanserad BST från den ovan skapade sorterade arrayen med hjälp av det diskuterade rekursiva tillvägagångssättet här . Det här steget tar också O(n)-tid eftersom vi korsar varje element exakt en gång och att bearbeta ett element tar O(1)-tid.
Nedan är implementeringen av ovanstående steg.
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->vänster, noder);> >nodes.push_back(root);> >storeBSTNodes(root->höger, noder);> }> /* Recursive function to construct binary tree */> Node* buildTreeUtil(vector &nodes,>int> start,> >int> end)> {> >// base case> >if> (start>slut)> >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(noder, start, mid-1);> >root->höger = buildTreeUtil(noder, mid+1, end);> >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->data = data;> >node->vänster = nod->höger = NULL;> >return> (node);> }> /* Function to do preorder traversal of tree */> void> preOrder(Node* node)> {> >if> (node == NULL)> >return>;> >printf>(>'%d '>, node->data);> >preOrder(node->vänster);> >preOrder(node->höger);> }> // Driver program> int> main()> {> >/* Constructed skewed binary tree is> >10> >/> >8> >/> >7> >/> >6> >/> >5 */> >Node* root = newNode(10);> >root->vänster = newNode(8);> >root->vänster->vänster = newNode(7);> >root->vänster->vänster->vänster = newNode(6);> >root->vänster->vänster->vänster->vänster = newNode(5);> >root = buildTree(root);> >printf>(>'Preorder traversal of balanced '> >'BST is :
'>);> >preOrder(root);> >return> 0;> }> |
>
typer av for loop
>
Java
java delad sträng med avgränsare
// 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>slut)> >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>slut:> >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> |
skillnaden mellan program och script
>
>
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>slut)> >{> >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
ramverk för java samlingar
> >// 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>slut)> >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);> > > |
>
>Produktion
Preorder traversal of balanced BST is : 7 5 6 8 10>
Tidskomplexitet: O(n), eftersom vi bara korsar trädet två gånger. En gång i ordningsföljd och sedan i konstruktion av det balanserade trädet.
Extra utrymme: O(n), Det extra utrymmet används för att lagra noderna för ordningsgenomgången i vektorn. Det extra utrymmet som tas av stack för rekursionsanrop är O(h) där h är trädets höjd.
Denna artikel har bidragit Aditya Goel . Om du gillartechcodeview.com och vill bidra kan du också skriva en artikel och maila din artikel till [email protected]