V tomto článku budeme diskutovať o binárnom vyhľadávacom strome. Tento článok bude veľmi užitočný a poučný pre študentov s technickým vzdelaním, pretože je to dôležitá téma ich kurzu.
Pred priamym prechodom na binárny vyhľadávací strom si najprv pozrime stručný popis stromu.
čo je strom?
Strom je druh dátovej štruktúry, ktorá sa používa na reprezentáciu údajov v hierarchickej forme. Môže byť definovaný ako kolekcia objektov alebo entít nazývaných ako uzly, ktoré sú navzájom prepojené, aby simulovali hierarchiu. Strom je nelineárna dátová štruktúra, pretože dáta v strome nie sú uložené lineárne ani sekvenčne.
Teraz začnime s témou, stromom binárneho vyhľadávania.
Čo je to strom binárneho vyhľadávania?
Binárny vyhľadávací strom sa riadi určitým poradím usporiadania prvkov. V binárnom vyhľadávacom strome musí byť hodnota ľavého uzla menšia ako rodičovský uzol a hodnota pravého uzla musí byť väčšia ako rodičovský uzol. Toto pravidlo sa rekurzívne aplikuje na ľavý a pravý podstrom koreňa.
Poďme pochopiť koncept binárneho vyhľadávacieho stromu na príklade.
Na obrázku vyššie môžeme pozorovať, že koreňový uzol je 40 a všetky uzly ľavého podstromu sú menšie ako koreňový uzol a všetky uzly pravého podstromu sú väčšie ako koreňový uzol.
Podobne môžeme vidieť, že ľavý potomok koreňového uzla je väčší ako jeho ľavý potomok a menší ako jeho pravý potomok. Spĺňa teda aj vlastnosť binárneho vyhľadávacieho stromu. Preto môžeme povedať, že strom na obrázku vyššie je binárny vyhľadávací strom.
Predpokladajme, že ak zmeníme hodnotu uzla 35 na 55 vo vyššie uvedenom strome, skontrolujte, či strom bude binárny vyhľadávací strom alebo nie.
Vo vyššie uvedenom strome je hodnota koreňového uzla 40, čo je väčšia ako jeho ľavý potomok 30, ale menšia ako pravý potomok 30, t.j. 55. Takže vyššie uvedený strom nespĺňa vlastnosť binárneho vyhľadávacieho stromu. Preto vyššie uvedený strom nie je binárnym vyhľadávacím stromom.
Výhody binárneho vyhľadávacieho stromu
- Vyhľadávanie prvku v binárnom vyhľadávacom strome je jednoduché, pretože vždy máme nápovedu, ktorý podstrom obsahuje požadovaný prvok.
- V porovnaní s poľami a prepojenými zoznamami sú operácie vkladania a vymazávania v BST rýchlejšie.
Príklad vytvorenia binárneho vyhľadávacieho stromu
Teraz sa pozrime na vytvorenie binárneho vyhľadávacieho stromu pomocou príkladu.
Predpokladajme, že dátové prvky sú - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Najprv musíme vložiť Štyri do stromu ako koreň stromu.
- Potom si prečítajte nasledujúci prvok; ak je menší ako koreňový uzol, vložte ho ako koreň ľavého podstromu a prejdite na ďalší prvok.
- V opačnom prípade, ak je prvok väčší ako koreňový uzol, vložte ho ako koreň pravého podstromu.
Teraz sa pozrime na proces vytvárania binárneho vyhľadávacieho stromu pomocou daného dátového prvku. Proces vytvárania BST je uvedený nižšie -
Krok 1 - Vložte 45.
použitia operačného systému
Krok 2 - Vložte 15.
Keďže 15 je menšie ako 45, vložte ho ako koreňový uzol ľavého podstromu.
Krok 3 - Vložte 79.
Keďže 79 je väčšie ako 45, vložte ho ako koreňový uzol pravého podstromu.
Krok 4 - Vložte 90.
90 je väčšie ako 45 a 79, takže sa vloží ako pravý podstrom 79.
Krok 5 - Vložte 10.
10 je menší ako 45 a 15, takže sa vloží ako ľavý podstrom 15.
Krok 6 - Vložte 55.
55 je väčší ako 45 a menší ako 79, takže bude vložený ako ľavý podstrom 79.
Krok 7 - Vložte 12.
previesť char na int java
12 je menší ako 45 a 15, ale väčší ako 10, takže bude vložený ako pravý podstrom 10.
Krok 8 - Vložte 20.
20 je menšie ako 45, ale väčšie ako 15, takže sa vloží ako pravý podstrom 15.
Krok 9 - Vložte 50.
50 je väčšie ako 45, ale menšie ako 79 a 55. Vloží sa teda ako ľavý podstrom 55.
Teraz je vytvorenie binárneho vyhľadávacieho stromu dokončené. Potom prejdime k operáciám, ktoré možno vykonať na binárnom vyhľadávacom strome.
V binárnom vyhľadávacom strome môžeme vykonávať operácie vkladania, mazania a vyhľadávania.
css pre tučné písmo
Poďme pochopiť, ako sa vykonáva vyhľadávanie v binárnom vyhľadávacom strome.
Vyhľadávanie v binárnom vyhľadávacom strome
Vyhľadávanie znamená nájsť alebo lokalizovať konkrétny prvok alebo uzol v dátovej štruktúre. V binárnom vyhľadávacom strome je vyhľadávanie uzla jednoduché, pretože prvky v BST sú uložené v špecifickom poradí. Kroky vyhľadávania uzla v strome binárneho vyhľadávania sú uvedené nasledovne -
- Najprv porovnajte prvok, ktorý sa má vyhľadávať, s koreňovým prvkom stromu.
- Ak sa root zhoduje s cieľovým prvkom, vráťte umiestnenie uzla.
- Ak sa nezhoduje, skontrolujte, či je položka menšia ako koreňový prvok, ak je menšia ako koreňový prvok, prejdite do ľavého podstromu.
- Ak je väčší ako koreňový prvok, prejdite do pravého podstromu.
- Opakujte vyššie uvedený postup rekurzívne, kým nenájdete zhodu.
- Ak sa prvok nenájde alebo sa v strome nenachádza, vráťte hodnotu NULL.
Teraz pochopme vyhľadávanie v binárnom strome pomocou príkladu. Berieme binárny vyhľadávací strom vytvorený vyššie. Predpokladajme, že musíme nájsť uzol 20 zo stromu nižšie.
Krok 1:
Krok 2:
Krok 3:
Teraz sa pozrime na algoritmus na vyhľadávanie prvku v binárnom vyhľadávacom strome.
Algoritmus na vyhľadávanie prvku v binárnom vyhľadávacom strome
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ýkon
Po vykonaní vyššie uvedeného kódu bude výstupom -
Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný.