In der Informatik ist ein binärer Suchbaum eine Kombination der abstrakten Datenstrukturen Suchbaum und Binärbaum. Ein binärer Suchbaum, häufig abgekürzt als BST (von englisch Binary Search Tree), ist ein binärer Baum, bei dem die Knoten „Schlüssel“ tragen, und die Schlüssel des linken Teilbaums eines Knotens nur kleiner (oder gleich) und die des rechten Teilbaums nur größer (oder gleich) als der Schlüssel des Knotens selbst sind.
Was die Begriffe „kleiner gleich“ und „größer gleich“ bedeuten, ist völlig dem Anwender überlassen; sie müssen nur eine Totalordnung (genauer: eine totale Quasiordnung siehe unten) etablieren. Am flexibelsten wird die Ordnungsrelation durch eine vom Anwender zur Verfügung zu stellende 3-Wege-Vergleichsfunktion realisiert. Auch ob es sich um ein einziges Schlüsselfeld oder eine Kombination von Feldern handelt, ist Sache des Anwenders; ferner ob Duplikate (unterschiedliche Elemente, die beim Vergleich aber nicht als „ungleich“ herauskommen) zulässig sein sollen oder nicht. Über Suchfunktionen für diesen Fall siehe unten.
Ein in-order-Durchlauf durch einen binären Suchbaum ist äquivalent zum Wandern durch eine sortierte Liste (bei im Wesentlichen gleichem Laufzeitverhalten). Mit anderen Worten: ein binärer Suchbaum bietet ggf. wesentlich mehr Funktionalität (zum Beispiel Durchlauf in der Gegenrichtung und/oder einen „direkten Zugriff“ mit potentiell logarithmischem Laufzeitverhalten – erzielt durch das Prinzip „Teile und herrsche“, das auf der Fernwirkung des Transitivitätsgesetzes beruht) bei einem gleichen oder nur unwesentlich höheren Speicherbedarf.
Motivation Suchbäume sind Lösungen des sogenannten „Wörterbuchproblems“. Angenommen ist eine große Anzahl von Schlüsseln, denen jeweils ein Wert beigegeben ist. In einem Wörterbuch deutsch–englisch ist das deutsche Wort der Schlüssel und englische Wörter sind der gesuchte Wert. Ähnlich verhält es sich bei einem Telefonbuch mit Namen und Adresse als Schlüssel und der Telefonnummer als dem gesuchten Wert.
Mathematisch gesehen realisiert ein Wörterbuch eine (endliche) Funktion mit Paaren (Schlüssel, Wert). Bei der Suche wird ein Suchbegriff (Argument der Funktion) mit einem der Schlüssel zur Deckung gebracht. Hat dies Erfolg, wird dem Suchbegriff der beigegebene Wert als Funktionswert zugeordnet.Gibt es keine Werte, sondern nur Schlüssel, so ist das zugrunde liegende Modell das der endlichen Menge, und die Fragestellung reduziert sich darauf, ob ein gegebener Schlüssel in der Menge vorhanden ist oder nicht. Es ist also die Indikatorfunktion der Menge zu realisieren.
In beiden Beispielen sind üblicherweise die Schlüssel sortiert. Das ist sehr zweckmäßig, denn es erlaubt, das Buch in der Mitte aufzuschlagen und zu überprüfen, ob der Suchbegriff gefunden ist. Ist er nicht gefunden und liegt er beispielsweise alphabetisch vor dem Buchstaben »K«, weiß man zusätzlich, dass man nicht weiter hinten mit »L«, »M« oder »Z« vergleichen muss. Der zur Untersuchung übrig bleibende Teil ist immer ein zusammenhängendes Segment, welches wie das ganze Buch am Anfang wieder halbiert wird – und so weiter bis zum Fund oder bis festzustellen ist, dass der Suchbegriff nicht vorkommt.
Diese Vorgehensweise hat in der Informatik den Namen „binäres Suchen“. Sie wird auf naheliegende Weise durch das sehr bekannte Suchverfahren „binäre Suche im Array“ nachgebildet. Ihr Verhalten ist informationstheoretisch optimal, nämlich logarithmisch, genauer: Bei Schlüsseln benötigt man maximal (Abrundungsfunktion und Aufrundungsfunktion) Vergleiche.
Anders als beim binären Suchen muss beim „sequentiellen Suchen“ der Suchbegriff potentiell mit allen Schlüsseln verglichen werden. (Dafür braucht allerdings die Eingabe nicht sortiert zu sein.) Der Unterschied zwischen den beiden Verfahren kann erheblich sein: In einem Telefonbuch mit Einträgen, müssen beim sequentiellen Suchen im Mittel Vergleiche durchgeführt werden. Beim binären Suchen gelangt man nach maximal Vergleichen zum selben Ergebnis.
Änderungen, Zugänge und Abgänge bei Wörter- und Telefonbüchern können sporadisch, bei Softwaresystemen müssen sie in der Regel unmittelbar reflektiert werden. Zugänge und Abgänge erfordern in einem Array Datentransporte, deren Aufwand proportional zur Länge des Arrays, also linear in ist. Ein solcher Aufwand macht die Effizienz des binären Suchens völlig zunichte.
Die Vorgehensweise beim binären Suchen lässt sich auch mit einem Binärbaum nachbilden. Der erste Schlüssel, mit dem der Suchbegriff zu vergleichen ist, wird in die Wurzel des Binärbaums platziert. Der beim Vergleichsergebnis »kleiner« aufzusuchende nächste Schlüssel wird in den linken Kindknoten platziert und entsprechend der Schlüssel für »größer« in den rechten Kindknoten. So fährt man fort, bis alle Schlüssel im Binärbaum untergebracht sind. (Dadurch wird der Binärbaum zu einem binären Suchbaum.)
Durch das Herauslösen der einzelnen Elemente aus dem Array wird große Flexibilität gewonnen: Der Aufwand beim Einfügen für das Zuweisen von Speicherplatz und Beschicken der Felder mit Werten sowie beim Löschen für die Rückgabe des Speicherplatzes ist unabhängig von der Anzahl der Elemente. Verloren geht beim Binärbaum allerdings ein Maß für die Balance, das beim Array durch das Bilden des Mittelwerts zwischen zwei Indizes gegeben ist. Darüber hinaus kann ein Binärbaum, der einmal hervorragend balanciert war, durch Einfügungen und Löschungen seine Balance verlieren und im Extremfall, wenn nämlich jeder Knoten nur noch einen Kindknoten hat (statt zwei), zu einer linearen Liste degenerieren – mit dem Ergebnis, dass eine Suche einer sequentiellen Suche gleichkommt.
Die Informatiker haben verschiedene Balance-Kriterien für Binärbäume entwickelt. Bei den meisten sind die Aufwände für das Suchen, Einfügen und Löschen logarithmisch, wenn auch mit unterschiedlichen konstanten Faktoren. Einige Lösungsprinzipien zur Problematik der Entartung bei dynamischen Binärbäumen finden sich im
mini|235px|Abb. 1A: Binärer Suchbaum der Höhe 5 mit Wurzel und 13 Knoten, die Schlüssel tragen mini|240px|Abb. 1B: Derselbe binäre Suchbaum derselben Höhe 5 in anderer Sichtweise:Wurzel , 13 innere Knoten (grün und blau) und 14 äußere Knoten (rot); die inneren mit den Schlüsseln der Abb. 1A
Terminologie Die Begriffe Knoten und Kante, letztere definitionsgemäß als gerichtete Kante (oder auch Bogen und Pfeil), werden von den allgemeinen Graphen übernommen. Wenn die Gerichtetheit aus dem Kontext klar genug hervorgeht, genügt Kante.
Bei gerichteten Graphen kann man einem Knoten sowohl Ausgangsgrad wie Eingangsgrad zuordnen. Üblicherweise werden Binärbäume als Out-Trees aufgefasst. In einem solchen gewurzelten Baum gibt es genau einen Knoten, der den Eingangsgrad 0 hat. Er wird als die Wurzel bezeichnet. Alle anderen Knoten haben den Eingangsgrad 1. Der Ausgangsgrad ist die Anzahl der Kindknoten und ist beim Binärbaum auf maximal 2 beschränkt. Damit ist seine Ordnung als Out-Tree ≤ 2.
Knoten mit Ausgangsgrad ≥ 1 bezeichnet man als interne (innere) Knoten, solche mit Ausgangsgrad 0 als Blätter oder externe (äußere) Knoten. Bei Binärbäumen – und nur dort – findet sich gelegentlich die Bezeichnung Halbblatt für einen Knoten mit Ausgangsgrad 1 (englisch manchmal: non-branching node). Dann ist ein Blatt ein doppeltes Halbblatt.
Unterschiedliche Sprechweisen Den Knoten des Binärbaums in der Abb. 1A sind Schlüssel in Gestalt von Großbuchstaben zugeordnet. Da bei der in-order-Traversierung deren (alphabetische) Sortierordnung befolgt wird, ist der Baum ein binärer Suchbaum.
In der Abb. 1B ist die identische Schlüsselmenge in einem anderen binären Suchbaum dargestellt, einem Suchbaum, der explizite „NIL-Knoten“ enthält. Hier tragen nur die internen Knoten Schlüssel, wogegen die externen, die NIL-Knoten (auch externe Blätter genannt), als Platzhalter für die Intervalle zwischen den Schlüsseln (so beispielsweise in der Abb. 3), also als Einfügepunkte des binären Suchbaums fungieren. (Der Knoten mit dem Schlüssel ist hier ein internes Blatt.) Knoten mit Ausgangsgrad 1 gibt es nicht. Der schlüssellose Suchbaum besteht aus genau einem Knoten, der extern und Wurzel zugleich ist. Da bei dieser Sichtweise die Höhe des (total) leeren Baums (der kein Suchbaum ist) zu −1 definiert ist, somit dem schlüssellosen Baum die Höhe 0 zukommt, stimmen die Höhenbegriffe überein, wenn in der Sichtweise der Abb. 1A dem leeren und zugleich schlüssellosen Baum die Höhe 0 und einem Baum, der nur aus einem Knoten besteht, die Höhe 1 zugeteilt wird.Die Sichtweise der Abb. 1B findet sich beispielsweise bei #Knuth und im Artikel Rot-Schwarz-Baum. Eine explizite Gegenüberstellung der beiden Sichtweisen gibt #Pfaff 2004a, p. 30 „4.1.1 Aside: Differing Definitions“. Dort wird die Sichtweise der Abb. 1A als die des Implementierers bezeichnet.
Knotenorientierte und blattorientierte Speicherung Wenn – wie oben und in der Abb. 1A – die Inhalte der Menge in den Knoten abgespeichert werden und die externen Knoten leer sind, nennt man die Art der Speicherung knotenorientiert. Um auszudrücken, dass sie nicht zur Menge gehören, bezeichnet man in diesem Fall die externen Knoten zur besseren Unterscheidung als externe Blätter. Ein externes Blatt stellt einen Einfügepunkt dar.
Bei der blattorientierten Speicherung sind die Inhalte der Menge in den Blättern abgespeichert, und die Knoten stellen nur Hinweisschilder für die Navigation dar, die möglicherweise mit den Schlüsseln der Menge wenig zu tun haben.#Mehlhorn 1988 S. 296
Begriffsklärung Zur Beachtung: Der Begriff „Nachbar“ (und „Nachbarschaft“ etc.) wird in diesem Artikel (und bei den Suchbäumen generell) anders als sonst in der Graphentheorie verwendet, nämlich ausschließlich im Sinn der eingeprägten Ordnungsrelation: „rechter“ Nachbar meint den nächsten Knoten in aufsteigender Richtung, „linker“ in absteigender. Muss in diesem Artikel auf die Hierarchiestruktur des Baumes eingegangen werden, so werden Begriffe wie „Elter“ oder „Vorfahr“ bzw. „Kind“ oder „Nachfahr“ verwendet. Die hierarchische Anordnung der Knoten in der Baumstruktur des binären Suchbaums wird als sekundär und mehr oder minder zufällig angesehen – ganz im Vordergrund steht die korrekte Darstellung der Reihenfolge. Ähnlich sekundär ist die Frage, welcher Knoten gerade die Rolle der Wurzel spielt, insbesondere wenn es sich um einen selbst-balancierenden Baum handelt. Insofern eignet die Adresse der Wurzel sich nicht zur Identifizierung des Baumes. Dagegen kann die feste Adresse eines Zeigers zur Wurzel als Identifikation des Baumes genommen werden, dessen Zeigerwert dann aber auch von den Operationen des Baums zu pflegen ist.
Ordnungsrelation Damit binäres Suchen, Sortieren etc. funktionieren kann, muss die Ordnungsrelation eine totale Quasiordnung, im Englischen „total preorder“, sein. Die Bezeichnungen für die induzierte Duplikatrelation und die induzierte strenge Halbordnung seien wie dort.
Die Trichotomie einer entsprechenden 3-Wege-Vergleichsfunktion deren Erfüllung der Relationsgesetze die Software nicht nachprüfen kann – von ihrem Ergebnis ist nur das Vorzeichen relevant – ergibt sich folgendermaßen: , falls ( kleiner als ), , falls ( Duplikat von ), , falls ( größer als ).
Nach Vertauschung von und und einer Umordnung erkennt man, dass .
Die induzierte Ordnungsrelation ist eine strenge schwache Ordnung, im Englischen strict weak ordering. Sie induziert auf den Äquivalenzklassen dieser Relation, genauer: den Äquivalenzklassen der Duplikatrelation, eine strenge Totalordnung.
Offensichtlich lässt sich jede solche Ordnung spiegeln, d. h. mit vertauschen, das Ergebnis ist wieder eine strenge schwache Ordnung. Nachbarschaftsbeziehungen bleiben bestehen, es wird nur „größer“ mit „kleiner“ bzw. „rechts“ mit „links“ vertauscht.
Anmerkungen: