Was ist ein binärer Suchbaum?
Der binäre Suchbaum ist ein erweiterter Algorithmus zur Analyse des Knotens, seiner linken und rechten Zweige, die in einer Baumstruktur modelliert sind und den Wert zurückgeben. Das BST basiert auf der Architektur eines grundlegenden binären Suchalgorithmus. Daher ermöglicht es ein schnelleres Nachschlagen, Einfügen und Entfernen von Knoten. Dies macht das Programm sehr schnell und genau.
In diesem Tutorial zur Datenstruktur lernen Sie:
- Was ist ein binärer Suchbaum?
- Attribute des binären Suchbaums
- Warum brauchen wir einen binären Suchbaum?
- Arten von Binärbäumen
- Wie funktioniert der binäre Suchbaum?
- Wichtige Begriffe
Attribute des binären Suchbaums
Eine BST besteht aus mehreren Knoten und besteht aus den folgenden Attributen:
- Knoten des Baums werden in einer Eltern-Kind-Beziehung dargestellt
- Jeder übergeordnete Knoten kann null untergeordnete Knoten oder maximal zwei Unterknoten oder Unterbäume auf der linken und rechten Seite haben.
- Jeder Unterbaum, auch als binärer Suchbaum bezeichnet, 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
- In ähnlicher Weise haben die Schlüssel der linken Teilbaumknoten geringere Werte als die Schlüssel des übergeordneten Knotens.
- Es gibt den Hauptknoten oder die übergeordnete Ebene 11. Darunter befinden sich linke und rechte Knoten / Zweige mit ihren eigenen Schlüsselwerten
- Der rechte Unterbaum hat Schlüsselwerte, die größer als der übergeordnete Knoten sind
- 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 reale Probleme machen, sind Geschwindigkeit und Genauigkeit.
- Aufgrund der Tatsache, dass die binäre Suche in einem verzweigten Format mit Eltern-Kind-Beziehungen vorliegt, weiß der Algorithmus, an welcher Stelle des Baums die Elemente durchsucht werden müssen. Dies verringert die Anzahl der Schlüsselwertvergleiche, die das Programm durchführen muss, um das gewünschte Element zu lokalisieren.
- Wenn das zu durchsuchende Element größer oder kleiner als der übergeordnete Knoten ist, weiß der Knoten außerdem, nach welcher Baumseite gesucht werden soll. Der Grund ist, dass der linke Unterbaum immer kleiner als der übergeordnete Knoten ist und der rechte Unterbaum Werte hat, die immer gleich oder größer als der übergeordnete Knoten sind.
- BST wird häufig verwendet, um komplexe Suchvorgänge, robuste Spielelogiken, Aktivitäten zur automatischen Vervollständigung und Grafiken zu implementieren.
- Der Algorithmus unterstützt effizient Vorgänge 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. In ähnlicher Weise sind alle Knoten voll und lenken ganz nach links.
- Vollständiger Binärbaum: Alle Knoten außer dem Blatt haben 2 untergeordnete Knoten.
- Ausgewogener oder perfekter Binärbaum: Im Baum haben alle Knoten zwei untergeordnete Knoten. Außerdem gibt es für jeden Unterknoten die gleiche Ebene.
Wie funktioniert der binäre Suchbaum?
Der Baum hat immer einen Wurzelknoten und weitere untergeordnete Knoten, ob links oder rechts. Der Algorithmus führt alle Operationen aus, indem er die Werte mit der Wurzel und ihren weiteren untergeordneten Knoten im linken oder rechten Unterbaum entsprechend vergleicht.
Abhängig von dem Element, das nach dem Vergleich eingefügt, gesucht oder gelöscht werden soll, kann der Algorithmus den linken oder rechten Teilbaum des Wurzelknotens leicht löschen.
BST bietet in erster Linie die folgenden drei Arten von Vorgängen für Ihre Verwendung an:
- Suchen: Durchsucht das Element aus dem Binärbaum
- Einfügen: Fügt dem Binärbaum ein Element hinzu
- Löschen: Löscht das Element aus einem Binärbaum
Jede Operation hat ihre eigene Struktur und Methode zur Ausführung / Analyse, aber die komplexeste von allen ist die Löschoperation.
Suchvorgang
Starten Sie die Analyse des Baums immer am Wurzelknoten und bewegen Sie sich dann weiter zum rechten oder linken Teilbaum des Wurzelknotens, je nachdem, welches Element entweder kleiner oder größer als die Wurzel ist.
- Das zu durchsuchende Element ist 10
- Vergleichen Sie das Element mit dem Wurzelknoten 12, 10 <12, und bewegen Sie sich zum linken Teilbaum. Keine Notwendigkeit, den rechten Teilbaum zu analysieren
- Vergleichen Sie nun 10 mit Knoten 7, 10> 7, und gehen Sie zum rechten Teilbaum
- Vergleichen Sie dann 10 mit dem nächsten Knoten, nämlich 9, 10> 9, und schauen Sie in das rechte untergeordnete Teilbaumelement
- 10 stimmt mit dem Wert im Knoten überein, 10 = 10, gibt den Wert an den Benutzer zurück.
Operation einfügen
Dies ist eine sehr einfache Operation. Zuerst wird der Wurzelknoten eingefügt, dann wird der nächste Wert mit dem Wurzelknoten verglichen. Wenn der Wert größer als root ist, wird er dem rechten Teilbaum hinzugefügt, und wenn er kleiner als root ist, wird er dem linken Teilbaum hinzugefügt.
- Es gibt eine Liste von 6 Elementen, die in der Reihenfolge von links nach rechts in eine BST eingefügt werden müssen
- 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
- Vergleichen Sie die verbleibenden Werte 19, 5 und 10 mit dem Wurzelknoten 12 und platzieren Sie sie entsprechend. 19> 12 platzieren Sie es als das rechte Kind von 12, 5 <12 & 5 <7, also platzieren Sie es als linkes Kind von 7.
- Vergleichen Sie nun 10, 10 ist <12 & 10 ist> 7 & 10 ist> 9, platzieren Sie 10 als rechten Teilbaum von 9.
Vorgänge löschen
Löschen ist unter allen anderen Vorgängen die fortschrittlichste und komplexeste. In der BST werden mehrere Fälle zum Löschen behandelt.
- Fall 1 - Knoten mit null Kindern: Dies ist die einfachste Situation. Sie müssen nur den Knoten löschen, der rechts oder links keine weiteren Kinder hat.
- Fall 2 - Knoten mit einem untergeordneten Knoten: Wenn 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 zwei Regeln
- 3a - In Order Predecessor: Sie müssen den Knoten mit zwei untergeordneten Knoten löschen und durch den größten Wert im linken Teilbaum des gelöschten Knotens ersetzen
- 3b - In Order Successor: Sie müssen den Knoten mit zwei untergeordneten Knoten löschen und durch den größten Wert im rechten Teilbaum des gelöschten Knotens ersetzen
- 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.
- Löschen Sie den Wert 19 und entfernen Sie die Verknüpfung vom Knoten.
- Zeigen Sie die neue Struktur des BST ohne 19 an
- Dies ist der zweite Löschfall, bei dem Sie einen Knoten mit 1 Kind löschen, wie Sie in der Abbildung sehen können, dass 9 ein Kind hat.
- Löschen Sie den Knoten 9 und ersetzen Sie ihn durch seinen untergeordneten Knoten 10 und fügen Sie einen Link von 7 bis 10 hinzu
- Zeigen Sie die neue Struktur des BST ohne 9 an
- Hier löschen Sie den Knoten 12, der zwei Kinder hat
- Das Löschen des Knotens erfolgt basierend auf der Vorgängerregel in der Reihenfolge, was bedeutet, dass das größte Element im linken Teilbaum von 12 ihn ersetzt.
- Löschen Sie den Knoten 12 und ersetzen Sie ihn durch 10, da dies der größte Wert im linken Teilbaum ist
- Zeigen Sie die neue Struktur der BST nach dem Löschen von 12 an
- 1 Löschen Sie einen Knoten 12 mit zwei untergeordneten Knoten
- 2 Das Löschen des Knotens erfolgt basierend auf der In Order Orderor-Regel. Dies bedeutet, dass das größte Element im rechten Teilbaum von 12 ihn ersetzt
- 3 Löschen Sie den Knoten 12 und ersetzen Sie ihn durch 19, da dies der größte Wert im rechten Teilbaum ist
- 4 Zeigen Sie die neue Struktur der BST nach dem Löschen von 12 an
Wichtige Begriffe
- Einfügen - Fügt ein Element in einen Baum ein / erstellt einen Baum.
- Suchen - Sucht ein Element in einem Baum.
- Vorbestellungsdurchquerung - Durchläuft einen Baum vorbestellt.
- Inorder Traversal - Durchläuft einen Baum in der richtigen Reihenfolge.
- Nachbestellungsdurchquerung - Durchläuft einen Baum nachträglich.
Zusammenfassung
- BST ist ein Algorithmus für Fortgeschrittene, der verschiedene Operationen basierend auf dem Vergleich von Knotenwerten mit dem Wurzelknoten ausführt.
- Jeder der Punkte in einer Eltern-Kind-Hierarchie repräsentiert den Knoten. Mindestens ein übergeordneter oder Stammknoten bleibt ständig vorhanden.
- Es gibt einen linken 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, eins oder zwei untergeordnete Knoten haben.
- Ein binärer Suchbaum erleichtert primäre Operationen wie Suchen, Einfügen und Löschen.
- Löschen ist am komplexesten und hat mehrere Fälle, z. B. einen Knoten ohne Kind, einen Knoten mit einem Kind und einen Knoten mit zwei Kindern.
- Der Algorithmus wird in realen Lösungen wie Spielen, automatisch vervollständigten Daten und Grafiken verwendet.