Der AVL-Baum ist ein binärer Suchbaum, der sich nach jeder Einfügung und Löschung selbst ausbalanciert. Benannt ist er nach seinen Erfindern Adelson-Velski und Landis (1962). Die zentrale Garantie: Die Höhe des Baumes bleibt immer O(log n) – damit kosten Suchen, Einfügen und Löschen im schlechtesten Fall garantiert O(log n) Schritte, unabhängig von der Reihenfolge der eingefügten Daten.
Das Problem: entartete Suchbäume
Ein normaler binärer Suchbaum kann entarten: Fügt man Zahlen in sortierter Reihenfolge ein, entsteht eine lange Kette – im Extremfall ein „Strichbaum“ mit Höhe n statt log n. Jede Suche würde dann O(n) Schritte brauchen, also so langsam werden wie das lineare Durchsuchen einer Liste. Der AVL-Baum verhindert genau das, indem er nach jeder Änderung prüft und korrigiert.
Der Balancefaktor und Rotationen
Der AVL-Baum definiert für jeden Knoten den Balancefaktor: die Höhe des linken Teilbaums minus die Höhe des rechten Teilbaums. Erlaubt sind nur die Werte −1, 0 und +1. Weicht ein Knoten nach einer Einfügung oder Löschung davon ab, wird der Baum durch Rotationen wieder in Balance gebracht:
- Einfache Rechtsrotation und einfache Linksrotation drehen die Verkettung an einem überlasteten Knoten um.
- Doppelrotationen (Links-Rechts und Rechts-Links) kombinieren zwei einfache Rotationen und kommen bei verschachtelten Abweichungen zum Einsatz.
- Nach einer Rotation sind die Suchbaum-Eigenschaft und die Sortierreihenfolge der Elemente unverändert – nur die Höhenverteilung stimmt wieder.
Da jede Rotation nur konstante Arbeit kostet und pro Änderung höchstens wenige Rotationen nötig sind, bleiben Einfügen und Löschen bei O(log n).
Anwendungen
- In-Memory-Datenstrukturen: Sortierte Mengen und Wörterbücher in Programmiersprachen, die garantierte Zugriffszeiten brauchen.
- Sortierung und Rangabfragen: Mit erweiterten Knoten lassen sich Elemente nach Rang finden oder zählen – etwa für Statistik und Datenanalyse.
- Datenbank-Indizes (historisch): Frühe In-Memory-Indizes nutzten AVL-Bäume; moderne Datenbanken setzen auf plattenfreundliche Varianten, weil der AVL-Baum als reiner Speicherbaum keine großen Seitenblöcke unterstützt.
Abgrenzung zu anderen balancierten Bäumen
Der AVL-Baum ist strenger balanciert als der Rot-Schwarz-Baum: Er hält die Teilbaumhöhen fast gleich, während Rot-Schwarz-Bäume Höhen bis zum Faktor 2 zulassen. Dafür verlangen AVL-Bäume bei vielen Einfügungen und Löschungen häufiger Rotationen. Wer viele Leseoperationen und wenige Änderungen hat, profitiert vom AVL-Baum; wer sehr viele Änderungen durchführt und einen guten Kompromiss sucht, greift zum Rot-Schwarz-Baum. Für Daten auf Festplatte oder SSD sind Hash-Tabellen oder B-Bäume mit großen Blöcken meist die bessere Wahl.
Verwandte Grundlagen: Binärer Suchbaum | Binärbaum | Baum-Datenstruktur | Big-O-Notation | Hash-Tabelle