AVL-Baum
Der erste selbstbalancierende binäre Suchbaum — Adelson-Velsky & Landis (1962). Jeder Knoten hält den Höhenunterschied seiner Kinder bei ≤ 1.
Beim Einfügen oder Löschen kann die Balance kippen; sie wird über Rotationen (einfach oder doppelt) wiederhergestellt. Garantiert O(log n) für alle Operationen. Strenger balanciert als ein Rot-Schwarz-Baum → schnellere Lookups, aber teurere Updates.
Idealer Einsatz: lesehastige Workloads. Konkurrenz: Rot-Schwarz-Baum (lockerer balanciert → bessere Update-Performance, das, was der Linux-Kernel nutzt), B-Baum (für Platten), Skip-Lists.