I denne artikel vil vi diskutere det binære søgetræ. Denne artikel vil være meget nyttig og informativ for studerende med teknisk baggrund, da det er et vigtigt emne for deres kursus.
Inden vi går direkte til det binære søgetræ, lad os først se en kort beskrivelse af træet.
Hvad er et træ?
Et træ er en slags datastruktur, der bruges til at repræsentere dataene i hierarkisk form. Det kan defineres som en samling af objekter eller enheder kaldet som noder, der er knyttet sammen for at simulere et hierarki. Træ er en ikke-lineær datastruktur, da dataene i et træ ikke lagres lineært eller sekventielt.
Lad os nu starte emnet, det binære søgetræ.
vælg som
Hvad er et binært søgetræ?
Et binært søgetræ følger en eller anden rækkefølge for at arrangere elementerne. I et binært søgetræ skal værdien af venstre node være mindre end den overordnede node, og værdien af den højre node skal være større end den overordnede node. Denne regel anvendes rekursivt på venstre og højre undertræ af roden.
Lad os forstå konceptet med binært søgetræ med et eksempel.
I ovenstående figur kan vi observere, at rodknuden er 40, og alle knuderne i det venstre undertræ er mindre end rodknuden, og alle knudepunkterne i det højre undertræ er større end rodknuden.
På samme måde kan vi se det venstre barn af rodknude er større end dets venstre barn og mindre end dets højre barn. Så det opfylder også egenskaben for binært søgetræ. Derfor kan vi sige, at træet i ovenstående billede er et binært søgetræ.
Antag, at hvis vi ændrer værdien af node 35 til 55 i ovenstående træ, så tjek om træet vil være binært søgetræ eller ej.
I ovenstående træ er værdien af rodnoden 40, hvilket er større end dets venstre underordnede 30, men mindre end det højre underordnede under 30, dvs. 55. Så ovenstående træ opfylder ikke egenskaben for binært søgetræ. Derfor er ovenstående træ ikke et binært søgetræ.
Fordele ved binært søgetræ
- Det er nemt at søge efter et element i det binære søgetræ, da vi altid har et hint om, hvilket undertræ der har det ønskede element.
- Sammenlignet med array og linkede lister er indsættelses- og sletningsoperationer hurtigere i BST.
Eksempel på oprettelse af et binært søgetræ
Lad os nu se oprettelsen af et binært søgetræ ved hjælp af et eksempel.
websteder som coomeet
Antag, at dataelementerne er - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Først skal vi indsætte Fire. Fem ind i træet som træets rod.
- Læs derefter det næste element; hvis den er mindre end rodknuden, indsæt den som roden af det venstre undertræ og flyt til det næste element.
- Ellers, hvis elementet er større end rodnoden, skal du indsætte det som roden af det højre undertræ.
Lad os nu se processen med at oprette det binære søgetræ ved hjælp af det givne dataelement. Processen med at oprette BST er vist nedenfor -
Trin 1 - Indsæt 45.
Trin 2 - Indsæt 15.
Da 15 er mindre end 45, så indsæt det som rodknudepunktet for det venstre undertræ.
Trin 3 - Indsæt 79.
Da 79 er større end 45, så indsæt det som rodknudepunktet for det højre undertræ.
Trin 4 - Indsæt 90.
90 er større end 45 og 79, så det vil blive indsat som det højre undertræ af 79.
Trin 5 - Indsæt 10.
10 er mindre end 45 og 15, så det vil blive indsat som et venstre undertræ på 15.
javascript window.open
Trin 6 - Indsæt 55.
55 er større end 45 og mindre end 79, så det vil blive indsat som venstre undertræ af 79.
Trin 7 - Indsæt 12.
12 er mindre end 45 og 15, men større end 10, så det vil blive indsat som det højre undertræ af 10.
Trin 8 - Indsæt 20.
20 er mindre end 45, men større end 15, så det vil blive indsat som det højre undertræ af 15.
Trin 9 - Indsæt 50.
50 er større end 45, men mindre end 79 og 55. Så det vil blive indsat som et venstre undertræ på 55.
Nu er oprettelsen af det binære søgetræ fuldført. Lad os derefter bevæge os mod de operationer, der kan udføres på binært søgetræ.
Vi kan udføre indsættelses-, sletnings- og søgeoperationer på det binære søgetræ.
Lad os forstå, hvordan en søgning udføres på et binært søgetræ.
Søgning i binært søgetræ
Søgning betyder at finde eller lokalisere et specifikt element eller node i en datastruktur. I binært søgetræ er det nemt at søge i en node, fordi elementer i BST er gemt i en bestemt rækkefølge. Trinnene til at søge en node i binært søgetræ er angivet som følger -
- Sammenlign først det element, der skal søges i, med træets rodelement.
- Hvis root matches med målelementet, så returner nodens placering.
- Hvis det ikke er matchet, så tjek om elementet er mindre end rodelementet, hvis det er mindre end rodelementet, så flyt til venstre undertræ.
- Hvis det er større end rodelementet, så flyt til højre undertræ.
- Gentag ovenstående procedure rekursivt, indtil matchen er fundet.
- Hvis elementet ikke findes eller ikke findes i træet, returneres NULL.
Lad os nu forstå søgningen i binært træ ved hjælp af et eksempel. Vi tager det binære søgetræ dannet ovenfor. Antag, at vi skal finde node 20 fra nedenstående træ.
Trin 1:
Trin 2:
Trin 3:
Lad os nu se algoritmen til at søge efter et element i det binære søgetræ.
Algoritme til at søge efter et element i binært søgetræ
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
javascript kommentar
Efter udførelse af ovenstående kode vil outputtet være -
Så det handler om artiklen. Håber artiklen vil være nyttig og informativ for dig.