Binärer Suchbaum (BST) mit Beispiel

Was ist ein binärer Suchbaum?

Der binäre Suchbaum ist ein fortgeschrittener Algorithmus, der zur Analyse des Knotens und seiner linken und rechten Zweige verwendet wird, die in einer Baumstruktur modelliert sind und den Wert zurückgeben. Der BST basiert auf der Architektur eines grundlegenden binären Suchalgorithmus und ermöglicht daher schnellere Nachschlagevorgänge, Einfügungen und Entfernungen von Knoten. Dies macht das Programm wirklich schnell und genau.

Attribute des binären Suchbaums

Ein BST besteht aus mehreren Knoten und umfasst die folgenden Attribute:

  • Knoten des Baums werden in einer Eltern-Kind-Beziehung dargestellt
  • Jeder übergeordnete Knoten kann null untergeordnete Knoten oder maximal zwei Unterknoten oder Teilbäume auf der linken und rechten Seite haben.
  • Jeder Unterbaum, auch binärer Suchbaum genannt, hat rechts und links von sich Unterzweige.
  • Alle Knoten sind mit Schlüssel-Wert-Paaren verknüpft.
  • Die Schlüssel der im linken Teilbaum vorhandenen Knoten sind kleiner als die Schlüssel ihres übergeordneten Knotens
  • Ebenso haben die Schlüssel der linken Teilbaumknoten kleinere Werte als die Schlüssel ihrer übergeordneten Knoten.

Attribute des binären Suchbaums

  1. Es gibt den Hauptknoten oder übergeordnete Ebene 11. Darunter befinden sich linke und rechte Knoten/Zweige mit eigenen Schlüsselwerten
  2. Der rechte Unterbaum hat Schlüsselwerte, die größer sind als die des übergeordneten Knotens
  3. Der linke Unterbaum hat Werte als der übergeordnete Knoten

Warum brauchen wir einen binären Suchbaum?

  • Die beiden Hauptfaktoren, die den binären Suchbaum zu einer optimalen Lösung für alle realen Probleme machen, sind Geschwindigkeit und Genauigkeit.
  • Aufgrund der Tatsache, dass die binäre Suche in einem verzweigten Format mit Eltern-Kind-Beziehungen erfolgt, weiß der Algorithmus, an welcher Stelle des Baums nach den Elementen gesucht werden muss. Dadurch verringert sich die Anzahl der Schlüsselwertvergleiche, die das Programm durchführen muss, um das gewünschte Element zu finden.
  • Falls das zu durchsuchende Element größer oder kleiner als der übergeordnete Knoten ist, weiß der Knoten außerdem, nach welcher Baumseite er suchen muss. Der Grund dafür ist, dass der linke Unterbaum immer kleiner als der übergeordnete Knoten ist und der rechte Unterbaum immer Werte aufweist, die gleich oder größer als die des übergeordneten Knotens sind.
  • BST wird häufig verwendet, um komplexe Suchvorgänge, robuste Spiellogiken, Auto-Vervollständigungsaktivitäten und Grafiken zu implementieren.
  • Der Algorithmus unterstützt effizient Operationen wie Suchen, Einfügen und Löschen.

Arten von Binärbäumen

Drei Arten von Binärbäumen sind:

  • Vollständiger Binärbaum: Alle Ebenen in den Bäumen sind voll von möglichen Ausnahmen der letzten Ebene. Ebenso sind alle Knoten voll und zeigen ganz nach links.
  • Vollständiger Binärbaum: Alle Knoten haben zwei untergeordnete Knoten außer dem Blatt.
  • Ausgeglichener oder perfekter Binärbaum: Im Baum haben alle Knoten zwei untergeordnete Knoten. Außerdem gibt es für jeden Unterknoten die gleiche Ebene.

Erfahren Sie mehr darüber Binärbaum in der Datenstruktur wenn Sie interessiert sind.

Wie funktioniert der binäre Suchbaum?

Der Baum hat immer einen Wurzelknoten und weitere untergeordnete Knoten, egal ob links oder rechts. Der Algorithmus führt alle Operationen durch, indem er Werte mit der Wurzel und ihren weiteren untergeordneten Knoten im linken oder rechten Teilbaum vergleicht.

Abhängig vom Element, das eingefügt, gesucht oder gelöscht werden soll, kann der Algorithmus nach dem Vergleich problemlos den linken oder rechten Teilbaum des Wurzelknotens löschen.

BST bietet Ihnen im Wesentlichen die folgenden drei Betriebsarten zur Nutzung an:

  • Suchen: Sucht das Element im Binärbaum
  • Einfügen: Fügt ein Element zum Binärbaum hinzu
  • Löschen: Element aus einem Binärbaum löschen

Jeder Vorgang verfügt über eine eigene Struktur und Ausführungs-/Analysemethode, der komplexeste von allen ist jedoch der Löschvorgang.

Suche OperaProduktion

Starten Sie die Analyse des Baums immer am Wurzelknoten und gehen Sie dann weiter zum rechten oder linken Teilbaum des Wurzelknotens, je nachdem, ob das zu lokalisierende Element kleiner oder größer als die Wurzel ist.

Suche OperaProduktion

  1. Das zu durchsuchende Element ist 10
  2. Vergleichen Sie das Element mit dem Wurzelknoten 12, 10 < 12, Sie gelangen also in den linken Teilbaum. Der rechte Teilbaum muss nicht analysiert werden
  3. Vergleichen Sie nun 10 mit Knoten 7, 10 > 7, gehen Sie also zum rechten Teilbaum
  4. Vergleichen Sie dann 10 mit dem nächsten Knoten, der 9 ist, 10 > 9, und schauen Sie im rechten Unterbaum nach
  5. 10 Übereinstimmungen mit dem Wert im Knoten, 10 = 10, geben den Wert an den Benutzer zurück.

Pseudocode für die Suche in BST

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

Insert OperaProduktion

Dies ist eine sehr einfache Operation. Zuerst wird der Stammknoten eingefügt, dann wird der nächste Wert mit dem Stammknoten verglichen. Wenn der Wert größer als der Stammknoten ist, wird er dem rechten Teilbaum hinzugefügt, und wenn er kleiner als der Stammknoten ist, wird er dem linken Teilbaum hinzugefügt.

Insert OperaProduktion

  1. Es gibt eine Liste von 6 Elementen, die in der Reihenfolge von links nach rechts in ein BST eingefügt werden müssen
  2. Fügen Sie 12 als Wurzelknoten ein und vergleichen Sie die nächsten Werte 7 und 9, um sie entsprechend in den rechten und linken Teilbaum einzufügen
  3. Vergleichen Sie die verbleibenden Werte 19, 5 und 10 mit dem Wurzelknoten 12 und platzieren Sie sie entsprechend. 19 > 12 Platziere es als rechtes Kind von 12, 5 < 12 & 5 < 7, also als linkes Kind von 7. Vergleiche nun 10, 10 ist < 12 & 10 ist > 7 & 10 ist > 9, Platziere 10 als rechter Teilbaum von 9.

Pseudocode zum Einfügen eines Knotens in BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Löschen Operations

Für das Löschen eines Knotens aus einem BST gibt es einige Fälle, z. B. das Löschen eines Stammknotens oder das Löschen eines Blattknotens. Außerdem müssen wir nach dem Löschen eines Stammknotens über den Stammknoten nachdenken.

Angenommen, wir möchten einen Blattknoten löschen. Dann können wir ihn einfach löschen. Wenn wir jedoch eine Wurzel löschen möchten, müssen wir den Wert der Wurzel durch einen anderen Knoten ersetzen. Nehmen wir das folgende Beispiel:

  • Fall 1 – Knoten ohne untergeordnete Knoten: Dies ist die einfachste Situation. Sie müssen lediglich den Knoten löschen, der rechts oder links keine weiteren untergeordneten Knoten hat.
  • Fall 2 – Knoten mit einem untergeordneten Knoten: Sobald Sie den Knoten gelöscht haben, verbinden Sie einfach seinen untergeordneten Knoten mit dem übergeordneten Knoten des gelöschten Werts.
  • Fall 3 Knoten mit zwei Kindern: Dies ist die schwierigste Situation und funktioniert nach den folgenden beiden Regeln
  • 3a – In der Reihenfolge Vorgänger: Sie müssen den Knoten mit zwei untergeordneten Knoten löschen und ihn durch den größten Wert im linken Teilbaum des gelöschten Knotens ersetzen
  • 3b – In der Reihenfolge Nachfolger: Sie müssen den Knoten mit zwei untergeordneten Knoten löschen und ihn durch den größten Wert im rechten Teilbaum des gelöschten Knotens ersetzen

Löschen Operations

  1. Dies ist der erste Löschfall, bei dem Sie einen Knoten löschen, der keine untergeordneten Knoten hat. Wie Sie im Diagramm sehen können, haben 19, 10 und 5 keine Kinder. Aber wir werden 19 löschen.
  2. Löschen Sie den Wert 19 und entfernen Sie den Link vom Knoten.
  3. Sehen Sie sich die neue Struktur des BST ohne 19 an

Löschen Operations

  1. Dies ist der zweite Löschfall, bei dem Sie einen Knoten löschen, der 1 Kind hat, wie Sie im Diagramm sehen können, dass 9 ein Kind hat.
  2. Löschen Sie den Knoten 9, ersetzen Sie ihn durch seinen untergeordneten Knoten 10 und fügen Sie einen Link von 7 zu 10 hinzu
  3. Sehen Sie sich die neue Struktur des BST ohne 9 an

Löschen Operations

  1. Hier löschen Sie den Knoten 12, der zwei untergeordnete Elemente hat
  2. Das Löschen des Knotens erfolgt auf der Grundlage der Vorgängerregel in der Reihenfolge, was bedeutet, dass das größte Element im linken Teilbaum von 12 ihn ersetzt.
  3. Löschen Sie den Knoten 12 und ersetzen Sie ihn durch 10, da dies der größte Wert im linken Teilbaum ist
  4. Sehen Sie sich die neue Struktur des BST nach dem Löschen von 12 an

Löschen Operations

  1. 1 Löschen Sie einen Knoten 12, der zwei untergeordnete Knoten hat
  2. 2 Das Löschen des Knotens erfolgt auf Grundlage der In-Order-Nachfolger-Regel, was bedeutet, dass das größte Element im rechten Teilbaum von 12 ihn ersetzt
  3. 3 Löschen Sie den Knoten 12 und ersetzen Sie ihn durch 19, da dies der größte Wert im rechten Teilbaum ist
  4. 4 Sehen Sie sich die neue Struktur des BST nach dem Löschen von 12 an

Pseudocode zum Löschen eines Knotens

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Wichtige Begriffe

  • Einfügen: Fügt ein Element in einen Baum ein bzw. erstellt einen Baum.
  • Suchen: Durchsucht ein Element in einem Baum.
  • Durchquerung vorbestellt: Durchquert einen Baum auf vorbestellte Weise.
  • Inorder Traversal: Durchläuft einen Baum in der richtigen Reihenfolge.
  • Postorder-Traversal: Durchläuft einen Baum nachträglich.

Zusammenfassung

  • BST ist ein Algorithmus auf fortgeschrittenem Niveau, der verschiedene Operationen basierend auf dem Vergleich von Knotenwerten mit dem Stammknoten ausführt.
  • Jeder Punkt in einer Eltern-Kind-Hierarchie stellt den Knoten dar. Mindestens ein übergeordneter oder Wurzelknoten bleibt ständig vorhanden.
  • Es gibt einen linken Teilbaum und einen rechten Teilbaum. Der linke Teilbaum enthält Werte, die kleiner als der Wurzelknoten sind. Der rechte Teilbaum enthält jedoch einen Wert, der größer als der Wurzelknoten ist.
  • Jeder Knoten kann entweder null, ein oder zwei Kinder haben.
  • Ein binärer Suchbaum erleichtert grundlegende Operationen wie Suchen, Einfügen und Löschen.
  • Beim Löschen handelt es sich um den komplexesten Knoten, der mehrere Fälle umfasst, z. B. einen Knoten ohne untergeordnetes Element, einen Knoten mit einem untergeordneten Element und einen Knoten mit zwei untergeordneten Elementen.
  • Der Algorithmus wird in realen Lösungen wie Spielen, Autovervollständigungsdaten und Grafiken verwendet.