AVL Baum
In unserem Video erfährst du schnell und einfach, wie du einen AVL Baum mittels Rotation trotz Einfügen und Löschen balanciert halten kannst, ohne dafür viel unnötigen Text zu lesen!
In unserem Blogbeitrag findest du alle wichtigen Informationen über AVL Bäume und den Balance Faktor, welches du eventuell auch unter dem Namen AVL-Kriterium oder AVL-Bedingung kennst. Danach findest du AVL Baum Aufgaben zu allen wichtigen Operationen: AVL Baum einfügen, AVL Baum löschen, sowie die AVL Baum Rotationen Einfachrotation und Doppelrotation.
Inhaltsübersicht
AVL Bäume
Die AVL Bäume (engl. avl tree) wurden ursprünglich von den russischen Mathematikern Georgi Maximowitsch Adelson-Velskii und Jewgeni Michailowitsch Landis entwickelt und gehören angesichts ihrer Struktur zum Typ Baum (Informatik).
Ein binärer Suchbaum unterscheidet sich von AVL Bäumen vor allem dadurch, dass durch die Verwendung der Balance-Bedingung verhindert werden kann, dass die Bäume nicht zu einer Liste bzw. zu rechts-/ linkslastigen Bäumen werden. Durch diese Balance wird das Navigieren durch den Baum, zum Beispiel das Suchen einer Zahl, stark optimiert.
Will man in dem obigen Beispiel die 42 suchen, müsste man im linken Baum jedes Element betrachten und damit allein schon sechs Überprüfungen vornehmen. Im rechten Baum reichen allein drei Schritte zur Überprüfung.
Balance-Faktor
Für AVL Bäume müssen die entsprechenden Höhen der einzelnen Teilbäume festgehalten werden. Dafür wird der Balance-Faktor BF verwendet. Dieser definiert sich ganz einfach als Höhe des rechten Teilbaums minus Höhe des linken Teilbaums, also gilt:
Balance Faktor = Höhe(rechter Teilbaum) – Höhe(linker Teilbaum)
Die Balance-Faktoren des folgenden Beispielbaums kann so direkt bestimmt werden. Begonnen wird dabei immer von den Blättern in Richtung Wurzel. Die Blätter 2, 15 und 42 haben dabei einen Faktor von 0, denn Blätter haben keine Kinder. Eine Stufe darüber ist rechts die 24. Dabei wird die Höhe der Teilbäume – also jeweils 1 – voneinander abgezogen. Dadurch erhält man ebenfalls den Wert 0. Bei der 3 auf der linken Seite ergibt sich entsprechen 0 minus 1, also -1. Für die Wurzel gilt schließlich 2 minus 2, also ebenfalls 0. Bei dem Baum handelt es sich also um einen AVL-Baum, weil der maximale Höhenunterschied 1 beziehungsweise -1 beträgt, da für die AVL-Bedingung gilt:
In unserem Video zum Binärbaum , gibt es alle wichtigen Informationen bezüglich Höhe, Stufe oder Traversierung!
Rekursiver Algorithmus: Balance-Kriterium
Der folgende rekursive Algorithmus testet, ob die Balance-Bedingung tatsächlich erfüllt ist.
algorithm istbalanciert (T: tree) :bool
begin
if istleer(t) then
return true;
else
return [istbalanciert(T.links) and istbalanciert(T.rechts)
and |hoehe(t.links) – hoehe(t.rechts) |<=1]
FI
end;
AVL Baum Aufgaben: Verschiedene Operationen
An AVL Bäumen können natürlich verschiedene Operationen vorgenommen werden. Man kann einen AVL Baum erstellen und dabei Elemente einfügen und löschen ohne oder mit Rotation.
Für die einzelnen Operationen findest du im Folgenden verschiedene AVL Baum Aufgaben.
AVL Baum Einfügen
Beim Einfügen wird ein Blatt durch den inneren Knoten mit einem Schlüssel ersetzt. Dadurch kann es passieren, dass der dadurch entstehende Suchbaum nicht mehr AVL-Baum ausgeglichen ist. Deshalb muss überprüft werden, ob die Höhendifferenz von maximal 1 weiterhin gegeben ist. Ist das der Fall, liegt eine einfache AVL-Baum-Einfügen-Operation vor.
Beispiel
Gegeben sei beispielsweise der folgende Baum. Die Knoten C und D haben keine Nachfolger, daher ist der Balance-Faktor für beide Knoten 0. Anders sieht es beim Knoten B aus: der linke Teilbaum hat die Höhe von 1, und der rechte Teilbaum eine Höhe von 0. Wir addieren also die negative Höhe des linken Teilbaums zur positiven Höhe des rechten Teilbaums und erhalten den Wert -1. Nun zum Knoten A. Der linke Teilbaum hat eine Höhe von 2, der rechte Teilbaum die Höhe 1. Addiert man also die Zahlen minus 2 und 1 ergibt das -1. Super! Der Betrag des Balance-Faktor keines Knoten ist größer als eins, der Baum ist also balanciert!
Im Beispiel wird jetzt der Knoten E einfügt. Deshalb muss im nächsten Schritt der Balance-Faktor neu berechnet werden. Da sich der Balance-Faktor dadurch nicht verändert hat, ist der Baum immer noch balanciert!
AVL Baum Löschen
Als weitere Möglichkeit neben dem Einfügen, kann zusätzlich auch eine AVL-Baum-Löschen-Operation ausgeführt werden. Dabei muss im Gegensatz zum Einfügen, folglich einfach ein Element aus dem Baum entfernt werden. Danach wird wieder überprüft, ob das AVL-Kriterium weiterhin erfüllt, also die Balance weiterhin vorhanden ist.
AVL Baum Rotation
Sollte durch das Einfügen der Balance-Faktor nicht erhalten bleiben, muss mittels vier verschiedener Möglichkeiten reagiert werden. Diese Varianten werden im Allgemeinen AVL Baum Rotation genannt. Diese können entweder einfach oder doppelt verwendetet werden.
Wenn die Lastigkeit auf Grund des linken Teilbaums herrscht, muss eine einfache Rechts-Rotation durchgeführt werden. Ist durch das Einfügen eines Werts ein Ungleichgewicht wegen des rechten Teilbaums, muss eine einfache Linksrotation ausgeführt werden.
In manchen Fällen, reicht aber eine einfache Rotation nicht aus. Dies ist der Fall, wenn zum einen der Balance-Faktor nicht gegeben ist und der Teilbaum in die entgegengesetzte Richtung verläuft, als sein eingefügtes Kind.
Fallunterscheidung
Das AVL-Kriterium wird verletzt und muss durch eine einfache Rotation behandelt werden, wenn
- in einen linken Teilbaum ein linkes Kind eingefügt wird (einfache Rechtsrotation)
- oder in einen rechten Teilbaum ein rechtes Kind hinzugefügt wird (einfache Linksrotation).
Der Balance-Faktor muss durch eine doppelte Rotation kuriert werden, um sein Symmetrie Problem zu lösen, wenn
- in einen linken Teilbaum ein rechtes Kind eingefügt wird (Links-Rechts-Rotation)
- oder in einen rechten Teilbaum ein linkes Kind hinzugefügt wird (Rechts-Links-Rotation).
Hier siehst du eine Übersicht, an der du dich orientieren kannst, wann du welche AVL Baum Rotationen vornehmen musst:
| Rotation | BF Oberer Knoten | BF Unterer Knoten |
| Rechts-Rotation | -2 | -1 |
| Links-Rotation | +2 | +1 |
| Rechts-Links-Rotation | +2 | -1 |
| Links-Rechts-Rotation | -2 | +1 |
AVL Baum Übung: Einfachrotation
Aber jetzt zu den richtigen AVL Baum Aufgaben! Gegeben sei dafür der folgende Baum, zu dem der Wert 1 eingefügt werden soll. Bei der Bestimmung der neuen Balance-Faktoren erhält man für die 1 eine 0, für die 2 eine -1, für die 3 eine -2 und für die Wurzel eine -1. Mit -2 ist die AVL-Bedingung also verletzt und der Baum muss entsprechend umgebaut werden. Das geschieht mit einer sogenannten Rechtsrotation des Knotens, der die Bedingung verletzt und desjenigen darunter. In diesem Fall müssen also die 2 und die 3 nach rechts rotieren: Die 2 wird dadurch zum Elternknoten und die 3 zum rechten Kindknoten. Durch die einfache AVL Baum Rotation nach rechts ist der Baum wieder balanciert.
Wenn nun die 15 gelöscht wird und eine 73 einfügt, dann ergibt sich ein Balance-Faktor von +2 bei der 24. Diesmal hilft eine Linksrotation, die aber zum Glück nach demselben Prinzip wie die Rechtsrotation funktioniert. Nur eben in die andere Richtung. Die 42 rückt nach links oben und wird zum Elternknoten und die 24 rutscht dabei nach links unten und wird zum Kind.
AVL Baum Übung: Doppelrotation
Leider gibt es auch ein wenig kompliziertere Fälle. Löscht man zunächst die 1 und die 3 aus unserem Baum, ergibt sich kein Problem. Doch was ist, wenn jetzt noch die 15 eingefügt wird? Daraus ergibt sich ein BF von +2, welcher die AVL-Bedingung verletzt. Der rechte Kindknoten hat dagegen eine -1. In diesem Fall muss bezüglich der Fallunterscheidung eine Rechts-Links-Rotation vorgenommen werden.
Zuerst wird eine Rechtsrotation mit der 24 durchgeführt. Danach folgt dann die Linksrotation des oberen Knotens – also der Wurzel 7 – mit dem neuen Kindknoten 24. Doch jetzt hätte die 24 ja drei Kinder, was in einem Binärbaum nicht möglich ist! Kein Problem. Das mittlere Kind – die 15 – wird einfach als Enkelknoten der Wurzel an die linke Seite unter die 7 umgehängt und sind fertig. Sehr schön. Der Baum ist wieder balanciert.
Laufzeit
Die Laufzeit bzw. Komplexität von AVL-Bäumen ist abhängig von den verschiedenen Operationen:
| Average-Case | Worst-Case | |
| Suchen |  |
|
| Einfügen |  |
|
| Löschen | |
|