V tem članku bomo razpravljali o binarnem iskalnem drevesu. Ta članek bo zelo koristen in informativen za študente s tehničnim znanjem, saj je pomembna tema njihovega predmeta.
Preden preidemo neposredno na binarno iskalno drevo, si najprej oglejmo kratek opis drevesa.
Kaj je drevo?
Drevo je neke vrste podatkovna struktura, ki se uporablja za predstavitev podatkov v hierarhični obliki. Lahko ga definiramo kot zbirko predmetov ali entitet, imenovanih vozlišča, ki so med seboj povezana za simulacijo hierarhije. Drevo je nelinearna podatkovna struktura, saj podatki v drevesu niso shranjeni linearno ali zaporedno.
Zdaj pa začnimo temo, drevo binarnega iskanja.
Kaj je binarno iskalno drevo?
Binarno iskalno drevo sledi določenemu vrstnemu redu za razporeditev elementov. V binarnem iskalnem drevesu mora biti vrednost levega vozlišča manjša od nadrejenega vozlišča, vrednost desnega vozlišča pa mora biti večja od nadrejenega vozlišča. To pravilo se rekurzivno uporablja za levo in desno poddrevo korena.
Razumejmo koncept binarnega iskalnega drevesa s primerom.
Na zgornji sliki lahko opazimo, da je korensko vozlišče 40 in so vsa vozlišča levega poddrevesa manjša od korenskega vozlišča, vsa vozlišča desnega poddrevesa pa so večja od korenskega vozlišča.
Podobno lahko vidimo, da je levi otrok korenskega vozlišča večji od njegovega levega otroka in manjši od njegovega desnega otroka. Torej izpolnjuje tudi lastnost binarnega iskalnega drevesa. Zato lahko rečemo, da je drevo na zgornji sliki binarno iskalno drevo.
Če v zgornjem drevesu spremenimo vrednost vozlišča 35 na 55, preverimo, ali bo drevo binarno iskalno drevo ali ne.
V zgornjem drevesu je vrednost korenskega vozlišča 40, kar je večje od njegovega levega otroka 30, a manjše od desnega otroka 30, tj. 55. Torej zgornje drevo ne izpolnjuje lastnosti binarnega iskalnega drevesa. Zato zgornje drevo ni binarno iskalno drevo.
Prednosti binarnega iskalnega drevesa
- Iskanje po elementu v binarnem iskalnem drevesu je enostavno, saj imamo vedno namig, v katerem poddrevu je želeni element.
- V primerjavi z matričnimi in povezanimi seznami so operacije vstavljanja in brisanja hitrejše v BST.
Primer ustvarjanja binarnega iskalnega drevesa
Zdaj pa si oglejmo ustvarjanje binarnega iskalnega drevesa na primeru.
razlika med podjetjem in družbo
Recimo, da so podatkovni elementi - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Najprej moramo vstaviti Štiri v drevo kot korenino drevesa.
- Nato preberite naslednji element; če je manjši od korenskega vozlišča, ga vstavite kot koren levega poddrevesa in se premaknite na naslednji element.
- V nasprotnem primeru, če je element večji od korenskega vozlišča, ga vstavite kot koren desnega poddrevesa.
Zdaj pa si oglejmo postopek ustvarjanja binarnega iskalnega drevesa z uporabo danega podatkovnega elementa. Postopek ustvarjanja BST je prikazan spodaj -
1. korak – Vstavite 45.
2. korak – Vstavite 15.
Ker je 15 manjše od 45, ga vstavite kot korensko vozlišče levega poddrevesa.
3. korak - Vstavite 79.
Ker je 79 večje od 45, ga vstavite kot korensko vozlišče desnega poddrevesa.
4. korak - Vstavite 90.
90 je večje od 45 in 79, zato bo vstavljeno kot desno poddrevo 79.
Korak 5 - Vstavite 10.
10 je manjše od 45 in 15, zato bo vstavljeno kot levo poddrevo 15.
Korak 6 - Vstavite 55.
shraniti iz
55 je večje od 45 in manjše od 79, zato bo vstavljeno kot levo poddrevo 79.
Korak 7 - Vstavite 12.
12 je manjši od 45 in 15, vendar večji od 10, zato bo vstavljen kot desno poddrevo 10.
Korak 8 - Vstavite 20.
20 je manjše od 45, a večje od 15, zato bo vstavljeno kot desno poddrevo 15.
Korak 9 - Vstavite 50.
50 je večje od 45, vendar manjše od 79 in 55. Torej bo vstavljeno kot levo poddrevo 55.
Zdaj je izdelava binarnega iskalnega drevesa končana. Nato se pomaknimo k operacijam, ki jih je mogoče izvajati v binarnem iskalnem drevesu.
Na binarnem iskalnem drevesu lahko izvajamo operacije vstavljanja, brisanja in iskanja.
Razumejmo, kako poteka iskanje v binarnem iskalnem drevesu.
Iskanje v binarnem iskalnem drevesu
Iskanje pomeni najti ali locirati določen element ali vozlišče v podatkovni strukturi. V binarnem iskalnem drevesu je iskanje po vozlišču enostavno, ker so elementi v BST shranjeni v določenem vrstnem redu. Koraki iskanja vozlišča v drevesu binarnega iskanja so navedeni na naslednji način -
- Najprej primerjajte element, ki ga želite iskati, s korenskim elementom drevesa.
- Če se koren ujema s ciljnim elementom, vrne lokacijo vozlišča.
- Če se ne ujema, preverite, ali je element manjši od korenskega elementa, če je manjši od korenskega elementa, se premaknite na levo poddrevo.
- Če je večji od korenskega elementa, se pomaknite na desno poddrevo.
- Ponavljajte zgornji postopek rekurzivno, dokler ne najdete ujemanja.
- Če elementa ni mogoče najti ali ni prisoten v drevesu, vrnite NULL.
Zdaj pa poglejmo iskanje v binarnem drevesu na primeru. Vzamemo binarno iskalno drevo, oblikovano zgoraj. Recimo, da moramo najti vozlišče 20 v spodnjem drevesu.
Korak 1:
2. korak:
3. korak:
Zdaj pa si oglejmo algoritem za iskanje elementa v binarnem iskalnem drevesu.
Algoritem za iskanje elementa v binarnem iskalnem drevesu
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> Izhod
Po izvedbi zgornje kode bo rezultat -
Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.