Vorlesung Informatik 2 - Teil B: Theorie
4.8 AVL Bäume - Grundlagen
Ein AVL-Baum ist ein binärer Suchbaum, der beim Einfügen und Löschen so balanciert bleibt, dass an jedem Knoten der Balance Faktor 0, 1 oder -1 ist.
1962 veröffentliche die russische Akademie der Wissenschaften einen fünf Seiten langen Artikel von Georgy Adelson-Velski und Evgenii Landis.
Die englische Übersetzung finde Sie hier: An Algorithm for the Organization of Information. O bwohl der Artikel nur drei Seiten lang ist, hat er eine enorme Bedeutung für die praktische Informatik.
Ein AVL Baum ist ein binärer Suchbaum, bei dem sich an jedem Knoten die Höhe der beiden Teilbäume höchsten um 1 unterscheidet.
Die Balance-Faktoren der Knoten in einem AVL Baum haben also alle die Werte 1, 0 oder -1.
Daraus folgt, dass die Höhe eines AVL Baumes die Komplexität O(logN) hat. Da bei Einfügen, Suchen und Löschen immer entlang eines absoluten Pfades bewegt, garantierrt der AVL Baum O(log N) für diese Operationen. MAn kann zeigen, dass die maximale Pfadlänge eines Baums mit n Knoten bei 1,44 log(n+2) - 1,33 liegt.
Ein AVL Baum implementiert also einen assoziative Speicher (Map) für Daten mit sortierbaren Schlüsseln, der für die Operationen pot, get und delete O(log N) garantiert.
Der AVl Algorithmus erhält die Balanciertheit durch sogenannte Rotationen von Teilbäumen.
Ein einfaches Beispiel: der Suchbaum aus den Buchstaben MOOS:
M
\
O
\
S
(doppelte Schlüssel kommen in einer Map nicht vor) verletzt am Knoten M die AVL Bedingung.
Durch eine Rotation nach Links wird O zur Wurzel und den Baum ist balanciert:
O
/ \
M S
das ist die einfache Linksrotation am Knoten M.
Erweitern wir den Baum zu den Buchstaben MOOSBACH, wird zunächst B und A an den linken Teilbaum angefügt. Dabei folgen wir nach jedem Einfügen den absoluten Pfad des neuen Knotens bis zur Wurzel und prüfen, ob die Balance-Bedingung verletzt ist. Nach dem Einfügen von A ist die am Knoten M der Fall, denn er hat einen Balance-Faktor von -2.
O
/ \
M S / B / A
Der erste Knoten, der beim Durchlaufen des Pfades die Balance verletzt, wird rotiert. In diesem Fall wird also eine einfache Rechtsrotation am Knoten M durchgeführt, und der Baum erfüllt wieder die AVL Bedingung.
O / \
B S / \ A M
Die Suche entlang des Pfades hat die Komplexität O(log N), das Rotieren O(1), denn es ist ja unabhängig von der Größe des Baumes.
Die Entscheidung, ob eine Rechts- oder Linksrotation durchgeführt werden muss, häng davon ab, in welchem Teilbaum sich der neue Knoten befindet.
Im Beispiel war der Pfad zwischen dem eingefügten Knoten und dem zu rotierenden Knoten immer gerade, also ohne Knick ( erst S-O-M und dann A-B-M ). In diesen Fällen reicht eine einfache Rotation.
Wenn der Pfad zwischen dem eingefügten Knoten und dem zu rotierenden Knoten einen Knick hat, muss eine Doppelrotation durchgeführt werden.
Beispiel: Suchbaum aus den Buchstaben KUSS:
K
\
U
/
S
Nachdem S eingefügt wurde, verletzt K die AVL Bedingung. Der Pfad von S nach K ist aber nicht gerade, sondern hat einen Knick. Deshalb wird zweimal rotiert:
- der mittlere Knoten (U) wird nach rechts rotiert. Danach hat der Pfad keinen Knick mehr
- der obere Knoten (K) wird nach links rotiert.
Diese doppelte Rechts-Links Rotation mach S zur neuen Wurzel und der Baum erfüllt wieder die AVL Bedingung.
K K S
\ \ / \
U - R(U) --> S -- L(K) --> K U
/ \
S U
Auch hier entscheidet die Richtung, aus der man kommt, ob eine Rechts-Links oder eine Links-Rechts Rotation durchgeführt werden muss.