AVL-träd
Det första självbalanserande binära sökträdet — Adelson-Velsky & Landis (1962). Varje nod håller skillnaden i höjd mellan sina barn på ≤ 1.
Vid insert/delete kan balansen brytas; återställs med rotationer (single eller double). Garanterar O(log n) för alla operationer. Striktare balanserat än röd-svart-träd → snabbare lookups, men dyrare uppdateringar.
Sweet spot: läs-tunga workloads. Konkurrent: röd-svart-träd (mer relaxerat → bättre update-perf, det Linux-kärnan använder), B-träd (för disk), skip lists.