AVL-Baum

Ein AVL-Baum ist eine Datenstruktur in der Informatik, genauer ein balancierter binärer Suchbaum. Als Invariante beim AVL-Baum gilt, dass sich für jeden Knoten k die Höhen $h_{1}$ und $h_{2}$ der beiden Teilbäume um höchstens 1 unterscheiden. Da diese Bedingung verhindert, dass der Baum aus der Balance gerät, nennt man ihn auch „ausgeglichen“. Die Höhe eines AVL-Baums mit n Knoten liegt in O(log n) und damit auch die maximale Anzahl der Schritte, um ein Element zu finden oder festzustellen, dass es nicht enthalten ist.

Der Name AVL leitet sich von den Erfindern Adelson-Velskii und Landis ab.

Operationen

Die folgenden Operationen sind auf einem AVL-Baum effizient mit Komplexität O(log n) ausführbar:

insert: Einfügen eines Elementes
remove: Entfernen eines Elementes
find: Suchen eines Elementes

find

Die find-Operation ist im AVL-Baum die einfachste aller Operationen, und wird als Subset in der insert-Operation als auch in der remove-Operation gebraucht. Daher wird sie hier zuerst diskutiert. Da der Suchbaum jederzeit so sortiert ist, daß rechts eines Knoten nur Knoten mit größeren Schlüsseln, und links vom Knoten nur Knoten mit kleineren (oder gleich grossen) Schlüsseln gespeichert sind, findet man einen Schlüssel, indem man von der Wurzel des Baumes schrittweise nach unten wandert, und dabei jeweils nach rechts abbiegt, falls der gesuchte Schlüssel größer als der des aktuellen Knotens ist oder links wenn er kleiner ist. Stimmt der Schlüssel überein, hat man ihn gefunden, erreicht man ein Blatt, dessen Schlüssel nicht passt, ist garantiert, daß der Schlüssel nicht im Baum existiert.

insert

Die insert-Operation versucht zuerst den Schlüssel mit der find-Operation zu finden. Scheitert dies, so ist das passende Blatt bekannt, das jetzt zum Knoten wird. An diesem wird der neue Schlüssel als Blatt aufgehängt. Beim Rücksprung aus der rekursiven find-Funktion wird geprüft, ob der Baum rebalanciert werden muß, und dies ggf. durchgeführt (s.u.).

remove

Die remove-Operation sucht zuerst den Schlüssel wie die find-Operation und entfernt dann den entsprechenden Knoten. War es ein Blatt, geht es im Rücksprung des Rekursivaufrufs mit dem Rebalancieren weiter (s.u.), sonst müssen die beiden frei gewordenen Teilbäume neu aufgehängt werden. Dies wird realisiert, indem entweder der rechte Teilbaum bis zum linkesten Blatt hochgewandert wird, oder der linke Teilbaum bis zum rechtesten Blatt. Dieses Blatt wird dann benutzt, um die beiden Teilbäume daran wieder aufzuhängen. Das Blatt nimmt den Platz des gelöschten Knotens ein. Im nun folgenden Rücksprung werden die ggf. nötigen Rebalancierungen durchgeführt.

Rebalancierung

Würde eine Einfüge- oder Löschoperation die Balance zerstören, wird zusätzlich eine Rebalancierung durchgeführt. Es lassen sich zwei Fälle unterscheiden, die man als einfache Rotation und Doppelrotation bezeichnet.

Einfache Rotation

Die nebenstehende Abbildung zeigt eine einfache Rotation. Auf der linken Seite ergibt sich nach einer Einfügung ein Höhenunterschied von zwei bei den beiden Teilbäumen von Knoten x. Da dieser Baum nicht mehr balanciert wäre, muss eine Rebalancierung durchgeführt werden. Das Ergebnis dieser Operation ist auf der rechten Seite der Abbildung gezeigt.

Die Rebalancierung ändert lokal die Baumstruktur unter Beibehaltung der Sortierungsbedingung. Dazu werden einzelne Knoten und Teilbäume in der Hierarchie angehoben und andere abgesenkt. Dies ist in der Abbildung durch senkrechte rote Pfeile dargestellt. Obwohl bei der Rebalancierung keine Seitwärtsverschiebungen stattfindet, wird diese Operation als Rotation bezeichnet. Bei der gezeigten Rotation nach links (gegen den Uhrzeigersinn) wird Knoten y und Teilbaum $t_{3}$ um eine Ebene erhöht und Knoten x und Teilbaum $t_{1}$ um eine abgesenkt. Die Verknüpfungen werden entsprechend angepasst, so dass Teilbaum t2 seinen Vaterknoten von y zu x wechselt und Knoten x und y ihre Position in der Hierarchie tauschen. Im resultierenden Baum ist die Balance wieder hergestellt. Zur dargestellten Rotation nach links, die den Teilbaum links außen absenkt und dafür den Teilbaum rechts außen erhöht, existiert eine spiegelbildliche Variante, die in einer Rotation nach rechts den linken Teilbaum erhöht und dafür den rechten absenkt.

Doppelrotation

Die in Abbildung 2 gezeigte Situation unterscheidet sich von der aus Abbildung 1 darin, dass die problematische Höhendifferenz zwischen dem linken Teilbaum $t_{1}$ und dem mittleren Teilbaum (mit Wurzel z) auftritt. Daher kann eine einfache Rotation wie in Abbildung 1, die den linken Teilbaum absenkt und dafür den rechten anhebt, keine Abhilfe schaffen. Die Doppelrotation, deren Ergebnis auf der rechten Seite von Abbildung 2 gezeigt ist, hebt den mittleren Teilbaum um eine Ebene an und senkt dafür den linken um eine Ebene ab. Dazu wird der Wurzelknoten z des mittleren Teilbaumes um zwei Ebenen erhöht und wird neuer Vaterknoten von x und y. Die dadurch entstehenden freien Teilbäume $t_{2}$ und $t_{3}$ werden an die Knoten x und y aufgeteilt. Auch bei der sog. Doppelrotation geschehen keine Seitwärtsverschiebungen, wodurch die Sortierreihenfolge der Knoten im AVL-Baum erhalten bleibt. Auch von der Doppelrotation existiert eine spiegelbildliche Variante, die ebenfalls den mittleren Teilbaum erhöht, dafür aber den rechten absenkt.

Nach einer Einfügung kann die Balance immer mit einer Rotationsoperation wiederhergestellt werden. Nach einer Löschoperation können mehrere Rebalancierungen vom jeweiligen Teilbaum aus bis hinauf zur Wurzel notwendig sein, um die Balance wiederherzustellen.

Implementierung

Jeder Knoten des Baums muss neben dem Schlüssel einen Balance-Wert speichern, der angibt ob der Baum links- oder rechtslastig ist. Der Balancegrad eines Knotens k berechnet sich aus ("Höhe des rechten Teilbaums") - ("Höhe des linken Teilbaums"). Er beträgt 0, wenn der Knoten ausgeglichen ist (also linker und rechter Teilbaum gleich tief sind); er ist positiv, wenn der rechte Teilbaum tiefer als der Linke ist und negativ, wenn der Linke tiefer als der Rechte ist. Bei einem Balance-Wert größer 1 oder kleiner -1 ist eine Rotation erforderlich.

Nach jedem Einfügen oder Löschen eines Knotens wird in allen seinen Vorgängern bis zur Wurzel der Balance-Wert angepasst und die Balancierung überprüft. Dies geschieht auf dem "Rückweg" der rekursiven Aufruffolge, was einen separaten Prüf- und Korrekturlauf überflüssig macht. Eine Rotation benötigt nur eine konstante Anzahl von Verknüpfungsänderungen am betreffenden Knoten, seinem Vorgänger und den beiden Nachfolgern.

Siehe auch

Rot-Schwarz-Baum

Weblinks

http://www.informatiktreff.de/materialien/sek_ii/algorithmen/avl/avlbaum.htm Ausführlichere Beschreibung
http://alfi.ira.uka.de/lehre/sommer2002/AVLTreeApplet/avl.html Java Applet zum Durchspielen verschiedener Szenarien
http://www-lehre.informatik.uni-osnabrueck.de/~ainf/2000/skript/node60.html Gute kurzgehaltene Beschreibung
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm Noch ein Java Applet mit Animation
http://www.binarytreesome.com/applets/latest/applet.html Ein sehr gutes Applet mit Animation (besonders zum interaktiven erlernen der Algorithmen)

Literatur

Udi Manber, Introduction to Algorithms -- A Creative Approach, 1989, Kapitel 4.3.4, S.75ff, Addison-Wesley Publishing Company