Binäre Suchbäume unterstützen drei Hauptoperationen: Einfügen von Elementen, Löschen von Elementen und Suchen (Überprüfen, ob ein Schlüssel vorhanden ist).

SearchingEdit

Die Suche in einem binären Suchbaum nach einem bestimmten Schlüssel kann rekursiv oder iterativ programmiert werden.

Wir beginnen mit der Untersuchung des Wurzelknotens. Wenn der Baum null ist, ist der gesuchte Schlüssel nicht im Baum vorhanden. Andernfalls, wenn der Schlüssel dem der Wurzel entspricht, ist die Suche erfolgreich und wir geben den Knoten zurück. Wenn der Schlüssel kleiner als der der Wurzel ist, suchen wir den linken Teilbaum., Wenn der Schlüssel größer als der der Wurzel ist, suchen wir in ähnlicher Weise den richtigen Teilbaum. Dieser Vorgang wird wiederholt, bis der Schlüssel gefunden wurde oder der verbleibende Teilbaum null ist. Wenn der gesuchte Schlüssel nach Erreichen eines Null-Teilbaums nicht gefunden wird, ist der Schlüssel nicht im Baum vorhanden. Dies wird leicht als rekursiver Algorithmus ausgedrückt (in Python implementiert):

Derselbe Algorithmus kann iterativ implementiert werden:

Diese beiden Beispiele unterstützen keine Duplikate, dh sie verlassen sich darauf, dass die Auftragsbeziehung eine Gesamtreihenfolge ist.

Man kann feststellen, dass der rekursive Algorithmus Schwanz rekursiv ist., In einer Sprache, die die Tail Call-Optimierung unterstützt, werden die rekursiven und iterativen Beispiele in äquivalente Programme kompiliert.

Da dieser Algorithmus im schlimmsten Fall von der Baumwurzel bis zum am weitesten von der Wurzel entfernten Blatt suchen muss, dauert die Suchoperation proportional zur Baumhöhe (siehe Baumterminologie). Im Durchschnitt haben binäre Suchbäume mit Knotentasten eine Höhe von O(log |Nodes|). Im schlimmsten Fall können binäre Suchbäume jedoch eine Höhe von O(|Nodes|) haben, wenn der unausgeglichene Baum einer verknüpften Liste (degenerierter Baum) ähnelt.,

Suche mit Duplikaten allowedEdit

Wenn die Auftragsbeziehung nur eine vollständige Vorbestellung ist, ist eine vernünftige Erweiterung der Funktionalität die folgende: auch im Falle einer Suche bis zum Ende. Dadurch kann eine Richtung angegeben (oder fest verdrahtet) werden, in die ein Duplikat eingefügt werden soll, entweder rechts oder links von allen Duplikaten im Baum. Wenn die Richtung fest verdrahtet ist, unterstützen beide Optionen, rechts und links, einen Stapel mit insert duplicate als Push-Operation und delete als Pop-Operation.,:155

Eine mit einer solchen Suchfunktion ausgestattete binäre Baumsortierung wird stabil.

InsertionEdit

Das Einfügen beginnt, wenn eine Suche beginnen würde; Wenn der Schlüssel nicht gleich dem der Wurzel ist, suchen wir die linken oder rechten Teilbäume wie zuvor. Schließlich erreichen wir einen externen Knoten und fügen das neue Schlüssel-Wert-Paar (hier als Datensatz ’newNode‘ codiert) als rechtes oder linkes untergeordnetes Element hinzu, abhängig vom Schlüssel des Knotens., Mit anderen Worten, wir untersuchen die Wurzel und fügen den neuen Knoten rekursiv in den linken Teilbaum ein, wenn sein Schlüssel kleiner als der des Stammes ist, oder den rechten Teilbaum, wenn sein Schlüssel größer oder gleich dem Stamm ist.

So kann eine typische binäre Suchbaumeinfügung in einem Binärbaum in C++durchgeführt werden:

Alternativ kann eine nicht rekursive Version wie folgt implementiert werden., Durch die Verwendung eines Zeigers-zu-Zeigers, um zu verfolgen, woher wir stammen, kann der Code eine explizite Überprüfung und Behandlung des Falls vermeiden, in dem ein Knoten an der Baumwurzel eingefügt werden muss:

Die obige destruktive prozedurale Variante ändert den Baum an Ort und Stelle. Es verwendet nur konstanten Heap-Speicherplatz (und die iterative Version verwendet auch konstanten Stack-Speicherplatz), aber die vorherige Version des Baums geht verloren., Alternativ können wir, wie im folgenden Python-Beispiel, alle Vorfahren des eingefügten Knotens rekonstruieren; Jeder Verweis auf die ursprüngliche Baumwurzel bleibt gültig, wodurch der Baum zu einer persistenten Datenstruktur wird:

Der Teil, der neu erstellt wird, verwendet im Durchschnitt O(log n) und im schlimmsten Fall O(n).

In beiden Versionen erfordert dieser Vorgang eine Zeit, die im schlimmsten Fall proportional zur Höhe des Baumes ist, dh O(log n) Zeit im Durchschnitt über alle Bäume, im schlimmsten Fall jedoch O(n) Zeit.,

Eine andere Möglichkeit, das Einfügen zu erklären, besteht darin, dass zum Einfügen eines neuen Knotens in den Baum zuerst sein Schlüssel mit dem des Stammes verglichen wird. Wenn der Schlüssel kleiner als der root ist, wird er mit dem Schlüssel des linken untergeordneten Elements des root verglichen. Wenn der Schlüssel größer ist, wird er mit dem rechten untergeordneten Element der Wurzel verglichen. Dieser Vorgang wird fortgesetzt, bis der neue Knoten mit einem Blattknoten verglichen wird, und dann wird er je nach Schlüssel als rechtes oder linkes Kind dieses Knotens hinzugefügt: Wenn der Schlüssel kleiner als der Schlüssel des Blattes ist, wird er als linkes Kind des Blattes eingefügt, andernfalls als rechtes Kind des Blattes.,

Es gibt andere Möglichkeiten, Knoten in einen Binärbaum einzufügen, aber dies ist die einzige Möglichkeit, Knoten an den Blättern einzufügen und gleichzeitig die BST-Struktur beizubehalten.

DeletionEdit

Beim Entfernen eines Knotens aus einem binären Suchbaum muss die Reihenfolge der Knoten in der Reihenfolge beibehalten werden. Es gibt viele Möglichkeiten, dies zu tun. Die folgende Methode, die 1962 von T. Hibbard vorgeschlagen wurde, garantiert jedoch, dass die Höhen der Subjekt-Teilbäume höchstens um eine geändert werden., Es gibt drei mögliche Fälle zu berücksichtigen:

• Löschen eines Knotens ohne untergeordnete Elemente: Entfernen Sie einfach den Knoten aus dem Baum.
• Löschen eines Knotens mit einem Kind: Entfernen Sie den Knoten und ersetzen Sie ihn durch sein Kind.
• Löschen eines Knotens D mit zwei untergeordneten Elementen: Wählen Sie entweder den In-Order-Vorgänger von D oder den In-Order-Nachfolger von E (siehe Abbildung). Anstatt D zu löschen, überschreiben Sie seinen Schlüssel und Wert mit E ’s. Wenn E kein Kind hat, entfernen Sie E von seinem vorherigen Elternteil G. Wenn E ein Kind F hat, ist es ein richtiges Kind, so dass es E bei E‘ s Elternteil ersetzen soll. ,

Wenn D zufällig die Wurzel ist, machen Sie den Ersatzknoten erneut zur Wurzel.

Knoten mit zwei untergeordneten Elementen sind schwieriger zu löschen., Der In-Order-Nachfolger eines Knotens ist das am weitesten links liegende Kind seines rechten Teilbaums, und der In-Order-Vorgänger eines Knotens ist das am weitesten rechts stehende Kind des linken Teilbaums. In beiden Fällen hat dieser Knoten nur ein oder gar kein Kind. Löschen Sie es gemäß einem der beiden oben genannten einfacheren Fälle.

Die konsistente Verwendung des In-Order-Nachfolgers oder des In-Order-Vorgängers für jede Instanz des Zwei-Kind-Falls kann zu einem unausgeglichenen Baum führen, sodass einige Implementierungen den einen oder anderen zu unterschiedlichen Zeiten auswählen.,

Laufzeitanalyse: Obwohl diese Operation den Baum nicht immer bis zu einem Blatt durchquert, ist dies immer eine Möglichkeit; Im schlimmsten Fall benötigt sie Zeit proportional zur Höhe des Baumes. Es erfordert nicht mehr, auch wenn der Knoten zwei untergeordnete Elemente hat, da er immer noch einem einzelnen Pfad folgt und keinen Knoten zweimal besucht.,

TraversalEdit

Sobald der binäre Suchbaum erstellt wurde, können seine Elemente in der Reihenfolge abgerufen werden, indem der linke Teilbaum des Stammknotens rekursiv durchlaufen wird, auf den Knoten selbst zugegriffen wird, dann rekursiv den rechten Teilbaum des Knotens durchläuft und dieses Muster mit jedem Knoten im Baum fortsetzt, während rekursiv auf ihn zugegriffen wird. Wie bei allen Binärbäumen kann man eine Durchquerung vor oder nach der Durchquerung durchführen, aber keine ist wahrscheinlich für binäre Suchbäume nützlich., Eine Durchquerung eines binären Suchbaums in der Reihenfolge führt immer zu einer sortierten Liste von Knotenelementen (Zahlen, Zeichenfolgen oder andere vergleichbare Elemente).

Der code für in-order traversal Python ist unten angegeben. Es ruft einen Rückruf (eine Funktion, die der Programmierer für den Wert des Knotens aufrufen möchte, z. B. Drucken auf dem Bildschirm) für jeden Knoten im Baum auf.

Traversal erfordert O (n) Zeit, da es jeden Knoten besuchen muss. Dieser Algorithmus ist auch O (n), daher ist er asymptotisch optimal.

Traversal kann auch iterativ implementiert werden. Für bestimmte Anwendungen, z.B., größere gleich Suche, approximative Suche, eine Operation für einzelne Schritt (iterative) Traversal kann sehr nützlich sein. Dies wird natürlich ohne das Callback-Konstrukt implementiert und benötigt im Durchschnitt O(1) und im schlimmsten Fall O(log n).

VerificationEdit

Manchmal haben wir bereits einen Binärbaum und müssen feststellen, ob es sich um eine BST handelt. Dieses problem hat eine einfache rekursive Lösung.,

Die BST-Eigenschaft—jeder Knoten im rechten Teilbaum muss größer als der aktuelle Knoten und jeder Knoten im linken Teilbaum muss kleiner als der aktuelle Knoten sein—ist der Schlüssel, um herauszufinden, ob ein Baum ein BST ist oder nicht. Der gierige Algorithmus-durchquere einfach den Baum, überprüfe bei jedem Knoten, ob der Knoten einen Wert enthält, der größer als der Wert am linken Kind und kleiner als der Wert am rechten Kind ist-funktioniert nicht für alle Fälle., Betrachten Sie den folgenden Baum:

 20 / \ 10 30 / \ 5 40

In der obigen Baumstruktur erfüllt jeder Knoten die Bedingung, dass der Knoten einen Wert enthält, der größer als sein linkes Kind und kleiner als sein rechtes Kind ist, und dennoch ist es kein BST: Der Wert 5 befindet sich im rechten Teilbaum des Knotens, der 20 enthält, eine Verletzung der BST-Eigenschaft.

Anstatt eine Entscheidung zu treffen, die ausschließlich auf den Werten eines Knotens und seiner untergeordneten Elemente basiert, benötigen wir auch Informationen, die vom übergeordneten Knoten herunterfließen., Wenn wir uns im Fall des obigen Baums an den Knoten erinnern könnten, der den Wert 20 enthält, würden wir sehen, dass der Knoten mit dem Wert 5 gegen den BST-Eigenschaftenvertrag verstößt.,

Die Bedingung, die wir also an jedem Knoten überprüfen müssen, ist:

• wenn der Knoten das linke Kind seines Elternteils ist, muss er kleiner (oder gleich) sein Elternteil und es muss den Wert von seinem Elternteil an seinen rechten Teilbaum weitergeben, um sicherzustellen, dass keiner der Knoten in diesem Teilbaum größer ist als das Elternteil
• Wenn der Knoten das rechte Kind seines Elternteils ist, muss er größer als das Elternteil sein und den Wert von seinem Elternteil an seinen linken Teilbaum stellen Sie sicher, dass keiner der Knoten in diesem Teilbaum kleiner als der übergeordnete ist.,

Eine rekursive Lösung in C++ kann dies weiter erklären:

node->key+1 und node->key-1 erlauben nur unterschiedliche Elemente in BST.

Wenn dieselben Elemente ebenfalls vorhanden sein sollen, können wir an beiden Stellen nur node->key.

Der erste Aufruf dieser Funktion kann ungefähr so lauten:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

Im Wesentlichen erstellen wir weiterhin einen gültigen Bereich (beginnend mit) und verkleinern ihn für jeden Knoten, während wir rekursiv nach unten gehen.,

Wie in Abschnitt #Traversal gezeigt, gibt eine In-Order-Durchquerung eines binären Suchbaums die sortierten Knoten zurück. Daher müssen wir nur den zuletzt besuchten Knoten behalten, während wir den Baum durchqueren, und prüfen, ob sein Schlüssel kleiner (oder kleiner/gleich, wenn Duplikate im Baum erlaubt sein sollen) im Vergleich zum aktuellen Schlüssel ist.

Parallele Algorithmenedit

Es gibt auch parallele Algorithmen für binäre Suchbäume, einschließlich Einfügen/Löschen mehrerer Elemente, Konstruktion aus Array, Filtern mit bestimmten Prädikaten, Abflachen zu einem Array, Zusammenführen/Teilzeichenfolgen / Schneiden von zwei Bäumen usw., Diese Algorithmen können mithilfe von Join-basierten Baumalgorithmen implementiert werden, die den Baum auch mithilfe mehrerer Ausgleichsschemata (einschließlich AVL-Baum, rot-schwarzer Baum, Gewichtsausgleichsbaum und Treap) ausgeglichen halten können .