AVL-Bäume: Korrekte Definition, Selbstbalancierung und Anwendungen

AVL steht für Adelson-Velsky und Landis – die sowjetischen Mathematiker, die diesen selbstbalancierenden binären Suchbaum 1962 erfanden. Es steht nicht für „Adaptive Variable-Length.“

Funktionsweise von AVL-Bäumen

• Jeder Knoten speichert einen Balancierungsfaktor = Höhe(linker Teilbaum) – Höhe(rechter Teilbaum).
• Erlaubte Balancierungsfaktoren: –1, 0, +1.
• Nach Einfügung/Löschung stellen Rotationen (einfach/doppelt) das Gleichgewicht in O(log n) Zeit wieder her.

Wichtige Eigenschaften

• Höhe immer O(log n) → garantiert O(log n) Suche, Einfügung, Löschung.
• Strikter ausbalanciert als Rot-Schwarzbäume → schnellere Suchen, etwas langsamere Schreibvorgänge.

Häufige Anwendungen

• In-Memory-Datenbanken und Indexe
• Compiler-Symbollisten
• Echtzeitsysteme mit voraussehbarer Latenz