I denne artikkelen vil vi diskutere det binære søketreet. Denne artikkelen vil være svært nyttig og informativ for studenter med teknisk bakgrunn, da det er et viktig emne for kurset deres.
Før vi går direkte til det binære søketreet, la oss først se en kort beskrivelse av treet.
Hva er et tre?
Et tre er en slags datastruktur som brukes til å representere dataene i hierarkisk form. Det kan defineres som en samling av objekter eller enheter kalt som noder som er koblet sammen for å simulere et hierarki. Tre er en ikke-lineær datastruktur da dataene i et tre ikke lagres lineært eller sekvensielt.
La oss nå starte emnet, det binære søketreet.
fjær og fjær mvc
Hva er et binært søketre?
Et binært søketre følger en eller annen rekkefølge for å ordne elementene. I et binært søketre må verdien til venstre node være mindre enn overordnet node, og verdien på høyre node må være større enn overordnet node. Denne regelen brukes rekursivt til venstre og høyre undertre av roten.
La oss forstå konseptet med binært søketre med et eksempel.
I figuren ovenfor kan vi observere at rotnoden er 40, og alle nodene til det venstre undertreet er mindre enn rotnoden, og alle nodene til det høyre undertreet er større enn rotnoden.
På samme måte kan vi se det venstre barnet av rotnoden er større enn det venstre barnet og mindre enn det høyre barnet. Så det tilfredsstiller også egenskapen til binært søketre. Derfor kan vi si at treet i bildet ovenfor er et binært søketre.
Anta at hvis vi endrer verdien av node 35 til 55 i treet ovenfor, sjekk om treet vil være binært søketre eller ikke.
I treet ovenfor er verdien av rotnoden 40, som er større enn venstre underordnet 30, men mindre enn høyre underordnet 30, dvs. 55. Så, treet ovenfor tilfredsstiller ikke egenskapen til binært søketre. Derfor er treet ovenfor ikke et binært søketre.
Fordeler med binært søketre
- Det er enkelt å søke etter et element i det binære søketreet, da vi alltid har et hint om hvilket undertre som har ønsket element.
- Sammenlignet med array og koblede lister, er innsettings- og slettingsoperasjoner raskere i BST.
Eksempel på å lage et binært søketre
La oss nå se opprettelsen av binært søketre ved å bruke et eksempel.
de er sangere
Anta at dataelementene er - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Først må vi sette inn Fire fem inn i treet som roten til treet.
- Les deretter neste element; hvis den er mindre enn rotnoden, sett den inn som roten til det venstre undertreet og gå til neste element.
- Ellers, hvis elementet er større enn rotnoden, sett det inn som roten til det høyre undertreet.
La oss nå se prosessen med å lage det binære søketreet ved å bruke det gitte dataelementet. Prosessen med å lage BST er vist nedenfor -
Trinn 1 - Sett inn 45.
Trinn 2 - Sett inn 15.
Siden 15 er mindre enn 45, så sett den inn som rotnoden til det venstre undertreet.
Trinn 3 - Sett inn 79.
Siden 79 er større enn 45, så sett den inn som rotnoden til det høyre undertreet.
Trinn 4 - Sett inn 90.
90 er større enn 45 og 79, så det vil bli satt inn som høyre undertre av 79.
Trinn 5 - Sett inn 10.
10 er mindre enn 45 og 15, så det vil bli satt inn som et venstre undertre på 15.
javascript window.open
Trinn 6 - Sett inn 55.
55 er større enn 45 og mindre enn 79, så det vil bli satt inn som venstre undertre av 79.
Trinn 7 - Sett inn 12.
12 er mindre enn 45 og 15, men større enn 10, så det vil bli satt inn som høyre undertre av 10.
Trinn 8 - Sett inn 20.
20 er mindre enn 45, men større enn 15, så det vil bli satt inn som høyre undertre av 15.
Trinn 9 - Sett inn 50.
50 er større enn 45, men mindre enn 79 og 55. Så det vil bli satt inn som et venstre undertre på 55.
Nå er opprettelsen av binært søketre fullført. Etter det, la oss gå mot operasjonene som kan utføres på binært søketre.
Vi kan utføre innsetting, sletting og søkeoperasjoner på det binære søketreet.
La oss forstå hvordan et søk utføres på et binært søketre.
Søker i binært søketre
Søk betyr å finne eller lokalisere et spesifikt element eller node i en datastruktur. I binært søketre er det enkelt å søke i en node fordi elementer i BST er lagret i en bestemt rekkefølge. Trinnene for å søke en node i binært søketre er oppført som følger -
- Sammenlign først elementet som skal søkes med rotelementet til treet.
- Hvis root matches med målelementet, returnerer du nodens plassering.
- Hvis det ikke samsvarer, sjekk om elementet er mindre enn rotelementet, hvis det er mindre enn rotelementet, flytt deretter til venstre undertreet.
- Hvis det er større enn rotelementet, så flytt til høyre undertreet.
- Gjenta prosedyren ovenfor rekursivt til matchen er funnet.
- Hvis elementet ikke finnes eller ikke finnes i treet, returnerer du NULL.
La oss nå forstå søket i binært tre ved å bruke et eksempel. Vi tar det binære søketreet dannet ovenfor. Anta at vi må finne node 20 fra treet nedenfor.
Trinn 1:
Steg 2:
Trinn 3:
La oss nå se algoritmen for å søke etter et element i det binære søketreet.
Algoritme for å søke etter et element i binært søketre
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> Produksjon
javascript kommentar
Etter utførelse av koden ovenfor, vil utgangen være -
Så det handler om artikkelen. Håper artikkelen vil være nyttig og informativ for deg.