Menü

Binärer Suchbaum C ++: BST-Implementierung und Operationen mit Beispielen

  • Haupt
  • Andere
  • Binärer Suchbaum C ++: BST-Implementierung und Operationen mit Beispielen

binary search tree c

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Ausführliches Tutorial zum binären Suchbaum (BST) in C ++, einschließlich Operationen, C ++ - Implementierung, Vorteilen und Beispielprogrammen:

Ein binärer Suchbaum oder BST, wie er im Volksmund genannt wird, ist ein binärer Baum, der die folgenden Bedingungen erfüllt:

  1. Die Knoten, die kleiner sind als der Wurzelknoten, der als linke untergeordnete Knoten der BST platziert wird.
  2. Die Knoten, die größer sind als der Stammknoten, der als die richtigen untergeordneten Knoten der BST platziert wird.
  3. Die linken und rechten Teilbäume sind wiederum die binären Suchbäume.

Diese Anordnung zum Ordnen der Schlüssel in einer bestimmten Reihenfolge erleichtert es dem Programmierer, Vorgänge wie Suchen, Einfügen, Löschen usw. effizienter auszuführen. Wenn die Knoten nicht geordnet sind, müssen wir möglicherweise jeden einzelnen Knoten vergleichen, bevor wir das Operationsergebnis erhalten können.

=> Überprüfen Sie hier die komplette C ++ - Schulungsserie.

Binärer Suchbaum in C ++

Was du lernen wirst:

Binärer Suchbaum C ++

Ein Beispiel für eine BST ist unten gezeigt.

Probe BST

Binäre Suchbäume werden aufgrund dieser spezifischen Reihenfolge der Knoten auch als 'geordnete binäre Bäume' bezeichnet.

Aus der obigen BST können wir sehen, dass der linke Teilbaum Knoten hat, die kleiner als die Wurzel sind, d. H. 45, während der rechte Teilbaum Knoten hat, die größer als 45 sind.

Lassen Sie uns nun einige grundlegende Operationen von BST diskutieren.

Grundoperationen

# 1) Einfügen

Die Einfügeoperation fügt einen neuen Knoten in einen binären Suchbaum ein.

Der Algorithmus für die binäre Suchbaum-Einfügeoperation ist unten angegeben.

Was ist der beste YouTube-Videokonverter?
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; end

Wie im obigen Algorithmus gezeigt, müssen wir sicherstellen, dass der Knoten an der richtigen Position platziert ist, damit wir nicht gegen die BST-Reihenfolge verstoßen.

Operation in BST einfügen

Wie wir in der obigen Folge von Diagrammen sehen, führen wir eine Reihe von Einfügeoperationen durch. Nach dem Vergleich des einzufügenden Schlüssels mit dem Wurzelknoten wird der linke oder rechte Teilbaum ausgewählt, damit der Schlüssel an der entsprechenden Position als Blattknoten eingefügt werden kann.

# 2) Löschen

Löschvorgang löscht einen Knoten, der dem angegebenen Schlüssel entspricht, aus BST. Auch in diesem Vorgang müssen wir die verbleibenden Knoten nach dem Löschen neu positionieren, damit die BST-Reihenfolge nicht verletzt wird.

Abhängig davon, welchen Knoten wir löschen müssen, gibt es in BST die folgenden Fälle zum Löschen:

# 1) Wenn der Knoten ein Blattknoten ist

Wenn der zu löschende Knoten ein Blattknoten ist, löschen wir den Knoten direkt.

Knoten ist ein Blattknoten

# 2) Wenn der Knoten nur ein Kind hat

Wenn der zu löschende Knoten nur ein Kind hat, kopieren wir das Kind in den Knoten und löschen das Kind.

Knoten hat nur ein Kind

# 3) Wenn der Knoten zwei Kinder hat

Wenn der zu löschende Knoten zwei untergeordnete Knoten hat, suchen wir den Inorder-Nachfolger für den Knoten und kopieren den Inorder-Nachfolger auf den Knoten. Später löschen wir den Inorder-Nachfolger.

Knoten hat zwei Kinder

In der obigen Baumstruktur zum Löschen des Knotens 6 mit zwei untergeordneten Elementen finden wir zuerst den Inorder-Nachfolger für diesen zu löschenden Knoten. Wir finden den Inorder-Nachfolger, indem wir den Mindestwert im richtigen Teilbaum finden. Im obigen Fall beträgt der Mindestwert im rechten Teilbaum 7. Wir kopieren es auf den zu löschenden Knoten und löschen dann den Inorder-Nachfolger.

# 3) Suchen

Die Suchoperation von BST sucht nach einem bestimmten Element, das in der BST als 'Schlüssel' identifiziert wurde. Der Vorteil der Suche nach einem Element in BST besteht darin, dass nicht der gesamte Baum durchsucht werden muss. Aufgrund der Reihenfolge in BST vergleichen wir stattdessen nur den Schlüssel mit der Wurzel.

Wenn der Schlüssel mit root identisch ist, geben wir root zurück. Wenn der Schlüssel nicht root ist, vergleichen wir ihn mit dem root, um festzustellen, ob wir den linken oder rechten Teilbaum durchsuchen müssen. Sobald wir den Teilbaum gefunden haben, müssen wir den Schlüssel suchen und rekursiv in einem der Teilbäume danach suchen.

Es folgt der Algorithmus für eine Suchoperation in BST.

Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end

Suchvorgang in BST

Wenn wir einen Schlüssel mit dem Wert 6 im obigen Baum suchen möchten, vergleichen wir zuerst den Schlüssel mit dem Wurzelknoten, d. H. If (6 == 7) => No if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Als nächstes steigen wir zum linken Unterbaum ab. Wenn (6 == 5) => Nein.

Wenn (6 Nein; das bedeutet 6> 5 und wir müssen uns nach rechts bewegen.

If (6 == 6) => Ja; Der Schlüssel ist gefunden.

# 4) Durchquerungen

Wir haben bereits die Durchquerungen für den Binärbaum besprochen. Auch im Fall von BST können wir den Baum durchlaufen, um die Reihenfolge inOrder, Preorder oder PostOrder zu erhalten. Wenn wir die BST in der Inorder01-Sequenz durchlaufen, erhalten wir tatsächlich die sortierte Sequenz.

Wir haben dies in der folgenden Abbildung gezeigt.

Durchquerungen

Die Durchquerungen für den obigen Baum sind wie folgt:

Inorder Traversal (lnr): 3 5 6 7 8 9 10
Vorbestellungsdurchlauf (nlr): 7 5 3 6 9 8 10
PostOrder Traversal (lrn): 3 6 5 8 10 9 7

Illustration

Lassen Sie uns aus den unten angegebenen Daten einen binären Suchbaum erstellen.

45 30 60 65 70

Nehmen wir das erste Element als Wurzelknoten.

# 1) 45

Wurzelknoten

In den folgenden Schritten platzieren wir die Daten gemäß der Definition des binären Suchbaums. Wenn die Daten kleiner als der übergeordnete Knoten sind, werden sie am linken untergeordneten Knoten platziert. Wenn die Daten größer als der übergeordnete Knoten sind, werden sie platziert wird das richtige Kind sein.

Diese Schritte werden unten gezeigt.

# 2) 30

Binärer Suchbaum Schritt 1 30

# 3) 60

Binärer Suchbaum Schritt 2 60

# 4) 65

11 Binärer Suchbaum Schritt 3

# 5) 70

Binärer Suchbaum Schritt 4

Wenn wir die Inorder Traversal für die oben konstruierte BST durchführen, die wir gerade erstellt haben, ist die Reihenfolge wie folgt.

Inorder Traversal Sequence

Wir können sehen, dass die Durchquerungssequenz Elemente in aufsteigender Reihenfolge angeordnet hat.

Implementierung des binären Suchbaums C ++

Lassen Sie uns BST und seine Operationen mithilfe der C ++ - Implementierung demonstrieren.

#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'<

Ausgabe:

Binärer Suchbaum erstellt (Inorder Traversal):

30 40 60 65 70

Knoten 40 löschen

Inorder Traversal für den geänderten binären Suchbaum:

30 60 65 70

Im obigen Programm geben wir die BST in der Reihenfolge der Durchquerung aus.

Vorteile von BST

# 1) Die Suche ist sehr effizient

Wir haben alle Knoten von BST in einer bestimmten Reihenfolge, daher ist die Suche nach einem bestimmten Artikel sehr effizient und schneller. Dies liegt daran, dass wir nicht den gesamten Baum durchsuchen und alle Knoten vergleichen müssen.

Wir müssen nur den Wurzelknoten mit dem Element vergleichen, das wir suchen, und dann entscheiden wir, ob wir im linken oder rechten Teilbaum suchen müssen.

# 2) Effizientes Arbeiten im Vergleich zu Arrays und verknüpften Listen

Wenn wir bei BST nach einem Element suchen, wird bei jedem Schritt die Hälfte des linken oder rechten Teilbaums entfernt, wodurch die Leistung des Suchvorgangs verbessert wird. Dies steht im Gegensatz zu Arrays oder verknüpften Listen, in denen alle Elemente nacheinander verglichen werden müssen, um ein bestimmtes Element zu suchen.

# 3) Einfügen und Löschen sind schneller

Einfüge- und Löschvorgänge sind im Vergleich zu anderen Datenstrukturen wie verknüpften Listen und Arrays ebenfalls schneller.

Anwendungen von BST

Einige der Hauptanwendungen von BST sind wie folgt:

Verwendung einer Torrent-Datei
  • BST wird verwendet, um die mehrstufige Indizierung in Datenbankanwendungen zu implementieren.
  • BST wird auch verwendet, um Konstrukte wie ein Wörterbuch zu implementieren.
  • Mit BST können verschiedene effiziente Suchalgorithmen implementiert werden.
  • BST wird auch in Anwendungen verwendet, für die eine sortierte Liste als Eingabe erforderlich ist, z. B. in Online-Shops.
  • BSTs werden auch verwendet, um den Ausdruck unter Verwendung von Ausdrucksbäumen zu bewerten.

Fazit

Binäre Suchbäume (BST) sind eine Variation des binären Baums und werden im Softwarebereich häufig verwendet. Sie werden auch als geordnete Binärbäume bezeichnet, da jeder Knoten in BST gemäß einer bestimmten Reihenfolge platziert wird.

Durch das Durchlaufen der Reihenfolge von BST erhalten wir die sortierte Reihenfolge der Elemente in aufsteigender Reihenfolge. Wenn BSTs für die Suche verwendet werden, ist dies sehr effizient und innerhalb kürzester Zeit erledigt. BSTs werden auch für eine Vielzahl von Anwendungen wie Huffmans Codierung, mehrstufige Indizierung in Datenbanken usw. verwendet.

=> Lesen Sie hier die beliebte C ++ - Schulungsserie.

Literatur-Empfehlungen

^