In diesem Artikel besprechen wir den binären Suchbaum. Dieser Artikel wird für Studierende mit technischem Hintergrund sehr hilfreich und informativ sein, da es sich um ein wichtiges Thema ihres Kurses handelt.
Bevor wir direkt zum binären Suchbaum übergehen, sehen wir uns zunächst eine kurze Beschreibung des Baums an.
Was ist ein Baum?
Ein Baum ist eine Art Datenstruktur, die zur Darstellung der Daten in hierarchischer Form verwendet wird. Es kann als eine Sammlung von Objekten oder Entitäten definiert werden, die als Knoten bezeichnet werden und miteinander verknüpft sind, um eine Hierarchie zu simulieren. Baum ist eine nichtlineare Datenstruktur, da die Daten in einem Baum nicht linear oder sequentiell gespeichert werden.
Typoskript-Datumstyp
Beginnen wir nun mit dem Thema, dem binären Suchbaum.
Was ist ein binärer Suchbaum?
Ein binärer Suchbaum folgt einer bestimmten Reihenfolge, um die Elemente anzuordnen. In einem binären Suchbaum muss der Wert des linken Knotens kleiner als der des übergeordneten Knotens sein und der Wert des rechten Knotens muss größer als der des übergeordneten Knotens sein. Diese Regel wird rekursiv auf den linken und rechten Teilbaum der Wurzel angewendet.
Lassen Sie uns das Konzept des binären Suchbaums anhand eines Beispiels verstehen.
In der obigen Abbildung können wir beobachten, dass der Wurzelknoten 40 ist und alle Knoten des linken Teilbaums kleiner als der Wurzelknoten sind und alle Knoten des rechten Teilbaums größer als der Wurzelknoten sind.
Ebenso können wir sehen, dass das linke Kind des Wurzelknotens größer als sein linkes Kind und kleiner als sein rechtes Kind ist. Es erfüllt also auch die Eigenschaft eines binären Suchbaums. Daher können wir sagen, dass der Baum im obigen Bild ein binärer Suchbaum ist.
Angenommen, wir ändern den Wert von Knoten 35 in 55 im obigen Baum und prüfen, ob der Baum ein binärer Suchbaum ist oder nicht.
Im obigen Baum beträgt der Wert des Wurzelknotens 40, was größer ist als sein linkes Kind 30, aber kleiner als sein rechtes Kind von 30, d. h. 55. Der obige Baum erfüllt also nicht die Eigenschaft des binären Suchbaums. Daher ist der obige Baum kein binärer Suchbaum.
Vorteile des binären Suchbaums
- Das Suchen eines Elements im binären Suchbaum ist einfach, da wir immer einen Hinweis darauf haben, welcher Unterbaum das gewünschte Element enthält.
- Im Vergleich zu Arrays und verknüpften Listen sind Einfüge- und Löschvorgänge in BST schneller.
Beispiel für die Erstellung eines binären Suchbaums
Sehen wir uns nun die Erstellung eines binären Suchbaums anhand eines Beispiels an.
Angenommen, die Datenelemente sind - 45, 15, 79, 90, 10, 55, 12, 20, 50
- Zuerst müssen wir einfügen Vier fünf in den Baum als die Wurzel des Baumes.
- Lesen Sie dann das nächste Element. Wenn es kleiner als der Wurzelknoten ist, fügen Sie es als Wurzel des linken Teilbaums ein und wechseln Sie zum nächsten Element.
- Andernfalls, wenn das Element größer als der Wurzelknoten ist, fügen Sie es als Wurzel des rechten Teilbaums ein.
Sehen wir uns nun den Prozess der Erstellung des binären Suchbaums unter Verwendung des angegebenen Datenelements an. Der Prozess zum Erstellen des BST ist unten dargestellt:
Schritt 1 – 45 einfügen.
Shreya Ghoshal erster Ehemann
Schritt 2 – 15 einfügen.
Da 15 kleiner als 45 ist, fügen Sie ihn als Wurzelknoten des linken Teilbaums ein.
Schritt 3 – Geben Sie 79 ein.
Da 79 größer als 45 ist, fügen Sie ihn als Wurzelknoten des rechten Teilbaums ein.
Schritt 4 – 90 einfügen.
90 ist größer als 45 und 79 und wird daher als rechter Teilbaum von 79 eingefügt.
Schritt 5 – 10 einfügen.
10 ist kleiner als 45 und 15 und wird daher als linker Teilbaum von 15 eingefügt.
Schritt 6 – 55 einfügen.
So finden Sie versteckte Apps auf Android
55 ist größer als 45 und kleiner als 79 und wird daher als linker Teilbaum von 79 eingefügt.
Schritt 7 – 12 einfügen.
12 ist kleiner als 45 und 15, aber größer als 10, daher wird er als rechter Teilbaum von 10 eingefügt.
Java analysiert String in int
Schritt 8 – 20 einfügen.
20 ist kleiner als 45, aber größer als 15, daher wird er als rechter Teilbaum von 15 eingefügt.
Schritt 9 – 50 einfügen.
50 ist größer als 45, aber kleiner als 79 und 55. Daher wird es als linker Teilbaum von 55 eingefügt.
Damit ist die Erstellung des binären Suchbaums abgeschlossen. Kommen wir anschließend zu den Operationen, die im binären Suchbaum ausgeführt werden können.
Wir können Einfüge-, Lösch- und Suchvorgänge für den binären Suchbaum ausführen.
Lassen Sie uns verstehen, wie eine Suche in einem binären Suchbaum durchgeführt wird.
Suche im binären Suchbaum
Suchen bedeutet, ein bestimmtes Element oder einen bestimmten Knoten in einer Datenstruktur zu finden oder zu lokalisieren. Im binären Suchbaum ist das Durchsuchen eines Knotens einfach, da Elemente in BST in einer bestimmten Reihenfolge gespeichert werden. Die Schritte zum Durchsuchen eines Knotens im binären Suchbaum sind wie folgt aufgeführt:
- Vergleichen Sie zunächst das zu durchsuchende Element mit dem Wurzelelement des Baums.
- Wenn root mit dem Zielelement übereinstimmt, wird die Position des Knotens zurückgegeben.
- Wenn es nicht übereinstimmt, prüfen Sie, ob das Element kleiner als das Stammelement ist. Wenn es kleiner als das Stammelement ist, wechseln Sie zum linken Unterbaum.
- Wenn es größer als das Wurzelelement ist, wechseln Sie zum rechten Teilbaum.
- Wiederholen Sie den obigen Vorgang rekursiv, bis die Übereinstimmung gefunden wird.
- Wenn das Element nicht gefunden wird oder nicht im Baum vorhanden ist, geben Sie NULL zurück.
Lassen Sie uns nun die Suche im Binärbaum anhand eines Beispiels verstehen. Wir verwenden den oben gebildeten binären Suchbaum. Angenommen, wir müssen Knoten 20 im folgenden Baum finden.
Schritt 1:
Schritt 2:
Schritt 3:
wie viele 0 in einer Milliarde
Sehen wir uns nun den Algorithmus zum Durchsuchen eines Elements im binären Suchbaum an.
Algorithmus zum Durchsuchen eines Elements im binären Suchbaum
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> Ausgabe
Nach der Ausführung des obigen Codes lautet die Ausgabe:
Das ist also alles über den Artikel. Ich hoffe, der Artikel ist hilfreich und informativ für Sie.