AVL-Baum

Ein AVL-Baum ist in der Informatik eine Datenstruktur, genauer ein balancierter binärer Suchbaum, bei dem für jeden Knoten k die Höhen h der beiden Teilbäume sich um höchstens 1 unterscheiden. Da der Baum so nicht aus der Balance geraten kann, nennt man ihn auch häufig "ausgeglichener Baum". Die Höhe eines AVL-Baums mit n Knoten liegt in O(log n) und somit 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.

Inhaltsverzeichnis
1 Operationen
2 Rebalancierung
3 Implementierung
4 Weblinks
5 Literatur

Operationen

Ein AVL-Baum stellt die Operationen

zur Verfügung. Die Operationen haben, richtig implementiert, im schlechtesten Fall ebenfalls eine asymptotische Laufzeit von O(logn).

Rebalancierung

Wird nach einer Einfüge- oder Löschoperation festgestellt, dass der AVL-Baum außer Balance geraten ist, so wird eine spezielle Rebalancierungsoperation angewandt. Es lassen sich zwei Fälle unterscheiden, die man als einfache Rotation und Doppelrotation bezeichnet. Die einfache Rotation wird durch die folgende Grafik an einem Beispiel veranschaulicht: center Man erkennt zunächst, dass der Höhenunterschied der beiden Teilbäume des Knotens x gleich 2 und damit der Baum aus der Balance ist. Durch die Rotation soll die Balance wiederhergestellt werden. Im vorliegenden Fall ist eine Rotation gegen den Uhrzeigersinn nötig. Bei der Rotation wird der Knoten y um eine Ebene erhöht und x um eine erniedrigt. Der Teilbaum B wird von y entfernt (seine Stelle wird ja nun von x eingenommen) und zu x hinzugefügt (da y nun zu dessen Vater geworden ist, hat x einen Teilbaum frei). Damit ist die Balance wiederhergestellt.

Die Doppelrotation kommt in schwierigeren Fällen zum Einsatz, in denen eine einfache Rotation nicht ausreichen würde, um zu einer Balance zu gelangen. Nach einer Einfügung reicht in jedem Fall eine einzige Rotation oder Doppelrotation aus, um die Invariante des AVL-Baums wieder zu erfüllen. Nach einer Löschoperation können ggf. mehrere Rebalancierungen vom jeweiligen Teilbaum aus bis hinauf zur Wurzel notwendig sein.

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 nach folgender Formel: -1 * ("Tiefe des linken Baums") + ("Tiefe des rechten Baums"), oder auch ("Tiefe des rechten Baums") - ("Tiefe des linken Baums"). Er beträgt also 0 wenn der Knoten ausgeglichen ist (heißt linker und rechter Teilbaum gleichtief sind), +1 wenn der rechte Teilbaum tiefer als der linke ist und -1 wenn der linke Teilbaum tiefer als der rechte Teilbaum ist. Sobald ein Balancegrad von > +1 oder < -1 erreicht ist sind Rotationen erforderlich.

Nach jedem Einfügen oder Löschen eines Knotens wird in all seinen Vorgängern bis zur Wurzel überprüft, ob nun die Balancierungsbedingung verletzt ist. Dies geschieht auf dem "Rückweg" der rekursiven Aufruffolge, es ist also nicht notwendig, einen separaten Prüf- und Korrekturlauf zu implementieren.

Ist an einem Knoten die Bedingung nicht mehr erfüllt, kann sie durch wenige Umordnungen von Kanten am betreffenden Knoten, seinem Vorgänger und den beiden Nachfolgern wieder hergestellt werden. Sämtliche auftretenden Fälle (z.B. linker Teilbaum war vorher schon höher und ist nun noch höher geworden) lassen sich vorweg erfassen und programmieren.

Weblinks

Literatur

See also: AVL-Baum, Asymptotische Laufzeit, Balancierter Baum, Binärer Suchbaum, Datenstruktur, Informatik, Landau-Symbole, Worst Case