Šiame straipsnyje aptarsime dvejetainės paieškos medį. Šis straipsnis bus labai naudingas ir informatyvus studentams, turintiems techninių žinių, nes tai svarbi jų kurso tema.
Prieš pereidami tiesiai prie dvejetainio paieškos medžio, pirmiausia pažiūrėkime trumpą medžio aprašymą.
Kas yra medis?
Medis yra tam tikra duomenų struktūra, naudojama duomenims pateikti hierarchine forma. Jį galima apibrėžti kaip objektų arba objektų, vadinamų mazgais, rinkinį, kurie yra susieti kartu, kad imituotų hierarchiją. Medis yra nelinijinė duomenų struktūra, nes duomenys medyje nėra saugomi tiesiškai arba nuosekliai.
Dabar pradėkime temą – dvejetainės paieškos medį.
Kas yra dvejetainės paieškos medis?
Dvejetainis paieškos medis atitinka tam tikrą elementų išdėstymo tvarką. Dvejetainėje paieškos medyje kairiojo mazgo reikšmė turi būti mažesnė nei pirminio mazgo, o dešiniojo mazgo vertė turi būti didesnė nei pirminio mazgo. Ši taisyklė rekursyviai taikoma kairiajam ir dešiniajam šaknies pomedžiui.
Supraskime dvejetainio paieškos medžio sąvoką su pavyzdžiu.
Aukščiau pateiktame paveikslėlyje galime pastebėti, kad šakninis mazgas yra 40, o visi kairiojo pomedžio mazgai yra mažesni už šakninį, o visi dešiniojo pomedžio mazgai yra didesni už šakninį mazgą.
Panašiai matome, kad kairysis šaknies mazgo vaikas yra didesnis už kairįjį ir mažesnis už dešinįjį. Taigi, jis taip pat atitinka dvejetainio paieškos medžio savybę. Todėl galime sakyti, kad aukščiau esančiame paveikslėlyje esantis medis yra dvejetainis paieškos medis.
Tarkime, jei aukščiau esančiame medyje pakeisime mazgo 35 reikšmę į 55, patikrinkite, ar medis bus dvejetainis paieškos medis, ar ne.
Aukščiau pateiktame medyje šaknies mazgo reikšmė yra 40, o tai yra didesnė už kairiojo porūšio 30, bet mažesnė už dešinįjį porūšį 30, ty 55. Taigi aukščiau pateiktas medis neatitinka dvejetainio paieškos medžio savybių. Todėl aukščiau pateiktas medis nėra dvejetainis paieškos medis.
Dvejetainės paieškos medžio privalumai
- Ieškoti elemento dvejetainiame paieškos medyje yra paprasta, nes visada turime užuominą, kuris pomedis turi norimą elementą.
- Palyginti su masyvu ir susietais sąrašais, BST įterpimo ir ištrynimo operacijos yra greitesnės.
Dvejetainės paieškos medžio kūrimo pavyzdys
Dabar pažiūrėkime, kaip sukurti dvejetainį paieškos medį naudojant pavyzdį.
Tarkime, kad duomenų elementai yra – 45, 15, 79, 90, 10, 55, 12, 20, 50
- Pirmiausia turime įterpti Keturi į medį kaip medžio šaknis.
- Tada perskaitykite kitą elementą; jei jis mažesnis už šakninį mazgą, įterpkite jį kaip kairiojo pomedžio šaknį ir pereikite prie kito elemento.
- Kitu atveju, jei elementas yra didesnis nei šakninis mazgas, įterpkite jį kaip dešiniojo pomedžio šaknį.
Dabar pažiūrėkime, kaip sukurti dvejetainį paieškos medį naudojant nurodytą duomenų elementą. BST kūrimo procesas parodytas žemiau -
1 veiksmas – įdėkite 45.
2 veiksmas – įdėkite 15.
Kadangi 15 yra mažesnis nei 45, įterpkite jį kaip kairiojo pomedžio šakninį mazgą.
3 veiksmas – įdėkite 79.
Kadangi 79 yra didesnis nei 45, įterpkite jį kaip dešiniojo pomedžio šakninį mazgą.
4 veiksmas – įdėkite 90.
90 yra didesnis nei 45 ir 79, todėl jis bus įterptas kaip dešinysis 79 pomedis.
5 veiksmas – įdėkite 10.
10 yra mažesnis nei 45 ir 15, todėl jis bus įterptas kaip kairysis 15 pomedis.
6 veiksmas – įdėkite 55.
55 yra didesnis nei 45 ir mažesnis nei 79, todėl jis bus įterptas kaip kairysis 79 pomedis.
Neena Gupta
7 veiksmas – įdėkite 12.
12 yra mažesnis nei 45 ir 15, bet didesnis nei 10, todėl jis bus įterptas kaip dešinysis 10 pomedis.
8 veiksmas – įdėkite 20.
20 yra mažesnis nei 45, bet didesnis nei 15, todėl jis bus įterptas kaip dešinysis 15 pomedis.
9 veiksmas – įdėkite 50.
50 yra didesnis nei 45, bet mažesnis nei 79 ir 55. Taigi, jis bus įterptas kaip kairysis 55 pomedis.
Dabar dvejetainio paieškos medžio kūrimas baigtas. Po to pereikime prie operacijų, kurias galima atlikti dvejetainėje paieškos medyje.
Dvejetainiame paieškos medyje galime atlikti įterpimo, trynimo ir paieškos operacijas.
Supraskime, kaip atliekama paieška dvejetainiame paieškos medyje.
Ieškoma dvejetainėje paieškos medyje
Paieška reiškia konkretų elementą arba mazgą duomenų struktūroje rasti arba surasti. Dvejetainėje paieškos medyje ieškoti mazgo lengva, nes BST elementai saugomi tam tikra tvarka. Mazgo paieškos dvejetainės paieškos medyje žingsniai išvardyti taip:
- Pirmiausia palyginkite ieškomą elementą su medžio šaknies elementu.
- Jei šaknis atitinka tikslinį elementą, grąžinkite mazgo vietą.
- Jei jis nesutampa, patikrinkite, ar elementas yra mažesnis už šakninį elementą, jei jis mažesnis už šakninį elementą, tada pereikite į kairįjį pomedį.
- Jei jis didesnis nei šakninis elementas, pereikite prie dešiniojo pomedžio.
- Kartokite aukščiau aprašytą procedūrą rekursyviai, kol bus rastas atitikmuo.
- Jei elementas nerastas arba jo nėra medyje, grąžinkite NULL.
Dabar, naudodamiesi pavyzdžiu, supraskime paiešką dvejetainiame medyje. Mes paimame dvejetainį paieškos medį, suformuotą aukščiau. Tarkime, kad turime rasti 20 mazgą iš žemiau esančio medžio.
1 žingsnis:
2 žingsnis:
3 veiksmas:
Dabar pažiūrėkime algoritmą, kaip ieškoti elemento dvejetainėje paieškos medyje.
Algoritmas ieškoti elemento dvejetainėje paieškos medyje
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> Išvestis
Įvykdžius aukščiau pateiktą kodą, išvestis bus -
Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.