AVL-Baum

(benannt nach Adelson-Velskii und Landis, 1962)

Def.:

Ein Knoten eines binären Baumes heißt ausgeglichen oder balanciert, wenn sich die Höhen seiner beiden Söhne um höchstens $1$ unterscheiden.

Def.:

Ein binärer Suchbaum, in dem jeder Knoten ausgeglichen ist, heißt AVL-Baum.

Sei $bal (b) =$ Höhe des rechten Teilbaums von $b$ minus Höhe des linken Teilbaums von $b$.

Aufgrund der Ausgeglichenheit ist die Suche in einem AVL-Baum auch im ungünstigsten Fall von der Ordnung $O( \log n)$. Um das zu gewährleisten, muss nach jedem Einfügen oder Löschen die Ausgeglichenheit überprüft und ggf. wiederhergestellt werden. Hierzu werden längs des Weges vom eingefügten bzw. gelöschten Element bis zur Wurzel die Balance-Werte abgefragt und durch so genannte Rotationen repariert.

Während das Einfügen eines einzelnen Schlüssels höchstens eine Rotation erfordert, kann das Löschen eine Rotation für jeden Knoten entlang des Weges zur Wurzel verursachen.

Rotationen für AVL-Baum bei linksseitigem Übergewicht

Single LL-Rotation

Bei Einfügen in Teilbaum $X$: Höhe des gesamten Baums vorher und nachher gleich.

Bei Löschen im Teilbaum $Z$: Höhe des gesamten Baums vorher und nachher gleich oder nachher um eins kleiner.

Double LR-Rotation

Bei Einfügen in Teilbaum $Y_1$ oder $Y_2$: Höhe des gesamten Baums vorher und nachher gleich.

Bei Löschen im Teilbaum $Z$: Höhe des gesamten Baums nachher um eins kleiner.

Bei rechtsseitigem Übergewicht werden die symmetrischen Rotationen ``single RR'' und ``double RL'' angewendet.

Minimal ausgeglichene AVL-Bäume sind Fibonacci-Bäume

Satz:

Die Höhe eines AVL-Baumes mit $n$ Knoten ist $\leq 1.45 \cdot \log n$, d.h. höchstens 45 % größer als erforderlich.

Bem.:

Das Löschen eines Knotens in einem Fibonacci-AVL-Baum führt zu einer Reduktion der Höhe des Baumes. Das Löschen des Knotens mit dem größten Schlüssel erfordert die größtmögliche Zahl von Rotationen: Im Fibonacci-Baum $F_n$ werden dabei $\lfloor\frac{n-1}{2}\rfloor$ LL-Rotationen durchgeführt.

Source: AVLKnoten.java     JavaDoc: AVLKnoten.html    

Source: AVLBaum.java     JavaDoc: AVLBaum.html     Source: AVLBaumTest.java     JavaDoc: AVLBaumTest.html     Applet: