V tomto článku se budeme zabývat binárním vyhledávacím stromem. Tento článek bude velmi užitečný a informativní pro studenty s technickým zázemím, protože je důležitým tématem jejich kurzu.
Než se přesuneme přímo do binárního vyhledávacího stromu, podívejme se nejprve na stručný popis stromu.
co je to strom?
Strom je druh datové struktury, která se používá k reprezentaci dat v hierarchické formě. Lze jej definovat jako kolekci objektů nebo entit nazývaných uzly, které jsou vzájemně propojeny, aby simulovaly hierarchii. Strom je nelineární datová struktura, protože data ve stromu nejsou uložena lineárně ani sekvenčně.
Nyní začněme téma, strom binárního vyhledávání.
Co je to strom binárního vyhledávání?
Binární vyhledávací strom se řídí určitým pořadím uspořádání prvků. V binárním vyhledávacím stromu musí být hodnota levého uzlu menší než nadřazený uzel a hodnota pravého uzlu musí být větší než nadřazený uzel. Toto pravidlo se aplikuje rekurzivně na levý a pravý podstrom kořene.
Pojďme pochopit koncept binárního vyhledávacího stromu na příkladu.
Na obrázku výše můžeme pozorovat, že kořenový uzel je 40 a všechny uzly levého podstromu jsou menší než kořenový uzel a všechny uzly pravého podstromu jsou větší než kořenový uzel.
Podobně můžeme vidět, že levý potomek kořenového uzlu je větší než jeho levý potomek a menší než jeho pravý potomek. Splňuje tedy i vlastnost binárního vyhledávacího stromu. Můžeme tedy říci, že strom na obrázku výše je binární vyhledávací strom.
Předpokládejme, že změníme-li hodnotu uzlu 35 na 55 ve výše uvedeném stromu, zkontrolujte, zda strom bude binární vyhledávací strom nebo ne.
Ve výše uvedeném stromu je hodnota kořenového uzlu 40, což je větší než jeho levý potomek 30, ale menší než pravý potomek 30, tj. 55. Výše uvedený strom tedy nesplňuje vlastnost binárního vyhledávacího stromu. Výše uvedený strom tedy není binárním vyhledávacím stromem.
Výhody binárního vyhledávacího stromu
- Hledání prvku v binárním vyhledávacím stromu je snadné, protože vždy máme nápovědu, který podstrom má požadovaný prvek.
- Ve srovnání s maticovými a propojenými seznamy jsou operace vkládání a mazání v BST rychlejší.
Příklad vytvoření binárního vyhledávacího stromu
Nyní se podívejme na vytvoření binárního vyhledávacího stromu na příkladu.
Předpokládejme, že datové prvky jsou – 45, 15, 79, 90, 10, 55, 12, 20, 50
- Nejprve musíme vložit Čtyři pět do stromu jako kořen stromu.
- Poté si přečtěte další prvek; pokud je menší než kořenový uzel, vložte jej jako kořen levého podstromu a přejděte na další prvek.
- V opačném případě, pokud je prvek větší než kořenový uzel, vložte jej jako kořen pravého podstromu.
Nyní se podívejme na proces vytváření binárního vyhledávacího stromu pomocí daného datového prvku. Proces vytváření BST je uveden níže -
Krok 1 – Vložte 45.
Krok 2 – Vložte 15.
Protože 15 je menší než 45, vložte jej jako kořenový uzel levého podstromu.
Krok 3 – Vložte 79.
Protože 79 je větší než 45, vložte jej jako kořenový uzel pravého podstromu.
Krok 4 - Vložte 90.
90 je větší než 45 a 79, takže bude vložen jako pravý podstrom 79.
Krok 5 – Vložte 10.
java end for loop
10 je menší než 45 a 15, takže bude vložen jako levý podstrom 15.
Krok 6 – Vložte 55.
55 je větší než 45 a menší než 79, takže bude vložen jako levý podstrom 79.
Krok 7 – Vložte 12.
12 je menší než 45 a 15, ale větší než 10, takže bude vložen jako pravý podstrom 10.
Krok 8 – Vložte 20.
20 je menší než 45, ale větší než 15, takže bude vložen jako pravý podstrom 15.
Krok 9 – Vložte 50.
50 je větší než 45, ale menší než 79 a 55. Bude tedy vložen jako levý podstrom 55.
Nyní je vytvoření binárního vyhledávacího stromu dokončeno. Poté se přesuneme k operacím, které lze provádět na binárním vyhledávacím stromě.
Na binárním vyhledávacím stromě můžeme provádět operace vkládání, mazání a vyhledávání.
Pojďme pochopit, jak se provádí vyhledávání na binárním vyhledávacím stromu.
Vyhledávání v binárním vyhledávacím stromu
Hledání znamená najít nebo najít konkrétní prvek nebo uzel v datové struktuře. V binárním vyhledávacím stromu je vyhledávání uzlu snadné, protože prvky v BST jsou uloženy ve specifickém pořadí. Kroky prohledání uzlu ve stromu binárního vyhledávání jsou uvedeny následovně -
- Nejprve porovnejte hledaný prvek s kořenovým prvkem stromu.
- Pokud je root shodný s elementem target, vraťte umístění uzlu.
- Pokud se neshoduje, zkontrolujte, zda je položka menší než kořenový prvek, pokud je menší než kořenový prvek, přejděte do levého podstromu.
- Pokud je větší než kořenový prvek, přejděte do pravého podstromu.
- Opakujte výše uvedený postup rekurzivně, dokud nebude nalezena shoda.
- Pokud prvek není nalezen nebo není přítomen ve stromu, vraťte hodnotu NULL.
Nyní pochopme vyhledávání v binárním stromu na příkladu. Vezmeme binární vyhledávací strom vytvořený výše. Předpokládejme, že musíme najít uzel 20 z níže uvedeného stromu.
Krok 1:
Krok 2:
Krok 3:
Nyní se podívejme na algoritmus pro vyhledávání prvku ve stromu binárního vyhledávání.
Algoritmus pro vyhledávání prvku v binárním vyhledávacím stromu
Search (root, item) Step 1 - if (item = root → data) or (root = NULL) return root else if (item <root 2 → data) return search(root left, item) else right, end if step - < pre> <p>Now let's understand how the deletion is performed on a binary search tree. We will also see an example to delete an element from the given tree.</p> <h3>Deletion in Binary Search tree</h3> <p>In a binary search tree, we must delete a node from the tree by keeping in mind that the property of BST is not violated. To delete a node from BST, there are three possible situations occur -</p> <ul> <li>The node to be deleted is the leaf node, or,</li> <li>The node to be deleted has only one child, and,</li> <li>The node to be deleted has two children</li> </ul> <p>We will understand the situations listed above in detail.</p> <p> <strong>When the node to be deleted is the leaf node</strong> </p> <p>It is the simplest case to delete a node in BST. Here, we have to replace the leaf node with NULL and simply free the allocated space.</p> <p>We can see the process to delete a leaf node from BST in the below image. In below image, suppose we have to delete node 90, as the node to be deleted is a leaf node, so it will be replaced with NULL, and the allocated space will free.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-15.webp" alt="Binary Search tree"> <p> <strong>When the node to be deleted has only one child</strong> </p> <p>In this case, we have to replace the target node with its child, and then delete the child node. It means that after replacing the target node with its child node, the child node will now contain the value to be deleted. So, we simply have to replace the child node with NULL and free up the allocated space.</p> <p>We can see the process of deleting a node with one child from BST in the below image. In the below image, suppose we have to delete the node 79, as the node to be deleted has only one child, so it will be replaced with its child 55.</p> <p>So, the replaced node 79 will now be a leaf node that can be easily deleted.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-16.webp" alt="Binary Search tree"> <p> <strong>When the node to be deleted has two children</strong> </p> <p>This case of deleting a node in BST is a bit complex among other two cases. In such a case, the steps to be followed are listed as follows -</p> <ul> <li>First, find the inorder successor of the node to be deleted.</li> <li>After that, replace that node with the inorder successor until the target node is placed at the leaf of tree.</li> <li>And at last, replace the node with NULL and free up the allocated space.</li> </ul> <p>The inorder successor is required when the right child of the node is not empty. We can obtain the inorder successor by finding the minimum element in the right child of the node.</p> <p>We can see the process of deleting a node with two children from BST in the below image. In the below image, suppose we have to delete node 45 that is the root node, as the node to be deleted has two children, so it will be replaced with its inorder successor. Now, node 45 will be at the leaf of the tree so that it can be deleted easily.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-17.webp" alt="Binary Search tree"> <p>Now let's understand how insertion is performed on a binary search tree.</p> <h3>Insertion in Binary Search tree</h3> <p>A new key in BST is always inserted at the leaf. To insert an element in BST, we have to start searching from the root node; if the node to be inserted is less than the root node, then search for an empty location in the left subtree. Else, search for the empty location in the right subtree and insert the data. Insert in BST is similar to searching, as we always have to maintain the rule that the left subtree is smaller than the root, and right subtree is larger than the root.</p> <p>Now, let's see the process of inserting a node into BST using an example.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-18.webp" alt="Binary Search tree"> <br> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-19.webp" alt="Binary Search tree"> <h3>The complexity of the Binary Search tree</h3> <p>Let's see the time and space complexity of the Binary search tree. We will see the time complexity for insertion, deletion, and searching operations in best case, average case, and worst case.</p> <h3>1. Time Complexity</h3> <table class="table"> <tr> <th>Operations</th> <th>Best case time complexity</th> <th>Average case time complexity</th> <th>Worst case time complexity</th> </tr> <tr> <td> <strong>Insertion</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> <tr> <td> <strong>Deletion</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> <tr> <td> <strong>Search</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> </table> <p>Where 'n' is the number of nodes in the given tree.</p> <h3>2. Space Complexity</h3> <table class="table"> <tr> <th>Operations</th> <th>Space complexity</th> </tr> <tr> <td> <strong>Insertion</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Deletion</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Search</strong> </td> <td>O(n)</td> </tr> </table> <ul> <li>The space complexity of all operations of Binary search tree is O(n).</li> </ul> <h2>Implementation of Binary search tree</h2> <p>Now, let's see the program to implement the operations of Binary Search tree.</p> <p> <strong>Program:</strong> Write a program to perform operations of Binary Search tree in C++.</p> <p>In this program, we will see the implementation of the operations of binary search tree. Here, we will see the creation, inorder traversal, insertion, and deletion operations of tree.</p> <p>Here, we will see the inorder traversal of the tree to check whether the nodes of the tree are in their proper location or not. We know that the inorder traversal always gives us the data in ascending order. So, after performing the insertion and deletion operations, we perform the inorder traversal, and after traversing, if we get data in ascending order, then it is clear that the nodes are in their proper location.</p> <pre> #include using namespace std; struct Node { int data; Node *left; Node *right; }; Node* create(int item) { Node* node = new Node; node->data = item; node->left = node->right = NULL; return node; } /*Inorder traversal of the tree formed*/ void inorder(Node *root) { if (root == NULL) return; inorder(root->left); //traverse left subtree cout<data <right); traverse right subtree } node* findminimum(node* cur) *to find the inorder successor* { while(cur->left != NULL) { cur = cur->left; } return cur; } Node* insertion(Node* root, int item) /*Insert a node*/ { if (root == NULL) return create(item); /*return new node if tree is empty*/ if (item data) root->left = insertion(root->left, item); else root->right = insertion(root->right, item); return root; } void search(Node* &cur, int item, Node* &parent) { while (cur != NULL && cur->data != item) { parent = cur; if (item data) cur = cur->left; else cur = cur->right; } } void deletion(Node*& root, int item) /*function to delete a node*/ { Node* parent = NULL; Node* cur = root; search(cur, item, parent); /*find the node to be deleted*/ if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) /*When node has no children*/ { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur->right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? cur->left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } int main() { Node* root = NULL; root = insertion(root, 45); root = insertion(root, 30); root = insertion(root, 50); root = insertion(root, 25); root = insertion(root, 35); root = insertion(root, 45); root = insertion(root, 60); root = insertion(root, 4); printf('The inorder traversal of the given binary tree is -
'); inorder(root); deletion(root, 25); printf('
After deleting node 25, the inorder traversal of the given binary tree is -
'); inorder(root); insertion(root, 2); printf('
After inserting node 2, the inorder traversal of the given binary tree is -
'); inorder(root); return 0; } </data></pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-20.webp" alt="Binary Search tree"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></root> Výstup
Po provedení výše uvedeného kódu bude výstupem -
Tak to je k článku vše. Doufám, že vám článek bude užitečný a informativní.