Binäre Suchbäume

Ein ausgeglichener binärer Suchbaum mit 1023 Schlüsseln findet jeden davon mit höchstens 10 Vergleichen; aus sortierter Eingabe gebaut, können dieselben Schlüssel 1023 brauchen.

Binäre Suche, in die Form eingebaut

Die binäre Suche in einem sortierten Array findet einen Schlüssel mit etwa log₂ n Prüfungen, aber Einfügen in ein sortiertes Array verschiebt Werte. Eine Hashtabelle fügt schnell ein, vergisst aber die Ordnung: Sie kann dir nicht einfach den kleinsten Schlüssel nennen oder den nächsten nach 40. Ein binärer Suchbaum (BST) will beides. Er besteht aus Knoten wie eine verkettete Liste, aber jeder Knoten hat zwei Zeiger, left und right. Der oberste Knoten ist die Wurzel, ein Knoten ohne Kinder ist ein Blatt.

Eine Regel macht ihn zum Suchbaum: Für jeden Knoten sind alle Schlüssel in seinem linken Teilbaum kleiner und alle Schlüssel in seinem rechten Teilbaum größer. Um einen Schlüssel zu suchen, beginnst du an der Wurzel und vergleichst. Gleich heißt gefunden. Kleiner heißt nach links, größer heißt nach rechts. Jeder Vergleich verwirft einen ganzen Teilbaum, so wie die binäre Suche die halbe Liste verwirft. Die Suche nach 60 im Baum 50, 30, 70, 20, 40, 60, 80 vergleicht mit 50, dann 70, dann 60: 3 Vergleiche.

Einfügen folgt demselben Weg. Geh nach links oder rechts, bis der Zeiger, den du brauchst, leer ist, und häng den neuen Knoten dort an. Einfügen von 45 vergleicht mit 50 (nach links), 30 (nach rechts) und 40 (nach rechts), und 40 hat kein rechtes Kind, also wird 45 dieses Kind. Einen Knoten zu löschen, der kein Blatt ist, braucht eine weitere Idee: Die MIT-Unterlagen tauschen sein Element mit dem nächsten oder vorherigen Schlüssel in der Reihenfolge und löschen stattdessen dort. Die Zählregel im Labor ist ein Vergleich pro Knoten auf dem Weg.

Auf die Höhe kommt es an

Wie viele Vergleiche kann eine Suche brauchen? Höchstens einen pro Ebene, die Kosten hängen also von der Höhe des Baums ab, der Zahl der Kanten auf dem längsten Weg von der Wurzel hinunter zu einem Blatt. Die MIT-Unterlagen sagen es so: Baumoperationen laufen in O(h) Zeit. Der Baum 50, 30, 70, 20, 40, 60, 80 hat die Höhe 2, also braucht keine Suche mehr als 3 Vergleiche. Ein perfekt ausgeglichener Baum mit 1023 Knoten hat die Höhe 9 und braucht höchstens 10.

Die Form hängt aber von der Einfügereihenfolge ab. Füg 10, 20, 30, 40, 50, 60, 70 sortiert ein, und jeder Schlüssel ist größer als alles davor, also kommt jeder neue Knoten rechts an den letzten. Der Baum wird eine Kette der Höhe 6, und die Suche nach 70 braucht 7 Vergleiche: eine verkettete Liste mit zusätzlichen Zeigern. Bei 1023 sortierten Schlüsseln braucht die schlechteste Suche 1023 Vergleiche statt 10.

Ausgeglichene Bäume lösen das, indem sie sich nach jedem Einfügen oder Löschen umformen. Das erste Verfahren war der AVL-Baum von Georgi Adelson-Velski und Jewgeni Landis aus dem Jahr 1962, den die Vorlesung 7 von MIT behandelt. Er hält an jedem Knoten die Höhen der beiden Teilbäume höchstens 1 auseinander und repariert jede Verletzung mit kleinen lokalen Umbauten, den Rotationen. So bleibt die Höhe O(log n), und Suchen, Einfügen und Löschen bleiben O(log n), egal in welcher Reihenfolge die Schlüssel kommen.

Schlüssel in Reihenfolge, ganz umsonst

Ein BST weiß mehr als nur, was enthalten ist. Besuch rekursiv den linken Teilbaum, dann den Knoten, dann den rechten Teilbaum, und die Schlüssel kommen sortiert heraus. Dieser In-Order-Durchlauf (MIT nennt es traversal order) ist die Art, wie ein BST „kleinster Schlüssel“, „größter Schlüssel“ und „nächster Schlüssel nach 40“ beantwortet, die Ordnungsoperationen der Set-Schnittstelle von MIT, die eine Hashtabelle nicht schnell kann.