AVL står för Adelson-Velsky och Landis – de sovjetiska matematikerna som uppfann detta självbalanserande binära sökträd 1962. Det betyder INTE "Adaptive Variable-Length."
Hur AVL-träd fungerar
- Varje nod lagrar en **balansfaktor** = höjd(vänster delträd) – höjd(höger delträd).
- Tillåtna balansfaktorer: –1, 0, +1.
- Efter insättning/borttagning, rotationer (enkel/dubbel) återställer balans i O(log n) tid.
Viktiga egenskaper
- Höjden alltid O(log n) → garanterat O(log n) sökning, insättning, borttagning.
- Strängare balanserade än röd-svarta träd → snabbare uppslag, något långsammare skrivningar.
Vanliga tillämpningar
- Minnesbaserade databaser och index
- Kompilatorns symboltabeller
- Realtidssystem som kräver förutsägbar latens
