AVL Trees

An AVL tree is a binary search tree that keeps every node's subtrees within one level of each other, guaranteeing O(log n) operations.

The balance condition

An AVL tree, named after Adelson-Velsky and Landis, is a binary search tree with a strict balance invariant: at every node the heights of the left and right subtrees differ by at most one. This bounds the total height at about 1.44 log n, so search, insert, and delete are all O(log n) in the worst case, not just on average.

Rotations restore balance

Kronos motion — classical

After an insertion or deletion, a node's balance factor may reach two, violating the invariant. A rotation restructures three nodes locally to lower the height while preserving the BST ordering. There are four cases: left-left and right-right need a single rotation; left-right and right-left need a double rotation.

Left-left heavy: single right rotation
Right-right heavy: single left rotation
Left-right heavy: left then right rotation
Right-left heavy: right then left rotation

Cost of maintenance

Each insertion or deletion walks down O(log n) to find the spot, then walks back up updating heights and performing at most a constant number of rotations. So maintaining balance adds only constant overhead per level, and the total operation stays O(log n).

AVL versus red-black

AVL trees are more rigidly balanced than red-black trees, which makes lookups slightly faster because the tree is shorter, but insertions and deletions may do more rotations. AVL is a good default when reads dominate writes; red-black is preferred when writes are frequent and slightly looser balance is acceptable.

Where they are used

AVL trees suit in-memory ordered maps and sets where predictable worst-case performance matters and the workload is read-heavy. For on-disk ordered data with large fan-out, a B-tree is the standard choice instead.