Binärer Suchbaum

Kernidee und Zweck

Ein binärer Suchbaum ist in der Informatik eine Kombination aus Suchbaum und Binärbaum. Er wird oft als BST bezeichnet, nach englisch Binary Search Tree. Jeder Knoten trägt einen Schlüssel. Für jeden Knoten gilt die Suchbaum-Eigenschaft: Die Schlüssel im linken Teilbaum sind nur kleiner oder gleich dem Schlüssel des Knotens, die Schlüssel im rechten Teilbaum nur größer oder gleich. Dadurch kann man beim Suchen nach jedem Vergleich entscheiden, ob nur noch links oder nur noch rechts weitergesucht werden muss.

Wozu „kleiner gleich“ und „größer gleich“ genau bedeuten, legt die Anwendung fest. Die Ordnung muss aber eine totale Quasiordnung bilden. Praktisch wird sie oft durch eine 3-Wege-Vergleichsfunktion umgesetzt: Sie liefert ein negatives Ergebnis, wenn x<y gilt, 0, wenn x ein Duplikat von y ist, und ein positives Ergebnis, wenn y<x gilt. Es kann ein einzelnes Schlüsselfeld oder eine Kombination von Feldern verwendet werden; auch ob Duplikate im Baum erlaubt sind, ist eine Entscheidung der Anwendung.

Binäre Suchbäume lösen das Wörterbuchproblem: Zu Schlüsseln werden Werte gespeichert, etwa deutsches Wort zu englischer Übersetzung oder Name und Adresse zu Telefonnummer. Wie bei einem sortierten Wörterbuch kann man die Suche immer wieder auf einen kleineren Bereich einschränken. Bei n Schlüsseln benötigt binäres Suchen im Array maximal ceil(log_2(n+1)) Vergleiche. Im Beispiel mit n=2^20-1=1'048'575 Einträgen braucht sequentielles Suchen im Mittel (n+1)/2=524'288 Vergleiche, binäres Suchen höchstens 20.

Der Vorteil gegenüber einem sortierten Array liegt bei Änderungen: Einfügungen und Löschungen in einem Array können lineare Datentransporte erfordern. Im Baum sind einzelne Elemente als Knoten verbunden, sodass das eigentliche Einfügen oder Freigeben eines Knotens unabhängig von n sein kann. Der Nachteil ist, dass ein Baum seine Balance verlieren kann. Im Extremfall hat jeder Knoten nur ein Kind; dann degeneriert der Baum zu einer linearen Liste, und die Suche verhält sich wie sequentielle Suche.

Aufbau, Begriffe und Ordnung

Ein binärer Suchbaum ist ein gewurzelter gerichteter Baum. Die Wurzel hat Eingangsgrad 0, alle anderen Knoten haben Eingangsgrad 1. Der Ausgangsgrad, also die Anzahl der Kindknoten, ist bei einem Binärbaum höchstens 2. Knoten mit mindestens einem Kind heißen interne oder innere Knoten; Knoten ohne Kind heißen Blätter oder externe Knoten. Ein Knoten mit genau einem Kind wird gelegentlich Halbblatt genannt.

Es gibt unterschiedliche Darstellungen. In einer Sichtweise tragen die vorhandenen Knoten die Schlüssel; fehlende Kinder werden einfach durch einen Nullzeiger dargestellt. In einer anderen Sichtweise gibt es explizite NIL-Knoten als äußere Knoten. Dann tragen nur innere Knoten Schlüssel, während äußere Knoten als Platzhalter für Einfügepunkte dienen. Der schlüssellose Suchbaum besteht in dieser Sichtweise aus genau einem externen Knoten, der zugleich Wurzel ist.

Bei knotenorientierter Speicherung liegen die Inhalte der Menge in den Knoten; externe Blätter sind leer und markieren Einfügepunkte. Bei blattorientierter Speicherung liegen die Inhalte in den Blättern, während innere Knoten nur der Navigation dienen. Der Artikel behandelt vor allem die knotenorientierte Sicht, weil sie gut zur Suche mit einer 3-Wege-Vergleichsfunktion passt.

Wichtig ist die Ordnungsrelation. Sie muss für binäres Suchen und Sortieren eine totale Quasiordnung sein. Die Vergleichsfunktion compare wird nur über ihr Vorzeichen benutzt: sgn(compare(x,y)) ist -1, falls x<y, 0, falls x~y, und +1, falls y<x. Außerdem gilt für alle x,y: sgn(compare(y,x))=-sgn(compare(x,y)). Die induzierte strenge Ordnung < ist eine strenge schwache Ordnung; auf den Äquivalenzklassen der Duplikatrelation entsteht eine strenge Totalordnung. Man kann die Ordnung spiegeln, also +1 und -1 vertauschen; dann werden links und rechts beziehungsweise kleiner und größer vertauscht, die Nachbarschaften bleiben aber erhalten.

Der Begriff „Nachbar“ meint hier nicht eine graphentheoretische Kante, sondern die Ordnung: rechter Nachbar bedeutet nächstes Element in aufsteigender Richtung, linker Nachbar in absteigender Richtung. Die hierarchische Baumform ist dafür zweitrangig; entscheidend ist, dass die in-order-Reihenfolge der Sortierordnung entspricht.

Suchen, Duplikate und Nähe

Die Suche beginnt an der Wurzel. Der Suchschlüssel wird mit dem Schlüssel des aktuellen Knotens verglichen. Bei Gleichheit ist der Eintrag oder ein Duplikat gefunden. Ist der Suchschlüssel kleiner, geht die Suche im linken Teilbaum weiter; ist er größer, im rechten. Fehlt der benötigte Teilbaum, ist der Suchschlüssel nicht vorhanden. Der letzte ungleiche Knoten zusammen mit der letzten Richtung bildet den Einfügepunkt: Dort kann ein neues Element eingefügt werden, ohne die in-order-Reihenfolge zu verletzen.

Wenn keine Duplikate in den Baum aufgenommen werden sollen, kann die Suche beim ersten Gleichheitsfund enden. Der Pseudocode Find gibt dann einen Knoten und ein Vergleichsergebnis zurück. Bei Equal ist der Schlüssel gefunden; bei LessThan, GreaterThan oder Empty beschreibt das Ergebnis einen Einfügepunkt.

Eine iterative Variante nutzt einen Wächterknoten, den Sentinel. Der Sentinel ersetzt fehlende Kindknoten und erspart pro Iterationsschritt eine Abfrage auf Abwesenheit eines Kindes, also bis zu h Abfragen bei Höhe h. Die Funktion FindWithSentinel hat dieselbe Funktionalität wie Find, ist aber so organisiert, dass gefundene echte Knoten und nicht gefundene Einfügepunkte unterschieden werden.

Wenn Duplikate erlaubt sind, ist es oft sinnvoll, nicht beim ersten Treffer stehenzubleiben. Stattdessen kann man bis zu den Blättern weitergehen, um ein neues Duplikat gezielt links oder rechts von vorhandenen Duplikaten einzufügen. FindDupGE sucht so, dass ein neues Duplikat rechts von allen vorhandenen Duplikaten eingefügt würde; eine gespiegelte Variante FindDupLE würde links einfügen. FindDup kombiniert zwei Aufgaben: Es meldet, ob ein Suchschlüssel vorhanden ist, und liefert zugleich einen Einfügepunkt für ein mögliches Duplikat. Dazu wird ein Cursor verwendet, also ein Objekt, das Knoten, Richtung und gegebenenfalls den Pfad zur Wurzel enthält.

Mit einer Einzelschritt-Traversierung kann jede Suchfunktion zu einer Proximitäts-Suche erweitert werden. Das bedeutet eine Suche in der Nähe eines Schlüssels, etwa nach dem kleinsten Element, das größer gleich einem Suchschlüssel ist. Liefert die Suche im ungleichen Fall einen Einfügepunkt, dann enthält dieser bereits einen Nachbarn; falls nötig geht man mit der Traversierung einen Schritt in aufsteigender oder absteigender Richtung weiter.

Einfügen, Löschen und Traversieren

Beim Einfügen wird vorausgesetzt, dass der Einfügepunkt schon gefunden wurde. Ein unmittelbarer Einfügepunkt besteht aus einem Knoten und einer Richtung, also links oder rechts. Der entsprechende Kindzeiger fehlt dort. Die Einfügeoperation lässt diesen Kindzeiger auf das neue Element zeigen; damit ist das neue Element korrekt gemäß der totalen Quasiordnung eingefügt. Ohne vorherige Suche ist die Komplexität des Einfügens konstant. Mit Suche wird die Laufzeit von der Suchoperation bestimmt. Nach dem Einfügen ist das neue Element ein Blatt. Werden sortierte Schlüssel wiederholt aufsteigend oder absteigend eingefügt, kann der Baum zu einer linearen Liste entarten.

Beim Löschen wird die in-order-Reihenfolge erhalten. Hat der zu löschende Knoten D kein Kind oder nur ein Kind F, wird F an die Stelle von D gesetzt; war D die Wurzel, wird F neue Wurzel. Hat D zwei Kinder, wird im rechten Teilbaum der linkeste Knoten E gesucht. E ist der in-order-Nachfolger von D und kann kein linkes Kind haben. Schlüssel und Daten von E werden nach D kopiert; anschließend wird E durch sein rechtes Kind F ersetzt, falls ein solches existiert. Diese von T. Hibbard 1962 vorgeschlagene Vorgehensweise hält Änderungen an den Höhen der Teilbäume gering. Im schlechtesten Fall hat Löschen wegen notwendiger Abstiege bis zu Halbblättern die Komplexität O(h), wobei h die Höhe des Baums ist. Bei zugelassenen Duplikaten schlägt Mehlhorn vor, Elemente mit gleichem Schlüssel nach Last In – First Out zu entfernen.

Traversierung bedeutet das systematische Durchlaufen der Knoten. Für binäre Suchbäume sind in-order- und reverse-in-order-Traversierungen besonders wichtig, weil sie die gespeicherte Ordnung in aufsteigender oder absteigender Richtung liefern. Eine ganze Traversierung über den Baum umfasst pro Kante einen Abstieg und einen Aufstieg; bei n Knoten ist der Aufwand 2n in Theta(n). Eine Einzelschritt-Traversierung Next liefert vom aktuellen Knoten aus das nächste Element in gewünschter Richtung. Im Mittel und amortisiert ist sie konstant, im schlechtesten Fall O(h). Ohne Elterzeiger muss der Cursor den Pfad zur Wurzel in einem Stack speichern; mit Elterzeigern ist der Cursor einfacher, kostet aber zusätzlichen Speicher pro Knoten.

Komplexität und Pfadlängen

Die Suchzeit hängt von der Höhe h des Baums ab, weil die Suche einem Pfad von der Wurzel zu einem Blatt folgt. Im Mittel und im schlechtesten Fall gilt O(h). Im besten Fall ist Find konstant, wenn die Wurzel direkt passt; FindDupGE und FindDup bleiben jedoch O(h), weil sie bis zum Einfügepunkt weiterlaufen.

Im entarteten Fall ist h so groß wie die Anzahl n der Elemente. Beim Aufbau eines solchen Baums kann im Extremfall jedes Element mit jedem verglichen werden; insgesamt entstehen binom(n,2) Vergleiche, also O(n^2). Höhenbalancierte Suchbäume haben dagegen Höhe O(log n) und ermöglichen garantiert logarithmische Suche. Ihr Aufbau benötigt O(n log n) Vergleiche, was den besten Sortieralgorithmen entspricht. Zufällig erzeugte Suchbäume haben im Durchschnitt ebenfalls logarithmische Höhe, wenn alle Permutationen der Einfügungen und Löschungen gleich wahrscheinlich sind und Löschungen nicht dauerhaft asymmetrisch nach einer Seite erfolgen.

Für genauere Kosten betrachtet der Artikel Suchtiefen und Pfadlängensummen. Sei X={x_1<x_2<...<x_n} eine Schlüsselmenge. Zugriffshäufigkeiten p_i gehören zu erfolgreichen Suchen nach x_i, Häufigkeiten q_j zu erfolglosen Suchen in den Intervallen zwischen x_j und x_{j+1}, mit x_0=-infty und x_{n+1}=+infty. Die gewichtete Pfadlängensumme eines Baums T ist S_z^T=sum_{i=1}^n p_i(a_i^T+1)+sum_{j=0}^n q_j b_j^T, wobei a_i^T die Tiefe eines inneren Knotens und b_j^T die Tiefe eines externen Blattes ist. Ist die Zugriffsverteilung eine Wahrscheinlichkeitsverteilung, dann ist S_z^T die mittlere Anzahl benötigter Vergleiche.

Für erfolgreiche Suche mit p_i=1 und q_j=0 ist S_e^T die Summe der Vergleiche für alle n Knoten; die interne Pfadlänge ist I=S_e^T-n. Für alle binären Suchbäume gilt S_e-Untergrenze(n) <= S_e^T <= n(n+1)/2. Die obere Grenze stammt von der linearen Kette, die untere von vollständig balancierten Bäumen. Ist k in N mit 2^{k-1} <= n+1 <= 2^k, dann gilt für die Untergrenze: S_e-Untergrenze(n)=1+(n+1)k-2^k. Für erfolglose Suche mit p_i=0 und q_j=1 heißt S_f^T externe Pfadlänge E. Es gilt S_f^T=S_e^T+n und damit S_f-Untergrenze(n) <= S_f^T <= n(n+3)/2.

Implementierung, Anwendungen und Auswahl

Eine typische Implementierung speichert pro Knoten einen Schlüssel sowie Zeiger auf linkes und rechtes Kind. Ein Zeigerwert 0 kann bedeuten, dass kein Kind existiert. Zusätzlich gibt es einen Kopf, der den Zeiger auf die Wurzel enthält und als eine Art Elter der Wurzel dient. Das ist nötig, weil die Wurzel durch Löschung oder Rotation wechseln kann und den Baum daher nicht dauerhaft identifizieren sollte.

Operationen werden oft rekursiv dargestellt, können aber iterativ implementiert werden. Iteration spart bis zu h Prozeduraufrufe und hält den Programmstapel konstant. Für Traversierung und manche Modifikationen muss der Rückweg zur Wurzel dann explizit gespeichert werden, etwa im Cursor. Der Artikel betont die Trennung von Navigation und Modifikation: Suchen, Traversieren oder ein zweiter Zugriffspfad können erst einen Cursor liefern; Einfügen oder Löschen verwenden diesen dann. Das kann besonders bei Anwendungen mit vielen sequentiellen Schritten Laufzeit sparen.

Cursor bestehen mindestens aus Knoten und Richtung. Wenn jeder Knoten einen Elterzeiger hat, reicht dieses Paar als vollwertiger Cursor. Ohne Elterzeiger muss zusätzlich der Pfad zur Wurzel in einem Stack im Cursor liegen. Elterzeiger erhöhen den Speicherbedarf, sparen aber bei Rückwegen Laufzeit. Bei mehreren Cursorn über Änderungen hinweg kann es wirtschaftlicher sein, Elterzeiger zu verwenden.

Ein Beispiel für mehrere Zugriffspfade ist Speichermanagement mit freien Speicherblöcken, die nach Ort und Größe gesucht werden. Für Ort sind Duplikate ausgeschlossen; für Größe sind sie unvermeidlich, daher bietet sich ein zusammengesetzter Schlüssel (Größe,Ort) an. Beim Anfordern wird ein Block passender Mindestgröße gesucht, entfernt und ein Rest wieder eingetragen. Bei Rückgabe wird nach Ort gesucht, Nachbarblöcke werden auf Konfliktfreiheit geprüft und gegebenenfalls verschmolzen.

Anwendungen dynamischer Suchbaumstrukturen sind unter anderem Duplikatunterdrückung, Deduplikation, Duplikaterkennung, elementare Mengenoperationen wie Durchschnitt und Vereinigung, die Standard Template Library, Verwaltung von Virtual Memory Areas, eindeutige Kennzeichnung von IP-Paketen, Variablenlisten in Interpretern oder Compilern sowie Binary Tree Sort. Für Massen- und Mengenoperationen können selbst-balancierende Binärbäume über eine JOIN-Operation verkettet werden; entsprechende parallele Algorithmen sind als PAM in C++ verfügbar.

Bei der Auswahl kommt es darauf an, ob die Daten statisch oder dynamisch sind. Binäres Suchen im Array ist für statische, vorsortierte Tabellen sehr gut, verhält sich bei Einfügungen und Löschungen aber linear. Für dynamische Daten sind binäre Suchbäume geeigneter, sofern Balance gewährleistet wird. AVL-Bäume, Rot-Schwarz-Bäume und Splay-Bäume sind wichtige Varianten. Ein vollständig balancierter Baum ist oft zu teuer im Unterhalt; höhenbalancierte Bäume bieten einen praktischen Kompromiss. Wenn Zugriffe auf externe Medien wichtig sind, gelten andere Kriterien; der B-Baum berücksichtigt solche Speicherhierarchien, ist aber nicht binär.