AVL-Bäume
Das Problem bei Binär-Bäumen ist, dass sie durch verschiedenste Einfüge- und Lösch-Operationen mit der Zeit degenerieren können. Dadurch verschwindet der Geschwindigkeitsvorteil gegenüber linearen Listen. AVL-Bäume nun sind Binär-Bäume, die nur sehr wenig degenerieren, sie balancieren sich aus. Sie behelfen sich dabei einer sehr einfachen Invariante:
Nach jeder Operation ist der Höhenunterschied der zwei Teilbäume eines jeden Knoten höchstens 1. Man schreibt dabei -1, wenn der linke Teilbaum grösser ist, 0, wenn beide gleich gross sind und +1, wenn der rechte Teilbaum grösser ist.
Um diese Invariante zu gewährleisten, wird in einem AVL-Baum nebst dem linken und rechten Teilbaum auch dieser Höhenunterschied, die sogenannte Balance, abgespeichert. Im folgenden wird diese Balance einfach in die Knoten hineingeschrieben. Beispiel eines AVL-Baumes:
----(-1)----
/ \
--(-1)-- (+1)
/ \ \
(+1) (0) (0)
\
(0)
Man sieht sofort, dass dieser Baum nicht optimal ist, aber die Verteilung ist ziemlich gut im Vergleich zu einem vollständig degenerierten Baum. Tatsächlich kann man beweisen, dass der Aufwand, um ein Element zu Finden, Einfügen und Löschen stets in O(logn) bewältigt werden kann.
Die Definition des AVL-Baumes an sich ist ziemlich einfach und einleuchtend, jedoch ist das Verfahren zur Aufrechterhaltung der Invariante etwas verwirrend. Um in die ganze Sache etwas Entwirrung zu zaubern, definiert man vorerst mal die sogenannten Rotationen.
Eine Rotation ist nichts anderes als das Umhängen von Teilbäumen und somit das Umordnen von Knoten. Im folgenden werden Teilbäume einer bestimmten Höhe einfach mit eckigen Klammern angegeben. Hier ein Beispiel einer Rotation:
--(A)-- --(B)--
/ \_ _/ \
(B) [Z] =ROR= [X] (A)
_/ \_ [_] [ ] _/ \_
[X] [Y] [ ] [Y] [Z]
[ ] [_] [_] [_] [_]
[ ]
[_]
Wie man sieht, wurden die beiden Knoten A und B nach rechts rotiert (ROtate Right). B hat dabei den Platz von A eingenommen, den ehemals rechten Teilbaum Y von B jedoch an den linken Platz von A übergeben. Dass dies möglich ist zeigt folgende Überlegung:
Sei der Knoten, an dem der Teilbaum Y hängt der Knoten Y. Vor der Rotation ist gegeben, dass der Wert von Y grösser ist als der Wert von B (Definition eines Binärbaums). Nach der Rotation befindet sich der Teilbaum immer noch rechts vom Konten B, ist also immer noch grösser (was natürlich auch so sein sollte, denn am Teilbaum selbst wurde ja nichts verändert). Betrachtet man den Knoten Y vom Knoten A aus, so steht dieser vor der Rotation links von A und nach der Rotation ebenfalls. Die Voraussetzung für einen geordneten Binärbaum bleibt also auf jeden Fall bestehen.
Man kann sich leicht ausmahlen, dass die links-Rotation (ROtate Left) äquivalent funktioniert.
Gerade bei diesem Beispiel kann man auch schön beobachten, was so eine Rotation bewirken kann. Vor der Rotation war der Baum linkslastig, nach der Rotation jedoch ausgeglichen. Hier nochmals das gleiche Beispiel, diesmal jedoch mit den Balance-Werten:
--(-2)-- --(0)--
/ \_ _/ \
(-1) [Z] =ROR= [X] (0)
_/ \_ [_] [ ] _/ \_
[X] [Y] [ ] [Y] [Z]
___[ ]____[_]_______________[_]____[_]___[_]___
[ ]
[_]
Visuell kann man die Ausgeglichenheit auch sehen, indem man die unteren Ränder der Teilbäume betrachtet: links sind sie stark unterschiedlich, wogegen rechts alle auf der selben Höhe enden.
Diese wenigen Grundlagen reichen nun aus, um die AVL-Bäume vollständig zu betrachten. Konkret heisst das, dass für alle möglichen Fälle, die bei einer Einfüge- oder Lösch-Operation auftreten können, eine Folge von Rotationen hergeleitet werden muss, um die Invariante eines AVL-Baumes wiederherzustellen.
Einfügen
Zuerst betrachtet man die Einfüge-Operation. Ein Element, das neu eingefügt wurde, wird immer als ein Blatt neu im Baum vorhanden sein. Man betrachtet nun allgemein alle Fälle, in dem ein Blatt in einem Teilbaum hinzugekommen ist. Das neue Element wird dabei mit # gekennzeichnet (Immer zwei Zeilen entsprechen einer Höhenstufe). Probleme gibt es grundsätzlich nur dann, wenn durch das Einfügen ein Teilbaum eines Knotens plötzlich grösser geworden ist als erlaubt. Was also betrachtet werden muss, sind die Eltern-Knoten von Teilbäumen.
Wird im linken Teilbaum eines Elternknotens ein Element eingefügt, so sind folgende Fälle trivial: Der Elternknoten ist rechtslastig (+1) und der Elternknoten ist ausgeglichen (0):
(+1) (0)
_/ \_ _/ \_
[X] [Y] [X] [Y]
[_] [ ] wird zu [ ] [ ]
# [ ] [#] [ ]
___ # ____[_]___________[#]___[_]___
Höhe unverändert
(0) (-1)
_/ \_ _/ \_
[X] [Y] [X] [Y]
___[_]___[_]_ wird zu _[ ]____[_]___
# [#]
# [#]
Höhe +1
Dazu gibt es natürlich auch die Seitenverkehrten Pendants (Neues Element wird in rechtem Teilbaum eingefügt). Beim ersteren Fall sieht man zusätzlich, dass nun die Höhe des Teilbaumen, der im Elternknoten verwurzelt ist, um 1 gestiegen ist. Dies bedeutet, dass man nun auch für den noch höheren Eltern-Knoten dieselbe Überprüfung machen muss (Auf keinen Fall vergessen!).
Problematischer wird es beim dritten Fall: Der Elternknoten ist linkslastig.
(-1) (-2)
_/ \_ _/ \_
[ ] [ ] [ ] [ ]
[ ] [_] wird zu [ ] [_]
[ ] [ ]
___[_]__________________[ ]__________
# [#]
# [#]
Um dieses Problem zu lösen, muss der linke Teilbaum weiter aufgesplittet werden. Dabei gibt es 3 verschiedene Möglichkeiten, die man in Betracht ziehen muss. Um die Sache etwas zu beschleunigen, hier sogleich die Auflösungen:
1:
--(-1)-- --(-2)--
/ \_ / \_
(0) [Z] (-1) [Z]
_/ \_ [_] wird zu _/ \_ [_]
[X] [Y] [X] [Y]
___[_]___[_]__________________[ ]____[_]________
# [#]
# [#]
--(0)--
_/ \
[X] (0)
=ROR= [ ] _/ \_
[#] [Y] [Z]
_________[#]____[_]___[_]___
Höhe unverändert
Dies entspricht dem Beispiel oben. Durch eine einfache rechts-Rotation kann der Teilbaum vollständig "repariert" werden.
2:
----(-1)---- ----(-2)----
/ \_ / \_
(0)---- [Z] (+1)---- [Z]
_/ \ [ ] wird zu _/ \ [ ]
[W] (0) [ ] [W] (-1) [ ]
[ ] _/ \_ [_] [ ] _/ \_ [_]
[ ] [X] [Y] [ ] [X] [Y]
___[_]___[_]___[_]________________[_]____[ ]____[_]_____
# [#]
# [#]
-(-2)- ---(0)---
/ \_ / \
--(-2) [Z] (0) (+1)
=ROL= / \_ [ ] =ROR= _/ \_ _/ \_
(0) [Y] [ ] [W] [X] [Y] [Z]
_/ \_ [_] [_] [ ] [ ] [_] [ ]
[W] [X] [ ] [#] [ ]
________[ ]___[ ]______________________[_]___[#]__________[_]___
[ ] [#] Höhe unverändert.
[_] [#]
Hier wird zuerst mit den beiden unteren Knoten eine links-Rotation ausgeführt und dann mit den beiden oberen eine rechts-Rotation.
3:
----(-1)---- ----(-2)----
/ \_ / \_
(0)---- [Z] (+1)---- [Z]
_/ \ [ ] wird zu _/ \ [ ]
[W] (0) [ ] [W] (+1) [ ]
[ ] _/ \_ [_] [ ] _/ \_ [_]
[ ] [X] [Y] [ ] [X] [Y]
___[_]___[_]___[_]_________________[_]____[_]____[ ]_____
# [#]
# [#]
-(-2) ---(0)---
/ \_ / \
--(-1) [Z] (-1) (0)
=ROL= / \_ [ ] =ROR= _/ \_ _/ \_
(-1) [Y] [ ] [W] [X] [Y] [Z]
_/ \_ [ ] [_] [ ] [_] [ ] [ ]
[W] [X] [#] [ ] [#] [ ]
________[ ]____[_]___[#]____________[_]__________[#]___[_]___
[ ] Höhe unverändert
[_]
Auch in diesem Fall muss zuerst eine links-Rotation durchgeführt werden und anschliessend eine rechts-Rotation.
Dies waren bereits alle Fälle für das Einfügen. Nachträglich nochmals der Hinweis auf den allerersten Fall, welcher der einzige war, bei dem die Höhe sich änderte. Also muss nur falls der Elternknoten eine Balance 0 hatte der Baum rekursiv nach oben traversiert werden. Für alle anderen Fälle ist nach den ein oder zwei Rotationen Schluss.
Löschen:
Das Löschen eines Knotens ist in etwa ähnlich kompliziert. Im folgenden wird der zu löschende Knoten ebenfalls mit ## bezeichnet. Folgendes sind die einfachen Fälle:
(-1) (0)
_/ \_ _/ \_
[X] [Y] wird zu [X] [Y]
[ ] [_] [_] [_]
[#] Höhe um 1 verringert
___[#]______________________________
(0) (+1)
_/ \_ _/ \_
[X] [Y] [X] [Y]
[ ] [ ] wird zu [_] [ ]
[#] [ ] [ ]
___[#]___[_]__________________[_]___
Höhe unverändert
Für den folgenden Fall muss wie oben der linke Teilbaum aufgesplittet werden:
(+1) (+2)
_/ \_ _/ \_
[ ] [ ] [ ] [ ]
[ ] [ ] [_] [ ]
[#] [ ] wird zu [ ]
[#] [ ] [ ]
[ ] [ ]
__________[_]___________________[_]___
Die ersten beiden Fälle ist noch relativ einfach:
1:
--(+1)-- --(+2)--
_/ \ _/ \
[X] (0) [X] (0)
[ ] _/ \_ wird zu [_] _/ \_
[#] [Y] [Z] [Y] [Z]
[#] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ]
___________[_]___[_]___________________[_]___[_]
--(-1)--
/ \_
(+1) [Z]
=ROL= _/ \_ [ ]
[X] [Y] [ ]
[_] [ ] [_]
[ ]
__________________[_]___________
Höhe unverändert
2:
--(+1)-- --(+2)--
_/ \ _/ \
[X] (+1) [X] (+1)
[ ] _/ \_ wird zu [_] _/ \_
[#] [Y] [Z] [Y] [Z]
[#] [_] [ ] [_] [ ]
[ ] [ ]
_________________[_]__________________________[_]
--(0)--
/ \_
(0) [Z]
=ROL= _/ \_ [ ]
[X] [Y] [ ]
[_] [_] [_]
Höhe um 1 verringert
___________________________
Wie man sieht, wird beim zweiten Fall die Höhe wiederum um 1 verringert. Dies passiert auch beim letzten Fall, alllerding sind hier zwei Rotationen notwendig:
--(+1)-- --(+2)--
_/ \ _/ \
[W] (-1)- wird zu [W] (-1)-
[ ] / \_ [_] / \_
[#] (?) [Z] (?) [Z]
[#] _/ \_ [_] _/ \_ [_]
[X] [Y] [X] [Y]
________[_]___[_]_____________________[_]___[_]_____
-(+2)- --(0)--
_/ \ / \
=ROR= [W] (?) =ROL= (?) (?)
[_] _/ \ _/ \_ _/ \_
[X] (?) [W] [X] [Y] [Z]
[_] _/ \_ [_] [_] [_] [_]
[Y] [Z] Höhe um 1 verringert
______________________[_]___[_]_________________________________
Mit dem Fragezeichen ist gemeint, dass rotationsmässig nicht darauf ankommt, wie die Balance an diesem Knoten ist. Er wurde hier einfach durch den Fall 0 representiert. Trotzdem müssen die Werte schlussendlich stimmen. Folgendes sind die Werte, die bei dem linken und rechten Fragezeichne stehen müssen:
ursprünglich links rechts (-1) (0) (+1) (0) (0) (0) (+1) (-1) (0)
Der aufmerksamen Leserin wird wahrscheinlich nicht entgangen sein, dass eine Einfüge-Operation die Höhe des Baumes tatsächlich nur dann beeinträchtigt, wenn der betroffene Teilbaum ausgeglichen ist, sprich, wenn es gar keine andere Möglichkeit mehr gibt, als den Teilbaum zu erweitern. Im Gegensatz dazu wird bei einer Lösch-Operation der Teilbaum immer so angeordnet, dass der Teilbaum nach der Operation optimal ist. Falls also die Möglichkeit existiert, die Höhe zu verringern, wird dies auch gemacht.
Implementation:
Mit diesem Grundwissen über die Funktionalität der AVL-Bäume ist es nicht mehr schwierig, einen entsprechenden Algorithmus zu kreieren, allerdings muss peinlichst genau darauf geachtet werden, dass alle Fälle richtig bearbeitet werden. Für das Einfügen und das Löschen muss jeweils der Vaterknoten (im folgenden stets als A bezeichnet) bekannt sein. Des weiteren wird im Folgenden der Teilbaum, der verändert wurde stets als X bezeichnet (was gleichbedeutend ist mit dem Knoten X, der den Teilbaum bildet). Auf den ersten Blick mag die Implementierung komplett anders aussehen als oben beschrieben, sie stimmt jedoch genau überein. Hier nochmals alle Fälle (links- und rechts-gerichtet) aufgelistet, wobei diese Funktion aufgerufen wird, nachdem der neue Knoten eingefügt bzw gelöscht wurde:
Einfügen(Knoten A, Teilbaum X)
//Einfacher Fall
IF A==(+1) AND X==linkerTeilbaum(A) THEN A:=(0);
//Einfacher Fall
ELSEIF A==(-1) AND X==rechterTeilbaum(A) THEN A:=(0);
//Einfacher Fall, Rekursiver Aufruf wegen Höhenveränderung
ELSEIF A==(0) AND X==linkerTeilbaum(A) THEN A:=(-1); Einfügen(Vater(A),A);
//Einfacher Fall, Rekursiver Aufruf wegen Höhenveränderung
ELSEIF A==(0) AND X==rechterTeilbaum(A) THEN A:=(+1); Einfügen(Vater(A),A);
ELSEIF A==(-1) AND X==linkerTeilbaum(A) THEN
//Fall 1
IF X==(-1) THEN ROR(X,A); X:=(0); A:=(0);
ELSE
R:=rechterTeilbaum(X);
//Doppelrotation
ROL(X,R); ROR(R,A);
//Fall 2
IF R==(-1) THEN R:=(0); X:=(0); A:=(+1)
//Fall 3
ELSE R:=(0); X:=(-1); A:=(0);
ENDIF
ELSE
//Fall 1
IF X==(+1) THEN ROL(X,A); X:=(0); A:=(0);
ELSE
L:=linkerTeilbaum(X);
//Doppelrotation
ROR(X,L); ROL(L,A);
//Fall 2
IF L==(+1) THEN L:=(0); X:=(0); A:=(-1)
//Fall 3
ELSE L:=(0); X:=(+1); A:=(0);
ENDIF
ENDIF
Löschen(Knoten A, Teilbaum X)
//Einfacher Fall, Rekursiver Aufruf wegen Höhenveränderung
IF A==(-1) AND X==linkerTeilbaum(A) THEN A:=(0); Löschen(Vater(A),A)
//Einfacher Fall, Rekursiver Aufruf wegen Höhenveränderung
ELSEIF A==(+1) AND X==rechterTeilbaum(A) THEN A:=(0); Löschen(Vater(A),A)
//Einfacher Fall
ELSEIF A==(0) AND X==linkerTeilbaum(A) THEN A:=(+1);
//Einfacher Fall
ELSEIF A==(0) AND X==rechterTeilbaum(A) THEN A:=(-1);
ELSEIF A==(+1) AND X==linkerTeilbaum(A) THEN
R:=rechterTeilbaum(A);
IF R==(-1) THEN
L:=linkerTeilbaum(R);
//Doppelrotation für Fall 3
ROR(L,R); ROL(L,A);
IF L==(-1) THEN A:=(0);L:=(0);R:=(+1)
//Anpassung der Knotenbalance
ELSEIF L==(0) THEN A:=(0);L:=(0);R:=(0)
ELSE A:=(-1);L:=(0);R:=(0)
Löschen(Vater(A),A);
ELSE
ROL(A,R);
//Fall 1
IF R==(0) THEN A:=(+1);R:=(-1);
//Fall 2
ELSE A:=(0);R:=(0);Löschen(Vater(A),A);
ENDIF
ELSE
L:=linkerTeilbaum(A);
IF L==(+1) THEN
R:=rechterTeilbaum(L);
//Doppelrotation für Fall 3
ROL(R,L); ROR(R,A);
IF R==(+1) THEN A:=(0);R:=(0);L:=(-1)
//Anpassung der Knotenbalance
ELSEIF R==(0) THEN A:=(0);R:=(0);L:=(0)
ELSE A:=(+1);R:=(0);L:=(0)
Löschen(Vater(A),A);
ELSE
ROR(A,L);
//Fall 1
IF L==(0) THEN A:=(-1);R:=(+1);
//Fall 2
ELSE A:=(0);L:=(0);Löschen(Vater(A),A);
ENDIF
ENDIF