Algorithmen und Datenstrukturen
Kapitel 5: Aufbau von Suchbäumen

5.1 Allgemeines zu Suchbäumen

Suchbäume sind Bäume, deren Elemente in einer ganz bestimmten Form angeordnet sind. Diese Form soll gewährleisten, dass ein beliebiges Element x aus einem Baum mit n Elementen mit dem Aufwand ld(n) gefunden werden kann (bei binären Bäumen). Wir wollen zu beginn einige Begriffe definieren:

Wurzel: Das Element, das den Anfang des Baumes darstellt.
Knoten: Ein Element innerhalb des Baumes, das mindestens einen Nachfolger hat.
Blatt: Ein Element am Ende des Baumes, das KEINE Nachfolger enthält, also einen Zweig abschließt.
Schlüssel: Ein Datum (Eintrag/Element) im Baum.
Unterbaum: Alle Elemente eines Baumes, die an einem Knoten hängen, der nicht die Wurzel ist (hier auch Zweig genannt).
Generation: Eine Ebene im Baum.

Ein Suchbaum muss der Anforderung genügen, dass alle Elemente so angeordnet sind, dass sie nach unten hin geordnet sind. Das heißt, alle Elemente rechts eines Knotens sind größer als der Knoten selbst. Alle Elemente links des Knotens sind kleiner als der Knoten. Wir erkennen, dass es keine Elemente geben darf, die gleich groß wie der Knoten sind! Dies verhält sich wie bei einer Datenbank, die auch stets einen Primärschlüssel enthält, in dem jeder Eintrag eindeutig ist.

Wenn wir einen bestimmten Schlüssel im Baum suchen wollen, so können wir in einem Suchbaum an jedem Knoten eine eindeutige Entscheidung für einen bestimmten Unterbaum treffen. Wir finden also stets den Zweig, der zum Ziel führt und können sicher sein, dass der jeweils nicht gewählte Unterbaum den Schlüssel nicht enthält, weil dort alle Werte größer bzw. kleiner sind als der Schlüssel.

An dieser Stelle haben wir nochmals einige Begriffsdefinitionen vorzunehmen:

Knotenorientierter Suchbaum: Der Baum enthält Schlüssel in Knoten und Blättern.
Blattorientierter Suchbaum: Der Baum enthält Schlüssel nur in Blättern. Die Knoten enthalten Zwischenwerte, die linken und rechten Nachfolger trennen und so eine Richtungsentscheid möglich machen.
Gerichteter Baum: Ein Baum, bei dem Richtungspfeile (Zeiger) vom Vorgänger zum Nachfolger führt.
Ungerichteter Baum: Es kann nicht bestimmt werden, welcher Knoten Vorgänger oder Nachfolger sein soll. Insbesondere ist bei einem solchen Baum nicht klar, welcher Knoten die Wurzel bilden soll.

Wir wollen im Folgenden zunächst nur gerichtete knotenorientierte Suchbäume betrachten!

5.1.1 Implementierung einer Baumstruktur

Um einen Baum in einer Programmiersprache darzustellen bedarf es im einfachsten Fall eine Struktur, die einen Schlüssel abbildet. Die Struktur enthält also eine Reihe von Variablen, die zusammen ein Element des Baumes enthält. Zusätzlich dazu werden noch zwei Zeiger vom Typ der Struktur benötigt, die den linken und den rechten Nachfolger referenzieren. Will man einen Baum mit mehr als zwei Nachfolgern pro Knoten implementieren, so braucht man nur entsprechend mehr Zeiger zu definieren. Wer noch Schwierigkeiten bei der Implementierung von Bäumen hat, kann sich zunächst auch das Übungen zu dynamisch verketteten Listen aus dem ANSI-C Teil ansehen. Dynamische Listen sind im Prinzip einseitige Bäume mit nur einem Nachfolger.

5.1.2 Operationen in Suchbäumen

5.1.2.1 Suchen eines Schlüssels

5.1.2.2 Eintragen eines Schlüssels

5.1.2.3 Löschen eines Schlüssels

5.2 AVL-Bäume (Ade´son - Vel´skii - Landis 1962)

Definition: Ein AVL-Baum ist ein Suchbaum, dessen Knoten sich in der Höhe ihrer Unterbäume um höchstens 1 unterscheidet.

Definition: Die Höhe eines leeren Baumes ist 0. Die Höhe eines Baumes mit nur einem Knoten ist 1. Bei allen anderen Bäumen ist die Höhe um 1 größer als die des höheren Unterbaumes.

Hier ist die AVL-Bedingung nicht erfüllt, weil der Zweig F um mehr als eins höher ist als der Zweig Z.	Hier ist die AVL-Bedingung erfüllt!

5.2.1 Ein neues Element in den Baum einhängen

Erkennbar ist, dass sich beim Einhängen eines Elementes in den Baum evtl. Probleme ergeben. Durch das einhängen eines Elementes unterhalb einer (Teil)- Wurzel W kann in den Tochterknoten L (Linker Nachfolger) und R (Rechter Nachfolger) ein Ungleichgewicht entstehen. Wir können (zurecht) davon ausgehen, dass es keine Rolle spielt, ob die Eintragung in L oder R passiert. Betrachten wir also nur die Ausgangssituation, dass L die Höhe k hat und eine Eintragung in R passiert. Es ergeben sich drei mögliche Fälle:

1. h(L) = k; h(R) = k ==> h(W) = k + 1
   Durch Eintragung in R wird | h(L) - h(R) | = 1 ==> Keine Verletzung der AVL- Bedingung möglich!
2. h(L) = k; h(R) = k + 1 ==> h(W) = k + 2
   Durch Eintragen in R entsteht ein Ungleichgewicht in W, weil h(R) = k + 2 um mehr als 1 von h(L) differiert => Die AVL-Bdeingung ist verletzt!

Lösung der Verletzung der AVL-Bedingung

Trotz dieser "Regelwidrigkeit" tragen wir erst einmal ungeniert das Element in den Baum ein. Dann prüfen wir, ob die AVL-Bedingung verletzt wurde. Ist das der Fall, müssen geeignete Maßnahmen ergriffen werden. Nehmen wir an, wir hätten in den folgenden Baum das Element A wie dargestellt eingehängt:

Die Rotation schreibt vor, dass wir den Teilbaum mit dem Übergewicht verkürzen müssen, indem wir die Wurzel in den jeweils anderen Baum verlagern. Den freigewordenen Platz füllt die kleine Rotation mit dem Nachfolgerknoten aus dem übergewichtigen Teilbaum auf (hier: M). Der Knoten B kann dort bleiben wo er ist (der linke Nachfolger von M), nur P hat seinen Platz verloren. Damit P im neuen Baum wieder gefunden werden kann, wird P zum linken Nachfolger von Q gemacht, dass ja nach rechts gerückt wurde und damit keinen linken Nachfolger mehr hat. Damit wären alle Elemente untergebracht und der Algorithmus abgeschlossen.

Hinweis: Beim Einhängen eines Elementes in den Baum betrachtet man zunächst den Knoten, in dem die Verletzung auftritt (Q im ursprünglichen Baum von oben). Dieser wird rotiert. Jetzt könnte man davon ausgehen, dass wir nach der Rotation den darüberliegenden Knoten weiterbehandeln muss. Es lässt sich zeigen, dass die Höhe des Teilbaumes W durch die Reorganisation der darunterliegenden Elemente nicht verändert wird. q.e.d.

Der Name "kleine Rotation" legt schon nahe, dass es auch einen großen Bruder dazu gibt. Und tatsächlich lässt sich zum Beispiel der Folgende Baum NICHT mit Hilfe der kleinen Rotation korrigieren:

Das Einfügen von D führt zu einer Verletzung der AVL-Bedingung. Wir könnten durchaus versuchen, eine kleine Rotation durchzuführen. Die AVL-Bedingung ist dann jedoch immer noch verletzt. An dieser Stelle sollte man sich zunächst klar machen, wie die aktuelle Situation zu bewerten ist. Dazu betrachten wir die "Enkelgeneration" des Knotens, in dem die Regelverletzung entstand (hier: B, F, M; Vater: K). Wir picken uns den Enkel heraus, in dem die Verletzung entstand (hier: F). Dieser ersetzt den Vaterknoten, der wie gewohnt um einen Schritt in die andere Richtung rutscht. Nachdem wir jetzt aber einen inneren Knoten vollständig verrutscht haben (F), müssen wir seine BEIDEN Nachfolger neu verteilen.

Wenn wir logisch vorgehen, bleibt uns keine große Wahl für die beiden "Waisen" E und G. Der rechte Nachfolger von C (F) ist weggefallen. Hierhin kommt der linke Nachfolger von F (E). Das nach unten gerutschte K hat noch platz für einen linken Nachfolger, wohin wir auch sofort das G hängen. Damit sind wieder alle Elemente verteilt und die Rotation abgeschlossen. Wir stellen zufrieden fest, dass auch hier die "Wurzel" X keine AVL-Verletzung mehr ertragen muss.

Zum Schluss stellt sich natürlich noch die Frage, wann man nun eine große Rotation nimmt und wann eine Kleine. Nebenstehende Grafik zeigt den Fehlerknoten M und seine Enkelgeneration. Kommt nun der Fehler aus einem der äußeren Knoten (A und R), so benötigt man eine kleine Rotation. Die große Rotation kommt zum Zug, wenn der Fehler aus einem inneren Knoten (B und P) kommt.

5.2.2 Löschen eines Elementes

Das Löschen funktioniert zunächst analog zu den normalen Suchbäumen (siehe dort). Jetzt müssen wir nur noch sehen, ob wir nicht die AVL-Bedingung verletzt haben. Ist das der Fall, dann müssen wir wieder unterscheiden, woher der Fehler kommt. Wir tun allerdings nicht so, als ob wir ein Element aus einem Zweig genommen hätten, sondern gehen davon aus, dass der jeweils andere Zweig länger geworden ist. Damit bekommen wir die selben Rotationsbedingungen wie beim Einhängen und können jetzt rotieren.

WICHTIG: Beim Löschen kann es durchaus vorkommen, dass die AVL-Bedingung in einem höher liegenden Knoten verletzt wird. Wir müssen also nach der Rotation den Baum weiter nach oben verfolgen und solange rotieren, bis keine Verletzung mehr auftritt.

5.3 B-Bäume (Bayer, McCreight 1970- ´75)

B-Bäume sind knotenorientierte Bäume, die mehr als ein Element pro Knoten enthalten. Ein B-Baum der Ordnung k hat dabei maximal 2*k Elemente pro Knoten, mindestens jedoch k. Einzig die Wurzel darf weniger, nicht jedoch mehr Elemente enthalten. Sehen wir uns einmal einen einfachen B-Baum an:

Aus dieser Struktur lassen sich schon einige Bedingungen für einen B-Baum herauslesen:

1. Ein Knoten mit c Elementen enthält c+1 Zeiger auf nachfolgerknoten
2. Innerhalb eines Knotens gilt: x₁ < x₂ < ... < x_c
3. Der linke Pfeil eines Elementes x zeigt auf einen Knoten, der nur kleinere Elemente y < x enthält
4. Der rechte Pfeil eines Elementes x zeigt auf einen Knoten, der nur größere Elemente z > x enthält

5.3.1 Einhängen von Elementen

Zunächst lässt sich feststellen, dass das Einhängen in nur teilweise gefüllte Knoten reichlich einfach ohne jegliche Bedingungsverletzung vonstatten geht. Wir wollen trivialerweise einmal die Elemente 9, 10, 38 und 39 in den Baum hängen:

Was aber passiert, wenn wir nun das Element 40 eintragen möchten. Es würde natürlich hinter die 39 gehören, da passt es aber nicht mehr hin. Der B-Baum Algorithmus schreibt uns in diesem Fall vor, dass wir aus dem "Knoten + neues Element" das mittlere zu nehmen haben, dieses in den Vater hängen und den betrachteten Knoten in zwei Teile spalten. Folgende Grafik illustriert dies:

Jetzt kommen wir aber in einen gewissen Notstand: Tragen wir doch einmal 11 in den Baum ein. Wir müssen das linke Blatt splitten und die 9 nach oben übernehmen. Leider ist die Wurzel schon voll, so dass wir diese auch splitten müssen. Zum Glück ist es uns erlaubt, die neu entstehende Wurzel mit nur einem Element (21) zu füllen:

5.3.2 Löschen eines Elementes

Das Löschen in einem B-Baum gestalltet sich sehr einfach. Wir unterscheiden hier folgende Fälle:

1. Löschen in einem Blatt, dass mehr als k Elemente enthält
   ==> Einfaches Löschen
2. Löschen in einem inneren Knoten oder der Wurzel
   ==> Wie bei AVL-Bäumen den Eintrag ersetzen durch den rechtesten Eintrag im linken Unterbaum oder den linkesten im Rechten.
3. Löschen in einem Blatt mit genau k Elementen
   • Falls möglich, legt man zwei benachbarte Blätter mit dem verweisenden Eintrag im Vater zu einem Knoten zusammen (hier: löschen von 25):
     
   • Ist dies nicht möglich, so wird rotiert:
     

5.3.3 Bewertung von B-Bäumen

Durch die geringe Höhe von B-Bäumen lassen sie sich relativ schnell durchsuchen. Die Algorithmen zum einhängen und löschen sind vergleichsweise einfach. Trotzdem haben sie einen entscheidenden Nachteil: Durch das Splitten der Bäume beim einhängen kann es passieren, dass wir sehr viele Knoten mit nur k Elementen erhalten. Speichert man die Daten auf dem Hintergrundspeicher (z.B. Festplatte), so ergibt sich das Problem, dass wir auch für die nicht belegten Plätze in einem Knoten Speicher vorsehen müssen und durch die große Zahl der leeren Plätze viel Speicher verloren geht (bis zu 50%).

Dieses Problem liese sich lösen, indem wir fordern, dass die maximale Anzahl der Elemente in einem Knoten ungerade sein muss. Dadurch würde sich eine maximale Fragmentierung von 33% statt 50% ergeben. In diese Lücke springen zum Beispiel B*-Bäume (manchmal auch als B´-Bäume bezeichnet), die in den Knoten nur die Schlüssel, die eigentlichen Elemente nur in den Blättern speichern. Man nennt B*-Bäume deshalb auch blattorientierte B-Bäume. Da man bei solchen Strukturen die inneren Knoten sehr Kompakt anordnen kann (geringe Datenmenge) wählt man häufig für die inneren Knoten 2*k_i = gerade, und für die Blätter 2*k_b = ungerade.