AVL-Baum – einfach erklärt

Grundidee und Bedeutung

Ein AVL-Baum ist eine Datenstruktur der Informatik und eine besondere Form des binären Suchbaums. Er wurde 1962 von Georgi Maximowitsch Adelson-Welski und Jewgeni Michailowitsch Landis vorgestellt und gilt als älteste Datenstruktur für balancierte Bäume. Wie andere Suchbäume dient er dem „Wörterbuchproblem“: Schlüssel sollen effizient gesucht, eingefügt und gelöscht werden können.

Der zentrale Vorteil eines AVL-Baums ist seine Höhen-Balancierung. An jedem Knoten dürfen sich die Höhen des linken und rechten Teilbaums höchstens um eins unterscheiden. Dadurch wächst die Höhe des Baums nur logarithmisch mit der Zahl der Schlüssel. Weil die Zahl der Vergleiche beim Suchen direkt von der Höhe abhängt, sind Suchen, Einfügen und Löschen im schlechtesten Fall logarithmisch: O(log n). Der Speicherplatzbedarf liegt bei O(n). Der reine Modifikationsaufwand beim Einfügen und Löschen ist im Mittel konstant, wenn das Positionieren auf das Zielelement nicht mitgerechnet wird.

AVL-Kriterium

Der Balance-Faktor BF(t) eines Knotens oder Teilbaums t ist definiert als Höhendifferenz zwischen rechtem und linkem Kindbaum:

BF(t) := Height(t_r) - Height(t_l).

Dabei ist Height(t) die Höhe des Baums t, t_l der linke Kindbaum und t_r der rechte Kindbaum. Ein Knoten mit BF(t)=0 heißt höhengleich oder ausgewogen. Bei BF(t)<0 ist er linkslastig, bei BF(t)>0 rechtslastig.

Ein binärer Suchbaum ist genau dann ein AVL-Baum, wenn an jedem Knoten t die AVL-Bedingung gilt:

-1 <= BF(t) <= +1.

Für einen AVL-Baum t mit n Knoten ist die Höhe durch folgende Ungleichung beschränkt:

log_2(n+1) <= Height(t) < c log_2(n+2) + b,

mit c := 1 / log_2 Phi ≈ 1,440420, b := (c/2) log_2 5 - 2 ≈ -0,327724 und Phi := (1 + sqrt(5)) / 2 ≈ 1,618034, der Zahl des goldenen Schnitts. Die untere Schranke stammt vom vollständigen Binärbaum, die obere vom Fibonacci-Baum, der bei gegebener Höhe die kleinste Knotenzahl und damit bei gleicher Knotenzahl die größte Höhe hat.

Suchen, Einfügen und Löschen

Viele Navigationsoperationen eines AVL-Baums entsprechen denen eines gewöhnlichen binären Suchbaums. Dazu gehören Suchen, Traversieren, Iterieren sowie das Aufsuchen des ersten oder letzten Elements. Der Baum bleibt dabei unverändert. Da die Höhe logarithmisch zur Knotenzahl ist, ist auch die Suchzeit im schlechtesten Fall O(log n). Das Suchen setzt eine totale Quasiordnung der Schlüssel voraus, meist durch eine Vergleichsfunktion.

Beim Einfügen wird zunächst wie in einem binären Suchbaum der Einfügepunkt gesucht. Der neue Schlüssel wird als Blatt eingehängt. Danach kann sich die Höhe eines Teilbaums ändern, und auf dem Weg zurück nach oben müssen Balance-Faktoren angepasst werden. Wird ein Balance-Faktor zu 0, ist die Höhenzunahme aufgefangen. Wird er zu ±1, muss weiter oben geprüft werden. Wird er zu ±2, ist eine Rebalancierung nötig. Nach einer Rebalancierung ist beim Einfügen das AVL-Kriterium wieder erfüllt, und oberhalb sind keine weiteren Änderungen nötig. Der Aufwand im schlechtesten Fall ist O(log n), der reine Modifikationsaufwand im Mittel und in reinen Einfügeszenarien amortisiert konstant.

Beim Löschen gibt es mehr Fälle. Ein Blatt oder Halbblatt lässt sich einfach entfernen. Hat der zu löschende Knoten zwei Kinder, wird ein In-order-Nachbar als Ersatz gewählt: entweder der rechteste Knoten des linken Kindbaums oder der linkeste des rechten Kindbaums. Danach müssen Höhenänderungen in den Balance-Faktoren berücksichtigt werden. Wird ein Balance-Faktor zu ±1, endet die Korrektur. Wird er zu 0, muss weiter oben geprüft werden. Wird er zu ±2, ist eine Rebalancierung nötig; danach kann die Höhe weiter sinken, sodass weitere Prüfungen folgen können. Auch das Löschen hat im schlechtesten Fall O(log n) Aufwand und im Mittel konstanten Modifikationsaufwand, wenn das Auffinden des Knotens nicht mitgerechnet wird.

Rebalancierung durch Rotationen

Eine Rebalancierung wird nötig, wenn durch Einfügen oder Löschen der Höhenunterschied zwischen zwei Geschwister-Teilbäumen größer als 1 wird. Dann ist am Elterknoten das AVL-Kriterium verletzt. Die Korrektur erfolgt durch Rotationen. Dabei bleibt die In-order-Reihenfolge der Schlüssel erhalten, also die Sortierreihenfolge des Suchbaums. Eine Rotation verändert nur eine konstante Anzahl von Verknüpfungen an einer konstanten Anzahl von Knoten.

Es gibt Einfachrotationen und Doppelrotationen. Eine Einfachrotation wird verwendet, wenn die Balance zweimal in dieselbe Richtung geht, zum Beispiel in einer Rechts-Rechts-Situation oder gespiegelt in einer Links-Links-Situation. In einer Rechts-Rechts-Situation hilft eine Linksrotation; in einer Links-Links-Situation eine Rechtsrotation.

Eine Doppelrotation wird verwendet, wenn die Balance die Richtung wechselt, zum Beispiel in einer Rechts-Links-Situation oder gespiegelt in einer Links-Rechts-Situation. Bei einer Rechts-Links-Situation besteht die Doppelrotation aus einer Rechtsrotation durch den rechten Kindknoten und danach einer Linksrotation durch den ursprünglichen Knoten. Bei einer Links-Rechts-Situation geschieht dies gespiegelt. Im Artikel wird als Beispiel genannt, dass der Baum aus Abbildung 1 nach Löschen des Knotens „G“ durch zwei Einfachrotationen Rechts(„F“) und später Links(„J“) rebalanciert wird; nach Einfügen eines Knotens „T“ geschieht dies durch die Doppelrotation LinksRechts(„V“, „S“).

Weitere Operationen und Implementierung

Neben den Standardoperationen können auch ganze AVL-Bäume verarbeitet werden. Beim Verketten werden zwei AVL-Bäume mit logarithmischem Aufwand zusammengefügt, wenn alle Schlüssel des ersten Baums vor allen Schlüsseln des zweiten liegen. Dabei wird ein Element als Bindeglied benutzt, und anschließend werden Balance-Faktoren wie beim Einfügen korrigiert. Beim Spalten wird ein AVL-Baum an einer Stelle zwischen zwei Schlüsseln in zwei AVL-Bäume geteilt: links die kleineren, rechts die größeren Schlüssel. Auch dies ist mit Aufwand proportional zur Höhe, also logarithmisch, möglich.

Aus solchen Operationen ergeben sich Anwendungsbeispiele: Eine Massenlöschung aller Schlüssel in einem zusammenhängenden Intervall kann durch zweimaliges Spalten und einmaliges Verketten erfolgen, bei einem Intervall am Rand auch durch einmaliges Spalten. Eine Masseneinfügung kann durch einmaliges Spalten und zweimaliges Verketten erfolgen, wenn die einzufügende Menge bereits als AVL-Baum vorbereitet ist und ihre Schlüssel in einem noch freien Intervall liegen.

Für die Implementierung braucht ein AVL-Knoten zusätzlich zum normalen binären Suchbaum den Balance-Faktor mit seinen drei Werten, also 2 Bits. Unter Umständen können diese Bits in einem Zeigerfeld untergebracht werden. Ein Cursor kann als Paar aus Knoten und Richtung dienen und Such-, Einfüge-, Lösch- und Traversieroperationen verbinden. Mit Elterzeigern ist der Cursor klein; ohne Elterzeiger muss zusätzlich der Pfad zur Wurzel gespeichert werden.

Bei paralleler Verarbeitung ist problematisch, dass AVL-Operationen sowohl von der Wurzel zum Blatt als auch vom Blatt zur Wurzel laufen können. Dadurch können Deadlocks entstehen, wenn Prozesse in entgegengesetzten Richtungen arbeiten. Verzögerte AVL-Bäume vermeiden dies, indem sie den Baum nur von der Wurzel zu den Blättern durchlaufen und Rebalancierungen später beim Suchen nachholen. Dabei gilt eine erweiterte AVL-Bedingung -k <= BF(t) <= +k für ein festes k aus N.

Vergleich und Anwendungen

AVL-Bäume sind eng mit Rot-Schwarz-Bäumen verwandt. Die Menge der AVL-Bäume ist eine echte Teilmenge der Rot-Schwarz-Bäume: Jeder Binärbaum, der das AVL-Kriterium erfüllt, kann so eingefärbt werden, dass er das Rot-Schwarz-Kriterium erfüllt. Umgekehrt gibt es Rot-Schwarz-Bäume, die kein AVL-Baum sind.

AVL-Bäume sind im Worst Case stärker balanciert als Rot-Schwarz-Bäume. Die Worst-Case-Höhe des AVL-Baums ist kleiner, im Artikel angegeben um den Faktor c/2 ≈ 0,720 mit c := 1 / log_2 Phi. Allgemein gelten AVL-Bäume als besser balanciert und beim Suchzeitverhalten als günstiger. Der Speicherplatzbedarf ist praktisch gleich: Rot-Schwarz-Bäume benötigen 1 Bit für die Farbe, AVL-Bäume 2 oder auch 1 Bit für den Balance-Faktor.

Für Platzbedarf und Laufzeit der genannten Operationen sind AVL-Bäume und Rot-Schwarz-Bäume im Mittel und im Worst Case im Wesentlichen gleich. Beim Einfügen haben beide amortisiert konstante Modifikationskosten; beim Löschen bietet der Rot-Schwarz-Baum amortisiert konstante Modifikationskosten, der AVL-Baum im Mittel konstante. Messungen von Ben Pfaff zeigen eine große Ähnlichkeit beider Strukturen mit Laufzeitverhältnissen AVL/RB zwischen 0,677 und 1,077, einem Median von ≈0,947 und einem geometrischen Mittelwert von ≈0,910.

Als grundlegende binäre Suchbäume haben AVL-Bäume ein breites Einsatzgebiet, sind aber häufig mit anderen Suchbaumarten austauschbar. Verwandte Strukturen sind Binärbaum, binärer Suchbaum, balancierter Baum, Rot-Schwarz-Baum, Splay-Baum, gewichteter binärer Suchbaum und Fibonacci-Baum.