In dit artikel bespreken we de binaire zoekboom. Dit artikel zal zeer nuttig en informatief zijn voor studenten met een technische achtergrond, aangezien het een belangrijk onderwerp van hun cursus is.

Voordat we rechtstreeks naar de binaire zoekboom gaan, bekijken we eerst een korte beschrijving van de boom.

Wat is een boom?

Een boom is een soort gegevensstructuur die wordt gebruikt om de gegevens in hiërarchische vorm weer te geven. Het kan worden gedefinieerd als een verzameling objecten of entiteiten die knooppunten worden genoemd en die met elkaar zijn verbonden om een ​​hiërarchie te simuleren. Boom is een niet-lineaire gegevensstructuur, omdat de gegevens in een boom niet lineair of opeenvolgend worden opgeslagen.

Laten we nu beginnen met het onderwerp, de binaire zoekboom.

Wat is een binaire zoekboom?

Een binaire zoekboom volgt een bepaalde volgorde om de elementen te rangschikken. In een binaire zoekboom moet de waarde van het linkerknooppunt kleiner zijn dan het bovenliggende knooppunt, en de waarde van het rechterknooppunt moet groter zijn dan het bovenliggende knooppunt. Deze regel wordt recursief toegepast op de linker- en rechtersubboom van de wortel.

Laten we het concept van de binaire zoekboom begrijpen met een voorbeeld.

In de bovenstaande afbeelding kunnen we zien dat het hoofdknooppunt 40 is, en dat alle knooppunten van de linker subboom kleiner zijn dan het hoofdknooppunt, en dat alle knooppunten van de rechter subboom groter zijn dan het hoofdknooppunt.

Op dezelfde manier kunnen we zien dat het linkerkind van het wortelknooppunt groter is dan het linkerkind en kleiner dan het rechterkind. Het voldoet dus ook aan de eigenschap van een binaire zoekboom. Daarom kunnen we zeggen dat de boom in de bovenstaande afbeelding een binaire zoekboom is.

Stel dat als we de waarde van knooppunt 35 in 55 in de bovenstaande boom wijzigen, controleren of de boom een ​​binaire zoekboom zal zijn of niet.

In de bovenstaande boom is de waarde van het hoofdknooppunt 40, wat groter is dan het linkerkind 30 maar kleiner dan het rechterkind van 30, d.w.z. 55. De bovenstaande boom voldoet dus niet aan de eigenschap van de binaire zoekboom. Daarom is de bovenstaande boom geen binaire zoekboom.

Voordelen van binaire zoekboom

• Het zoeken naar een element in de binaire zoekboom is eenvoudig omdat we altijd een indicatie hebben welke subboom het gewenste element bevat.
• In vergelijking met array- en gekoppelde lijsten zijn invoeg- en verwijderbewerkingen sneller in BST.

Voorbeeld van het maken van een binaire zoekboom

Laten we nu eens kijken naar het maken van een binaire zoekboom aan de hand van een voorbeeld.

Stel dat de gegevenselementen dat zijn - 45, 15, 79, 90, 10, 55, 12, 20, 50

• Eerst moeten we invoegen Vier vijf in de boom als de wortel van de boom.
• Lees dan het volgende element; als het kleiner is dan het hoofdknooppunt, voeg het dan in als de wortel van de linker subboom en ga naar het volgende element.
• Anders, als het element groter is dan het hoofdknooppunt, voegt u het in als de hoofdmap van de rechter subboom.

Laten we nu eens kijken naar het proces van het maken van de binaire zoekboom met behulp van het gegeven data-element. Het proces voor het maken van de BST wordt hieronder weergegeven:

Stap 1 - Plaats 45.

Stap 2 - Plaats 15.

Omdat 15 kleiner is dan 45, voegt u dit dus in als het hoofdknooppunt van de linker subboom.

Stap 3 - Plaats 79.

Omdat 79 groter is dan 45, voegt u dit dus in als het hoofdknooppunt van de rechter subboom.

Stap 4 - Plaats 90.

90 is groter dan 45 en 79, dus het wordt ingevoegd als de rechter subboom van 79.

Stap 5 - Plaats 10.

10 is kleiner dan 45 en 15, dus het wordt ingevoegd als een linker subboom van 15.

Stap 6 - Plaats 55.

55 is groter dan 45 en kleiner dan 79, dus het wordt ingevoegd als de linker subboom van 79.

Stap 7 - Plaats 12.

12 is kleiner dan 45 en 15 maar groter dan 10, dus het wordt ingevoegd als de rechter subboom van 10.

Stap 8 - Plaats 20.

20 is kleiner dan 45 maar groter dan 15, dus het wordt ingevoegd als de rechter subboom van 15.

Stap 9 - Plaats 50.

50 is groter dan 45 maar kleiner dan 79 en 55. Het wordt dus ingevoegd als een linker subboom van 55.

Nu is het maken van de binaire zoekboom voltooid. Laten we daarna verder gaan met de bewerkingen die kunnen worden uitgevoerd in de binaire zoekboom.

We kunnen invoeg-, verwijder- en zoekbewerkingen uitvoeren op de binaire zoekboom.

Laten we begrijpen hoe een zoekopdracht wordt uitgevoerd in een binaire zoekboom.

Zoeken in binaire zoekboom

Zoeken betekent het vinden of lokaliseren van een specifiek element of knooppunt in een datastructuur. In de binaire zoekboom is het zoeken naar een knooppunt eenvoudig omdat elementen in BST in een specifieke volgorde worden opgeslagen. De stappen voor het zoeken naar een knooppunt in de binaire zoekboom worden als volgt weergegeven:

1. Vergelijk eerst het te doorzoeken element met het hoofdelement van de boom.
2. Als root overeenkomt met het doelelement, retourneer dan de locatie van het knooppunt.
3. Als het niet overeenkomt, controleer dan of het item kleiner is dan het hoofdelement. Als het kleiner is dan het hoofdelement, ga dan naar de linker subboom.
4. Als het groter is dan het hoofdelement, ga dan naar de rechter subboom.
5. Herhaal de bovenstaande procedure recursief totdat de match is gevonden.
6. Als het element niet wordt gevonden of niet aanwezig is in de boom, retourneert u NULL.

Laten we nu het zoeken in de binaire boom begrijpen aan de hand van een voorbeeld. We nemen de hierboven gevormde binaire zoekboom. Stel dat we knooppunt 20 uit de onderstaande boom moeten vinden.

Stap 1:

Stap 2:

Stap 3:

Laten we nu eens kijken naar het algoritme om een ​​element in de binaire zoekboom te doorzoeken.

Algoritme om een ​​element in de binaire zoekboom te zoeken

 Search (root, item) Step 1 - if (item = root &#x2192; 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&apos;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&apos;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&apos;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&apos;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 &apos;n&apos; 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&apos;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-&gt;data = item; node-&gt;left = node-&gt;right = NULL; return node; } /*Inorder traversal of the tree formed*/ void inorder(Node *root) { if (root == NULL) return; inorder(root-&gt;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-&gt;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-&gt;left = insertion(root-&gt;left, item); else root-&gt;right = insertion(root-&gt;right, item); return root; } void search(Node* &amp;cur, int item, Node* &amp;parent) { while (cur != NULL &amp;&amp; cur-&gt;data != item) { parent = cur; if (item data) cur = cur-&gt;left; else cur = cur-&gt;right; } } void deletion(Node*&amp; 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-&gt;left == NULL &amp;&amp; cur-&gt;right == NULL) /*When node has no children*/ { if (cur != root) { if (parent-&gt;left == cur) parent-&gt;left = NULL; else parent-&gt;right = NULL; } else root = NULL; free(cur); } else if (cur-&gt;left &amp;&amp; cur-&gt;right) { Node* succ = findMinimum(cur-&gt;right); int val = succ-&gt;data; deletion(root, succ-&gt;data); cur-&gt;data = val; } else { Node* child = (cur-&gt;left)? cur-&gt;left: cur-&gt;right; if (cur != root) { if (cur == parent-&gt;left) parent-&gt;left = child; else parent-&gt;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(&apos;The inorder traversal of the given binary tree is - 
&apos;); inorder(root); deletion(root, 25); printf(&apos;
After deleting node 25, the inorder traversal of the given binary tree is - 
&apos;); inorder(root); insertion(root, 2); printf(&apos;
After inserting node 2, the inorder traversal of the given binary tree is - 
&apos;); 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&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></root>

Uitvoer

Linux gratis ipconfig

Na de uitvoering van de bovenstaande code zal de uitvoer zijn:

Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.