AVL tree
The first self-balancing binary search tree — Adelson-Velsky & Landis (1962). Each node keeps the height difference between children at ≤ 1.
Balance can break on insert/delete; restored via rotations (single or double). Guarantees O(log n) for every operation. More strictly balanced than red-black trees → faster lookups, more expensive updates.
Sweet spot: read-heavy workloads. Competitor: red-black tree (more relaxed → better update perf, what the Linux kernel uses), B-tree (for disk), skip lists.