Tässä artikkelissa käsittelemme binaarihakupuuta. Tämä artikkeli on erittäin hyödyllinen ja informatiivinen opiskelijoille, joilla on tekninen tausta, koska se on tärkeä aihe heidän kurssillaan.
Ennen kuin siirryt suoraan binäärihakupuuhun, katsotaanpa ensin puun lyhyt kuvaus.
java muuntaa merkki merkkijonoksi
Mikä on puu?
Puu on eräänlainen tietorakenne, jota käytetään esittämään tiedot hierarkkisessa muodossa. Se voidaan määritellä kokoelmaksi objekteja tai kokonaisuuksia, joita kutsutaan solmuiksi ja jotka on linkitetty toisiinsa simuloimaan hierarkiaa. Puu on epälineaarinen tietorakenne, koska puun tietoja ei tallenneta lineaarisesti tai peräkkäin.
Aloitetaan nyt aihe, binaarihakupuu.
Mikä on binäärihakupuu?
Binäärihakupuu noudattaa tiettyä järjestystä elementtien järjestämiseksi. Binaarihakupuussa vasemman solmun arvon on oltava pienempi kuin pääsolmun ja oikean solmun arvon on oltava suurempi kuin pääsolmun. Tätä sääntöä sovelletaan rekursiivisesti juuren vasempaan ja oikeaan alipuuhun.
Ymmärretään binaarihakupuun käsite esimerkin avulla.
Yllä olevasta kuvasta voidaan havaita, että juurisolmu on 40 ja kaikki vasemman alipuun solmut ovat pienempiä kuin juurisolmu ja kaikki oikean alipuun solmut ovat suurempia kuin juurisolmu.
Samoin voimme nähdä, että juurisolmun vasen lapsi on suurempi kuin sen vasen lapsi ja pienempi kuin sen oikea lapsi. Joten se täyttää myös binäärihakupuun ominaisuuden. Siksi voimme sanoa, että yllä olevan kuvan puu on binäärihakupuu.
Oletetaan, että jos muutamme solmun 35 arvoa 55:ksi yllä olevassa puussa, tarkista onko puu binäärihakupuu vai ei.
Yllä olevassa puussa juurisolmun arvo on 40, mikä on suurempi kuin sen vasen lapsi 30, mutta pienempi kuin oikea lapsi 30, eli 55. Yllä oleva puu ei siis täytä binaarihakupuun ominaisuutta. Siksi yllä oleva puu ei ole binäärihakupuu.
Binaarihakupuun edut
- Elementin etsiminen binaarihakupuusta on helppoa, koska meillä on aina vihje siitä, missä alipuussa on haluttu elementti.
- Verrattuna matriisiin ja linkitettyihin luetteloihin, lisäys- ja poistotoiminnot ovat nopeampia BST:ssä.
Esimerkki binaarihakupuun luomisesta
Katsotaanpa nyt binaarihakupuun luomista esimerkin avulla.
Oletetaan, että tietoelementit ovat - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Ensin meidän on lisättävä Neljä viisi puuhun puun juureksi.
- Lue sitten seuraava elementti; jos se on pienempi kuin juurisolmu, lisää se vasemman alipuun juureksi ja siirry seuraavaan elementtiin.
- Muussa tapauksessa, jos elementti on suurempi kuin juurisolmu, lisää se oikean alipuun juureksi.
Katsotaanpa nyt prosessia, jolla luodaan binaarihakupuu käyttämällä annettua tietoelementtiä. BST:n luomisprosessi on esitetty alla -
Vaihe 1 - Lisää 45.
Vaihe 2 - Lisää 15.
Koska 15 on pienempi kuin 45, lisää se vasemman alipuun juurisolmuksi.
Vaihe 3 - Lisää 79.
Koska 79 on suurempi kuin 45, lisää se oikean alipuun juurisolmuksi.
Vaihe 4 - Aseta 90.
90 on suurempi kuin 45 ja 79, joten se lisätään 79:n oikeanpuoleiseksi alipuuksi.
Vaihe 5 - Lisää 10.
10 on pienempi kuin 45 ja 15, joten se lisätään 15:n vasemmaksi alipuuksi.
Vaihe 6 - Aseta 55.
55 on suurempi kuin 45 ja pienempi kuin 79, joten se lisätään 79:n vasemmanpuoleiseksi alipuuksi.
Vaihe 7 - Lisää 12.
12 on pienempi kuin 45 ja 15, mutta suurempi kuin 10, joten se lisätään 10:n oikeanpuoleiseksi alipuuksi.
Vaihe 8 - Aseta 20.
20 on pienempi kuin 45, mutta suurempi kuin 15, joten se lisätään 15:n oikeanpuoleiseksi alipuuksi.
Vaihe 9 - Aseta 50.
50 on suurempi kuin 45, mutta pienempi kuin 79 ja 55. Joten se lisätään vasemmanpuoleisena alipuuna 55.
Nyt binaarihakupuun luominen on valmis. Sen jälkeen siirrytään kohti operaatioita, jotka voidaan suorittaa binaarihakupuussa.
Voimme suorittaa lisäys-, poisto- ja hakutoimintoja binäärihakupuussa.
Ymmärretään, kuinka haku suoritetaan binäärihakupuussa.
Haku binäärihakupuusta
Haku tarkoittaa tietyn elementin tai solmun löytämistä tai paikantamista tietorakenteessa. Binaarihakupuussa solmun etsiminen on helppoa, koska BST:n elementit tallennetaan tietyssä järjestyksessä. Solmun etsimisen vaiheet binaarihakupuussa on lueteltu seuraavasti -
- Vertaa ensin etsittävää elementtiä puun juurielementtiin.
- Jos root täsmää kohdeelementin kanssa, palauta solmun sijainti.
- Jos se ei täsmää, tarkista onko alkio pienempi kuin juurielementti, jos se on pienempi kuin juurielementti, siirry sitten vasemmalle alipuuhun.
- Jos se on suurempi kuin juurielementti, siirry oikeaan alipuuhun.
- Toista yllä olevaa toimenpidettä rekursiivisesti, kunnes vastaavuus löytyy.
- Jos elementtiä ei löydy tai se ei ole puussa, palauta NULL.
Ymmärretään nyt haku binääripuussa esimerkin avulla. Otamme yllä muodostetun binäärihakupuun. Oletetaan, että meidän on löydettävä solmu 20 alla olevasta puusta.
Vaihe 1:
Vaihe2:
Vaihe 3:
lista solmu javassa
Katsotaanpa nyt algoritmia, jolla haetaan elementtiä binaarihakupuussa.
Algoritmi elementin etsimiseksi binaarihakupuussa
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> Lähtö
Yllä olevan koodin suorittamisen jälkeen tulos on -
Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle.