3.6.1 Ausgeglichene Bäume

Wenn man keine weiteren Vorkehrungen trifft, kann ein Baum (beispielsweise ein binärer Suchbaum) im besten Fall halbwegs ausgeglichen sein (im Hinblick auf die Pfadlänge von der Wurzel zu den einzelnen Blättern); dann kann man bei $N$ Knoten (Elementen) schlimmstenfalls $\log N + 1$ Vergleiche erwarten, um ein Element zu finden (was einem Laufzeitverhalten von $\mbox{O}(\log N)$ für die Suche nach einem Element entspricht); ebenso kann der Baum aber auch im ungünstigsten Fall zu einer Liste entarten; dann ist die maximale Pfadlänge $N$, und die Suchzeit von der Größenordnung $\mbox{O}(N)$.

Um den ungünstigsten Fall zu vermeiden, muß man den Baum ständig ausgeglichen halten. Das bedeutet, daß bei jeder Änderung an der Struktur (Einfügen, Löschen) der Baum möglicherweise reorganisiert werden muß. Durch diesen zusätzlichen Aufwand beim Aufbau des Baums erkauft man sich bessere Suchzeiten, da die Pfadlängen so kurz wie möglich gehalten werden. (Daran kann man natürlich schon erkennen, daß sich der Aufwand nicht lohnt, wenn die Suchzeiten unkritisch sind, und eine Ersparnis hier den Mehraufwand beim Implementieren und Einfügen nicht rechtfertigt.)

Im folgenden werden die wichtigsten Methoden, ausgeglichene Bäume zu bauen, kurz vorgestellt.

Der zusätzliche Verwaltungsaufwand ist in jedem Fall enorm; die einzelnen Verfahren werden deshalb nicht bis ins Detail beschrieben. Mehr zu dem Thema findet man recht verständlich bei [Sedgewick C].

Prinzipiell kann man einen binären Suchbaum, wie er bisher vorgestellt wurde, ausgeglichen halten, indem nach jeder Strukturänderung nach dem mittleren Element (in der Suchreihenfolge) gesucht wird, dieses Element zur Wurzel gemacht wird mit allen kleineren Elementen links davon und allen größeren Elementen rechts davon, und dann anschließend die beiden Teilbäume ebenso in Ordnung bringt. Dadurch bedingt aber jede kleine Änderung eine komplette Neuorganisation des gesamten Baums mit entsprechend vielen Verschiebungen.

Die tatsächlich verwendeten Verfahren dagegen erlauben mehr Freiheit, was den einzelnen Knoten angeht: anstatt nur ein Element und zwei Nachfolger je Knoten zuzulassen, geht man zu größeren Knoten über, die anstatt einem auch mehr Elemente besitzen können, und statt zwei auch mehr Nachfolger. Dadurch kann man Strukturänderungen in den meisten Fällen auf einen kleinen Bereich begrenzen, und spart dadurch im Schnitt viel Rechenaufwand.

3.6.1.1 Top-Down 2-3-4-Bäume

Wenn man Knoten mit

2

Nachfolgern und einem Datenelement,

3

Nachfolgern und zwei Datenelementen, sowie

4

Nachfolgern und drei Datenelementen

zuläßt, kommt man zu sogenannten 2-3-4-Bäumen.

Abbildung: Beispiel für einen 2-3-4-Baum

In Abbildung 3.1 ist ein kleiner Baum zu sehen, der aus einem 3-Knoten als Wurzel, und je einem 2-, 4- und 3-Knoten als Kinder.

Beim Einfügen eines neuen Elements wird die passende Stelle im Baum gesucht. Wenn hier gerade ein 2- oder 3-Knoten steht, dann wird er um das neue Datenelement erweitert. Trifft man dagegen auf einen 4-Knoten, dann kann der kein weiteres Element aufnehmen, und muß vor dem Einfügen in zwei 2-Knoten zerlegt werden.

Durch das Aufteilen eines 4-Knotens muß aber der nächsthöhere Knoten ein Element mehr aufnehmen. Falls das auch ein 4-Knoten ist, muß der wiederum aufgeteilt, gegebenenfalls dessen Vater ebenfalls, und so weiter. Dieses Aufteilen bottom up, also von unten nach oben, kann einerseits im ungünstigsten Fall rechenaufwendig sein, und ist andererseits ungeschickt zu programmieren, weil man entweder bei jedem Element einen Zeiger auf den Vater braucht um sich in Richtung Wurzel hangeln zu können, oder jeweils aufwendig von oben her im Baum suchen muß.

Günstiger ist es daher, top down vorzugehen: Wenn man ein Element einfügen will, und von der Wurzel aus nach einem geeigneten Platz sucht, teilt man gleich vorsorglich alle besuchten 4-Knoten in jeweils zwei 2-Knoten auf. Dann ist jedes Aufteilen nur eine lokale Operation, bei der nur der direkte Vater berücksichtigt werden muß.

Die Ausgeglichenheit ergibt sich bei dieser Art von Bäumen automatisch.

Das Implementieren dieser Bäume ist sehr aufwendig, weil einzelne Operationen nur umständlich zu programmieren sind. Deshalb werden Bäume in dieser Form kaum verwendet; aber als Grundlage um ausgefeiltere Strukturen zu beschreiben, sind sie recht nützlich.

3.6.1.2 Red-Black-Trees

So nett die automatische Ausgeglichenheit der 2-3-4-Bäume auch ist: Die Implementation ist sehr aufwendig, weil die Verwaltung einer unterschiedlichen Anzahl Elementen in einem Knoten umständlich ist; ein Binärbaum ist viel einfacher.

Jetzt gibt es aber die Möglichkeit, jeden 4-Knoten eines 2-3-4-Baums (drei Elemente) in einen Knoten mit dem mittleren Element und dem ersten und dritten Element als linken oder rechten Nachfolger aufzulösen.

Ebenso kann man einen 3-Knoten (zwei Elemente) in einen Knoten umsetzen aus dem linken Element und einem rechten Nachfolger aus dem rechten Element; wahlweise kann man auch das rechte Element des ursprünglichen Knotens nehmen, und das linke Element als linken Nachfolger einhängen (Abbildung 3.2).

Abbildung: Umwandlung von 2-3-4-Knoten zu binären Knoten

Der kleine Baum aus Abbildung 3.1 ist in Abbildung 3.3 zu einem Binärbaum umgebaut.

Abbildung: Der 2-3-4-Baum umgebaut zu einem Binärbaum (Red-Black-Tree)

Aufgrund der üblichen Darstellung (beim Auflösen von 3- und 4-Knoten eingeführte Kanten in rot, ursprüngliche Kanten schwarz) heißen solche Bäume Red-Black-Trees oder Rot-Schwarz-Bäume.

Die zusätzlichen (roten) Kanten bewirken natürlich, daß der Baum nicht mehr wirklich ausgeglichen ist. Da aber durch jeden umgewandelten Knoten höchstens eine zusätzliche Baumebene eingeführt wird, wächst jeder Pfad um maximal 100%. Die Suchzeit bleibt nach wie in der Ordnung $\mbox{O}(\log N)$. Ausgeglichen ist der Baum nur, wenn man ausschließlich die schwarzen Kanten zählt.

3.6.1.3 AVL-Bäume

Ein AVL-Baum (nach Georgii Maksimovich Adel'son-Vel'skii und Evgenii Mikhailovich Landis) ist ein Binärbaum.

Die Tiefen beider Teilbäume jedes Knotens unterscheiden sich jeweils höchstens um 1. Bei einer Verletzung dieser Bedingung führt zu einer Ausgleichsoperation, die rechenaufwendig ist; dafür werden Rotationen durchgeführt; der Baum muß anhand des Suchwegs zur Einfügestelle nach oben durchlaufen werden (bottom up).

Neben dem erhöhten Rechenaufwand zum Ausgleichen ist zusätzlich noch etwas Zusatzinformation pro Knoten nötig (zwei Bit meist, mindestens eines).

3.6.1.4 B-Bäume, Bayerbäume

Bayerbaum

variierbare Anzahl Elemente/Nachfolger pro Knoten; dadurch ist die Knotengröße an effektive Hardwarenutzung anpaßbar (beispielsweise an die Blockgröße eines Dateisystems). Dadurch sehr geeignet für Indexdateien von Datenbanken.

Die einzelnen Knoten sind nicht immer ganz gefüllt, sondern die Belegung jedes Knotens schwankt zwischen einem Kleinst- und einem Größtwert. Dadurch ist in der Regel immer Luft vorhanden, um Strukturänderungen beim Einfügen oder Löschen möglichst lokal zu halten.

Kompakte Einführung in [c't 5/89 Bayerbäume].