← Back to the red black trees page
AVL Tree
The strictest balancer: sibling heights differ by at most 1. Reads are fastest of any BST; writes pay for it with more rotations.
What to know
- Balance factor ∈ {−1, 0, 1} stored per node; violations trigger LL/RR/LR/RL rotations.
- Height ≤ 1.44 log n — measurably shorter than red-black’s 2 log n bound.
- Choose AVL for read-heavy workloads, red-black for mixed ones.
In the wild: Read-heavy in-memory indexes, language runtimes, early filesystem trees.
Algorithms to reach for
Rotation rebalancing
O(log n)Restore balance factor after each write
Height-tracked search
O(log n)Fastest guaranteed BST lookups
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.