AVL-Baum

Ein AVL-Baum ist eine Datenstruktur aus der Informatik, genauer ein binärer Suchbaum, bei dem für jeden Knoten gilt, dass sich die Höhe des linken Teilbaums und die Höhe des rechten Teilbaums maximal um 1 unterscheiden. Der Name AVL leitet sich von den Erfindern Adelson-Velskii und Landis ab.

Diese Bedingung ist schwächer als die Forderung nach vollständiger Balanciertheit, stellt aber trotzdem sicher, dass der Baum nicht zu einer linearen Liste ausarten kann.

Operationen

Ein AVL-Baum stellt die Operationen

• insert, zum Einfügen eines Elementes,
• remove, zum Entfernen eines Elementes und
• find, zum suchen eines Elementes im Baum

zur Verfügung. Die Operationen sind dabei alle mit der Worst-Case-Laufzeit O(logn) implementierbar.

Implementation

Nach jedem Einfügen oder Löschen eines Knotens wird in all seinen Vorgängern bis zur Wurzel überprüft, ob nun die AVL-Bedingung 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. Dazu ist es allerdings notwendig, in jedem Knoten die Zusatzinformation zu speichern, welcher seiner beiden Teilbäume höher ist. 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.

Beim Einfügen eines Knotens ist höchstens eine Korrektur nötig, beim Löschen eines Knotens mitunter mehrere.

Weblinks

• http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/avlbaum/ Interaktive Demo (Java-Applet)
• http://www.informatiktreff.de/materialien/sek_ii/algorithmen/avl/avlbaum.htm Ausführlichere Beschreibung