Ņemot vērā BST ( B inārs S earch T ree), kas var būt nelīdzsvarota, pārveidojiet to par līdzsvarotu BST ar minimālo iespējamo augstumu.
Piemēri:
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>Ieteicamā prakse No parastā BST līdz līdzsvarotai BST Izmēģiniet to!
A Vienkāršs risinājums ir šķērsot Inorder mezglus un pa vienam ievietot pašbalansējošā BST, piemēram, AVL kokā. Šī risinājuma laika sarežģītība ir O(n Log n) un šis risinājums negarantē minimālo iespējamo augstumu, jo sliktākajā gadījumā AVL koka augstums var būt 1,44* žurnāls 2 n .
An Efektīvs risinājums var izveidot līdzsvarotu BST O(n) laikā ar minimālu iespējamo augstumu. Zemāk ir soļi.
- Pārvietojiet doto BST secībā un saglabājiet rezultātu masīvā. Šis solis aizņem O(n) laiku. Ņemiet vērā, ka šis masīvs tiks kārtots, jo BST šķērsošana secībā vienmēr rada sakārtotu secību.
- Izveidojiet līdzsvarotu BST no iepriekš izveidotā sakārtotā masīva, izmantojot apspriesto rekursīvo pieeju šeit . Šis solis aizņem arī O(n) laiku, jo mēs šķērsojam katru elementu precīzi vienreiz, un elementa apstrāde prasa O(1) laiku.
Zemāk ir aprakstīta iepriekš minēto darbību īstenošana.
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->pa kreisi, mezgli);> >nodes.push_back(root);> >storeBSTNodes(root->pa labi, mezgli);> }> /* Recursive function to construct binary tree */> Node* buildTreeUtil(vector &nodes,>int> start,> >int> end)> {> >// base case> >if> (start>beigas)> >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->pa kreisi = buildTreeUtil(mezgli, sākums, 1. vidus);> >root->pa labi = buildTreeUtil(mezgli, vidus+1, beigas);> >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->dati = dati;> >node->pa kreisi = mezgls->pa labi = NULL;> >return> (node);> }> /* Function to do preorder traversal of tree */> void> preOrder(Node* node)> {> >if> (node == NULL)> >return>;> >printf>(>'%d '>, node->dati);> >preOrder(node->pa kreisi);> >preOrder(node->pa labi);> }> // Driver program> int> main()> {> >/* Constructed skewed binary tree is> >10> >/> >8> >/> >7> >/> >6> >/> >5 */> >Node* root = newNode(10);> >root->pa kreisi = newNode(8);> >root->pa kreisi->pa kreisi = newNode(7);> >root->pa kreisi->pa kreisi->pa kreisi = newNode(6);> >root->pa kreisi->pa kreisi->pa kreisi->pa kreisi = newNode(5);> >root = buildTree(root);> >printf>(>'Preorder traversal of balanced '> >'BST is :
'>);> >preOrder(root);> >return> 0;> }> |
>
verilog parametrs
>
Java
bash cilpai no 1. līdz 10
// 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>beigas)> >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>beigas:> >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> |
kas ir kaudze java
>
>
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>beigas)> >{> >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
apaļa matemātika java
> >// 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>beigas)> >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);> > > |
>
>Izvade
Preorder traversal of balanced BST is : 7 5 6 8 10>
Laika sarežģītība: O(n), tā kā mēs tikai divreiz šķērsojam koku. Vienreiz inorder traversā un tad līdzsvarota koka būvniecībā.
Palīgtelpa: O(n), Papildu vieta tiek izmantota, lai vektorā saglabātu secības šķērsošanas mezglus. Arī rekursijas izsaukuma steka aizņemtā papildu vieta ir O(h), kur h ir koka augstums.
Šis raksts ir pievienots Aditja Gēla . Ja jums patīktechcodeview.com un vēlaties sniegt savu ieguldījumu, varat arī uzrakstīt rakstu un nosūtīt savu rakstu uz e-pastu [email protected]