Holger Bihr u. Björn Hockmann, Freiherr-vom-Stein-Gymnasium Oberhausen
1. Eigenschaften von AVL-Bäumen
2. Einfügen von Knoten in AVL-Bäumen
3. Löschen von Knoten in AVL-Bäumen
4. Demonstrationsprogramm (Delphi)
Bei AVL-Bäumen (benannt nach Adelson,Velskii und Landis) handelt
es sich um beinahe ausgeglichene Binärbäume. Dabei gilt für
jeden Knoten eines AVL-Baumes die Bedingung, dass sich die Höhe der
beiden untergeordneten Teilbäume höchstens um 1 unterscheiden
darf. Diese Lösung stellt einen guten Kompromiss zwischen einer geringen
Gesamthöhe des Baumes und einem relativ geringen Aufwand beim Einfügen
sowie Löschen von Elementen dar. In der Praxis speichert man für
jeden Knoten einen Grad der Ausgeglichenheit, dabei wird zwischen linkslastig,
völlig ausgeglichen und rechtslastig unterschieden. Eine geringe Gesamthöhe
des Baumes ist erwünscht, da sich die Laufzeit zum Suchen eines Knotens
proportional zur Höhe des Baumes verhält. Ein völlig ausgeglichener
Baum erreicht eine maximale Laufzeit von O(log n), das bedeutet,
die Laufzeit ist proportional zur Baumhöhe. n ist dabei die
Anzahl der Knoten. Ein AVL-Baum weist prinzipiell etwas schlechtere Werte
auf, seine Höhe liegt laut Adelson,Velskii und Landis maximal um 45%
höher als die Höhe eines vollständig ausgeglichenen Baumes.
Der am schlechtesten ausgeglichene AVL-Baum hat bei einer Höhe
i L knoten, wobei für L(i) gilt: L(0)=0, L(1)=1,
L(h)=L(h-1)+1+L(h-2). Empirische Tests haben dabei gezeigt, dass die
zu erwartende Höhe h eines AVL-Baumes mit n Knoten
h=log(n)+c beträgt, wobei c~0,25 gilt, so dass sich
ein AVL-Baum praktisch genauso gut wie ein völlig ausgeglichener Baum
verhält. Aufgrund des gegenüber „normalen“ Binärbäumen
aufwendigeren Einfügens und Löschens sind AVL-Bäume da besonders
attraktiv, wo auf einen fest vorgegebenen Datenbestand viele Zugriffe erforderlich
sind, insbesondere wenn auf alle Knoten im Mittel gleich oft zugegriffen
wird.
2. Einfügen von Knoten in AVL-Bäume
Der Einfügealgorithmus arbeitet folgendermaßen: Der Baum wird bis zum Astende durchlaufen; dabei wird, wenn der Knoten einen größeren Wert enthält, der rechte Teilbaum gewählt, sonst der linke. Dann wird der Knoten angehängt, danach der Suchpfad zurückgegangen und für jeden Knoten der Grad der Ausgeglichenheit aktualisiert, eventuell eine Rotation ausgeführt, wobei es 2 verschiedene Arten gibt.
Der äußere Teilbaum ist zu lang:
|
In diesem Fall wird das AVL-Kriterium für den Knoten 20 nach Einfügen
des Elementes 3 nicht mehr erfüllt. Da der zu lange Teilbaum außen
liegt, ist nur eine einfache Rotation erforderlich. Dabei muss der gesamte
(Teil-)Baum neu angehängt werden, in diesem Fall am Knoten 10. Der
Knoten 15 muss links an den Knoten 20 wieder angefügt werden, da es
ja der nächstkleinere vorhandene Knoten ist. Hier der neu ausgeglichene
Baum (nach einer einfachen Rotation):
 |
Der innere Teilbaum ist zu lang:
 |
Durch Anfügen der 3 wäre das AVL-Kriterium für den Knoten
5 nicht mehr erfüllt; die Höhe des linken Teilbaumes ist 3, die
des rechten nur 1, was ein Ausgleichen erforderlich macht. Eine einfache
Rotation – wie wenn der zu lange Ast außen liegen würde – hätte
jedoch folgendes Ergebnis:
 |
Das Ungleichgewicht wurde lediglich auf die andere Seite verlagert, die
Unausgeglichenheit bleibt erhalten. Daher sind in diesem Fall 2 Rotationen
(Doppelrotation) erforderlich. Zuerst wird der zu lange Ast auf die Außenseite
verlagert.
 |
Nun ist wiederum der äußere Ast zu lang, so dass der Teilbaum
nun mit einer einfachen Rotation der (Teil-)Baum (am Knoten 4) neu aufgehängt
werden kann.
Der nach einer Doppelrotation neu ausgeglichene Baum:
 |
Aufwandsbetrachtungen beim Einfügen
Dieses Beispiel zeigt, dass die Höhe des (Teil-)Baumes nach der Rotation mit der vor dem Einfügen identisch ist. Das garantiert, daß maximal eine (Doppel)rotation zum Ausgleichen des Baumes erforderlich ist.Die Laufzeit des Algorithmus zum Einfügen eines Knotens ist daher kaum länger als die Zeit, die zum Suchen höchstens benötigt wird, nämlich um das Ende eines Astes zu erreichen. Im Mittel kommt eine einfache oder doppelte Rotation auf 2 Eintragungen.
3. Löschen von Knoten in AVL-Bäumen
Der Löschalgorithmus arbeitet ähnlich dem Einfüge-Algorithmus
(Knoten suchen, löschen und nachher den Suchpfad zurückverfolgen,
Balancefaktoren aktualisieren und eventuell Rotationen ausführen).
Wenn ein zu löschender Knoten 1 Nachfolger besitzt, wird er durch
diesen ersetzt. Hat er jedoch 2 Nachfolger, wird er durch den am besten
geeigneten ersetzt; das kann entweder der nächstkleinere oder nächstgrößere
vorhandene Knoten sein, also entweder der am weitesten rechts liegende
Knoten seines linken Teilbaumes oder der am weitesten links liegende Knoten
seines rechten Teilbaumes. Dabei wird bei unterschiedlich langen Teilbäumen
der zu löschende Knoten durch den entsprechenden seines höheren
Teilbaumes ersetzt, um eine notwendige Rotation auf der Ebene des zu löschenden
Knotens zu verhindern, da durch das Ersetzen ja die Höhe des Teilbaumes
reduziert werden kann, etwa in folgendem Beispiel:
 |
Wenn der Knoten 10 gelöscht werden soll, könnte er durch die
7 oder die 11 ersetzt werden; ein Ersetzen durch die 7 (Knoten des kürzeren
Teilbaumes) würde eine Rotation erfordern, ein Ersetzen durch
die 11 hingegen nicht.
Trotzdem kann es sein, dass – wie beim Einfügen – ein erneutes Ausgleichen
erforderlich ist. Ebenfalls gibt es wieder 2 verschiedene Fälle:
Der äußere Teilbaum ist zu lang:
In diesem Fall genügt wieder eine einfache Rotation.
 |
Durch Löschen des Knotens 4 entsteht eine Unausgeglichenheit bei Knoten
3; der Teilbaum wird dabei am Knoten 2 neu anfgehängt. Hier der neu
ausgeglichene Baum nach der einfachen Rotation:
 |
Der innere Teilbaum ist zu lang:
In diesem Fall ist wieder eine Doppelrotation erforderlich.
 |
Beim Löschen von Knoten 2 wird dieser durch den Knoten 1 ersetzt,
so daß die Höhe des linken Teilbaumes des Knotens 3 reduziert
wird. Da der rechte Teilbaum jedoch die Höhe 3 hat, ist ein Ausgleichen
erforderlich.
 |
Zuerst muss der innere zu lange Ast nach außen gehängt werden.
 |
So ist der äußere Teilbaum des Knotens 7 zu lang, was durch
eine weitere Rotation behoben werden kann. Dazu muss der (Teil-)Baum an
Knoten 7 neu angehängt werden.
 |
Wäre hingegen nur einmal eine einfache Rotation angewandt worden,
wie es erforderlich ist, wenn der äußere Teilbaum zu lang ist,
erhielte man folgendes Ergebnis:
 |
Dabei erkennt man, daß die Unausgeglichenheit wiederum nur auf den
anderen Teilbaum verlagert wurde.
Mehrere Rotationen durch Löschen eines Knotens
Beim Löschen eines Knotens kann es – anders als beim Einfügen
– sein, dass das Löschen eines Knotens mehr als eine einfache oder
doppelte Rotation erfordert. Denn wenn durch die Rotation die Höhe
eines Teilbaumes reduziert wird, ist es möglich, daß der übergeordnete
Knoten dieses Teilbaums dadurch das AVL-Kriterium nicht mehr erfüllt.
Dann ist eine weitere Rotation erforderlich:
 |
Das Löschen von Knoten 4 erfordert zunächst eine einfache Rotation.
Der Teilbaum 3-2-1 wird dabei am Knoten 2 neu aufgehängt. Der Baum
sieht dann folgendermaßen aus:
 |
Jetzt ist der Knoten 5 unausgeglichen. Die Höhe seines linken Teilbaumes
beträgt 2, die des rechten hingegen 4, was ein erneutes Ausgleichen
erfordert.
 |
Nun ist der (Teil-)Baum durch erneutes Rotieren ausgeglichen.
Aufwandsbetrachtungen beim Löschen
Dadurch, dass das Löschen eines einzelnen Knotens Rotationen auf
jeder Ebene des Baumes hervorrufen kann, kann die Laufzeit möglicherweise
länger sein als die beim Einfügen von neuen Knoten. Im Mittel
ist sie jedoch identisch, da es seltener als beim Einfügen vorkommt,
dass eine Rotation erforderlich ist.
4. Demonstrationsprogramm (Delphi)
Das Delphi-Projekt AVL1 ist ein Programm zur Darstellung eines AVL-Baums. In den Baum werden beim Start zufällige Knoten eingefügt und angezeigt. Weitere Knoten können eingefügt, entfernt und gesucht werden. Eine Log-Datei beschreibt die Navigation durch den Baum und die Reorganisation, wenn das AVL-Kriterium nicht erfüllt ist.
Download:
Die Datei avl1.zip enthält das Beispielprojekt
als kompilierbares Programm (Delphi 1.0).