Šajā rakstā mēs apspriedīsim bināro meklēšanas koku. Šis raksts būs ļoti noderīgs un informatīvs studentiem ar tehnisko pieredzi, jo tā ir svarīga viņu kursa tēma.
Pirms pāriet tieši uz bināro meklēšanas koku, vispirms apskatīsim īsu koka aprakstu.
Kas ir koks?
Koks ir sava veida datu struktūra, ko izmanto, lai attēlotu datus hierarhiskā formā. To var definēt kā objektu vai entītiju kolekciju, ko sauc par mezgliem, kas ir savstarpēji saistīti, lai simulētu hierarhiju. Koks ir nelineāra datu struktūra, jo dati kokā netiek glabāti lineāri vai secīgi.
Tagad sāksim tēmu — Binārās meklēšanas koku.
Kas ir binārās meklēšanas koks?
Binārais meklēšanas koks seko noteiktai secībai, lai sakārtotu elementus. Binārajā meklēšanas kokā kreisā mezgla vērtībai ir jābūt mazākai par vecākmezglu, bet labā mezgla vērtībai ir jābūt lielākai par vecākmezglu. Šis noteikums tiek rekursīvi piemērots saknes kreisajam un labajam apakškokam.
Izpratīsim binārā meklēšanas koka jēdzienu ar piemēru.
Iepriekš redzamajā attēlā var novērot, ka saknes mezgls ir 40, un visi kreisā apakškoka mezgli ir mazāki par saknes mezglu, un visi labā apakškoka mezgli ir lielāki par saknes mezglu.
Tāpat mēs varam redzēt, ka saknes mezgla kreisais bērns ir lielāks par kreiso bērnu un mazāks par labo bērnu. Tātad, tas atbilst arī binārā meklēšanas koka īpašībai. Tāpēc mēs varam teikt, ka koks iepriekš attēlā ir binārs meklēšanas koks.
Pieņemsim, ja iepriekš minētajā kokā mainām mezgla 35 vērtību uz 55, pārbaudiet, vai koks būs binārais meklēšanas koks.
Iepriekš minētajā kokā saknes mezgla vērtība ir 40, kas ir lielāka par tā kreiso atvasi 30, bet mazāka par labo atvasi 30, t.i., 55. Tātad iepriekš minētais koks neapmierina binārā meklēšanas koka īpašību. Tāpēc iepriekš minētais koks nav binārs meklēšanas koks.
Binārās meklēšanas koka priekšrocības
- Elementa meklēšana binārajā meklēšanas kokā ir vienkārša, jo mums vienmēr ir mājiens, kurā apakškokā ir vēlamais elements.
- Salīdzinot ar masīvu un saistītajiem sarakstiem, BST ievietošanas un dzēšanas darbības ir ātrākas.
Binārā meklēšanas koka izveides piemērs
Tagad apskatīsim binārā meklēšanas koka izveidi, izmantojot piemēru.
Pieņemsim, ka datu elementi ir - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Pirmkārt, mums ir jāievieto Četri kokā kā koka sakne.
- Pēc tam izlasiet nākamo elementu; ja tas ir mazāks par saknes mezglu, ievietojiet to kā kreisā apakškoka sakni un pārejiet uz nākamo elementu.
- Pretējā gadījumā, ja elements ir lielāks par saknes mezglu, ievietojiet to kā labā apakškoka sakni.
Tagad apskatīsim binārā meklēšanas koka izveides procesu, izmantojot doto datu elementu. BST izveides process ir parādīts zemāk -
1. darbība — ievietojiet 45.
2. darbība — ievietojiet 15.
Tā kā 15 ir mazāks par 45, ievietojiet to kā kreisā apakškoka saknes mezglu.
iestatīt java
3. darbība — ievietojiet 79.
Tā kā 79 ir lielāks par 45, ievietojiet to kā labā apakškoka saknes mezglu.
4. darbība — ievietojiet 90.
90 ir lielāks par 45 un 79, tāpēc tas tiks ievietots kā 79 labais apakškoks.
5. darbība — ievietojiet 10.
10 ir mazāks par 45 un 15, tāpēc tas tiks ievietots kā 15 kreisais apakškoks.
6. darbība — ievietojiet 55.
55 ir lielāks par 45 un mazāks par 79, tāpēc tas tiks ievietots kā 79 kreisais apakškoks.
7. darbība — ievietojiet 12.
12 ir mazāks par 45 un 15, bet lielāks par 10, tāpēc tas tiks ievietots kā 10 labais apakškoks.
8. darbība — ievietojiet 20.
20 ir mazāks par 45, bet lielāks par 15, tāpēc tas tiks ievietots kā 15 labais apakškoks.
9. darbība — ievietojiet 50.
50 ir lielāks par 45, bet mazāks par 79 un 55. Tātad tas tiks ievietots kā 55 kreisais apakškoks.
Tagad binārā meklēšanas koka izveide ir pabeigta. Pēc tam pāriesim uz operācijām, kuras var veikt Binārā meklēšanas kokā.
Mēs varam veikt ievietošanas, dzēšanas un meklēšanas darbības binārajā meklēšanas kokā.
Sapratīsim, kā tiek veikta meklēšana binārā meklēšanas kokā.
Meklēšana binārajā meklēšanas kokā
Meklēšana nozīmē konkrēta elementa vai mezgla atrašanu vai atrašanu datu struktūrā. Binārajā meklēšanas kokā mezgla meklēšana ir vienkārša, jo elementi BST tiek glabāti noteiktā secībā. Mezgla meklēšanas darbības binārās meklēšanas kokā ir norādītas šādi:
- Vispirms salīdziniet meklējamo elementu ar koka saknes elementu.
- Ja sakne ir saskaņota ar mērķa elementu, atgrieziet mezgla atrašanās vietu.
- Ja tas nav saskaņots, pārbaudiet, vai vienums ir mazāks par saknes elementu, ja tas ir mazāks par saknes elementu, tad pārejiet uz kreiso apakškoku.
- Ja tas ir lielāks par saknes elementu, pārejiet uz labo apakškoku.
- Atkārtojiet iepriekš minēto procedūru rekursīvi, līdz tiek atrasta atbilstība.
- Ja elements nav atrasts vai nav kokā, atgrieziet NULL.
Tagad, izmantojot piemēru, sapratīsim meklēšanu binārajā kokā. Mēs izmantojam iepriekš izveidoto bināro meklēšanas koku. Pieņemsim, ka mums ir jāatrod mezgls 20 no zemāk esošā koka.
1. darbība:
2. darbība:
3. darbība:
zemsvītras piezīmes
Tagad apskatīsim algoritmu elementa meklēšanai binārajā meklēšanas kokā.
Algoritms elementa meklēšanai binārajā meklēšanas kokā
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> Izvade
Pēc iepriekš minētā koda izpildes izvade būs -
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.