I den här artikeln kommer vi att diskutera det binära sökträdet. Den här artikeln kommer att vara mycket användbar och informativ för studenter med teknisk bakgrund eftersom det är ett viktigt ämne för deras kurs.
Innan vi går direkt till det binära sökträdet, låt oss först se en kort beskrivning av trädet.
Vad är ett träd?
Ett träd är en slags datastruktur som används för att representera data i hierarkisk form. Det kan definieras som en samling objekt eller enheter som kallas noder som är länkade samman för att simulera en hierarki. Träd är en icke-linjär datastruktur eftersom data i ett träd inte lagras linjärt eller sekventiellt.
Låt oss nu börja ämnet, det binära sökträdet.
Vad är ett binärt sökträd?
Ett binärt sökträd följer någon ordning för att ordna elementen. I ett binärt sökträd måste värdet på vänster nod vara mindre än föräldernoden, och värdet på höger nod måste vara större än föräldernoden. Denna regel tillämpas rekursivt på rotens vänstra och högra underträd.
Låt oss förstå konceptet med binärt sökträd med ett exempel.
I figuren ovan kan vi observera att rotnoden är 40, och alla noder i det vänstra underträdet är mindre än rotnoden, och alla noder i det högra underträdet är större än rotnoden.
På samma sätt kan vi se rotnodens vänstra barn är större än dess vänstra barn och mindre än dess högra barn. Så det uppfyller också egenskapen för binärt sökträd. Därför kan vi säga att trädet i bilden ovan är ett binärt sökträd.
Anta att om vi ändrar värdet på nod 35 till 55 i ovanstående träd, kontrollera om trädet kommer att vara binärt sökträd eller inte.
I ovanstående träd är rotnodens värde 40, vilket är större än dess vänstra underordnade 30 men mindre än höger underordnat 30, dvs. 55. Så, ovanstående träd uppfyller inte egenskapen för binärt sökträd. Därför är trädet ovan inte ett binärt sökträd.
Fördelar med binärt sökträd
- Att söka efter ett element i det binära sökträdet är enkelt eftersom vi alltid har en antydan om att vilket underträd som har det önskade elementet.
- Jämfört med array och länkade listor är insättnings- och raderingsoperationer snabbare i BST.
Exempel på att skapa ett binärt sökträd
Låt oss nu se skapandet av ett binärt sökträd med ett exempel.
Antag att dataelementen är - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Först måste vi infoga Fyra fem in i trädet som trädets rot.
- Läs sedan nästa element; om den är mindre än rotnoden, infoga den som roten till det vänstra underträdet och flytta till nästa element.
- Annars, om elementet är större än rotnoden, infoga det som roten till det högra underträdet.
Låt oss nu se processen för att skapa det binära sökträdet med hjälp av det givna dataelementet. Processen för att skapa BST visas nedan -
Steg 1 - Infoga 45.
Steg 2 - Infoga 15.
Eftersom 15 är mindre än 45, så infoga det som rotnoden för det vänstra underträdet.
Steg 3 - Infoga 79.
Eftersom 79 är större än 45, så infoga det som rotnoden för det högra underträdet.
vyer och tabeller
Steg 4 - Infoga 90.
90 är större än 45 och 79, så det kommer att infogas som det högra underträdet av 79.
Steg 5 - Infoga 10.
10 är mindre än 45 och 15, så det kommer att infogas som ett vänster underträd av 15.
Steg 6 - Infoga 55.
55 är större än 45 och mindre än 79, så det kommer att infogas som det vänstra underträdet av 79.
Steg 7 - Infoga 12.
12 är mindre än 45 och 15 men större än 10, så det kommer att infogas som det högra underträdet av 10.
Steg 8 - Infoga 20.
20 är mindre än 45 men större än 15, så det kommer att infogas som det högra underträdet av 15.
Steg 9 - Infoga 50.
50 är större än 45 men mindre än 79 och 55. Så det kommer att infogas som ett vänster underträd av 55.
Nu är skapandet av binärt sökträd slutfört. Efter det, låt oss gå mot de operationer som kan utföras på binärt sökträd.
Vi kan utföra infogning, radering och sökoperationer på det binära sökträdet.
Låt oss förstå hur en sökning utförs på ett binärt sökträd.
Söker i binärt sökträd
Sökning innebär att hitta eller lokalisera ett specifikt element eller nod i en datastruktur. I binärt sökträd är det lätt att söka i en nod eftersom element i BST lagras i en specifik ordning. Stegen för att söka en nod i binärt sökträd listas enligt följande -
- Jämför först elementet som ska sökas med trädets rotelement.
- Om root matchas med målelementet returnerar du nodens plats.
- Om det inte matchas, kontrollera om objektet är mindre än rotelementet, om det är mindre än rotelementet, flytta sedan till det vänstra underträdet.
- Om det är större än rotelementet, flytta till höger underträd.
- Upprepa ovanstående procedur rekursivt tills matchningen hittas.
- Om elementet inte hittas eller inte finns i trädet, returnera NULL.
Låt oss nu förstå sökningen i binärt träd med hjälp av ett exempel. Vi tar det binära sökträdet som bildas ovan. Anta att vi måste hitta nod 20 från trädet nedan.
Steg 1:
Steg 2:
Steg 3:
Låt oss nu se algoritmen för att söka efter ett element i det binära sökträdet.
Algoritm för att söka efter ett element i binärt sökträd
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> Produktion
Efter exekvering av ovanstående kod kommer utgången att vara -
Så det handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig.