What an AVL tree guarantees
An AVL tree is a binary search tree where, for every node, the heights of the left and right subtrees differ by at most one. We store this difference as the node's balance factor. Because the height stays logarithmic in the number of nodes, search, insert, and delete all stay fast.
When balance breaks
After inserting or deleting, a node's balance factor can reach plus or minus two. We fix it by walking back up to the root and rotating the first unbalanced node we meet.
There are four cases, named by the path to the deeper grandchild:
- Left Left heavy: one right rotation.
- Right Right heavy: one left rotation.
- Left Right heavy: rotate the child left, then the node right.
- Right Left heavy: rotate the child right, then the node left.
A single rotation relinks three subtrees and updates two heights. A double rotation is just two singles chained together.
Why it works
A rotation preserves the in order ordering of keys, so the tree stays a valid search tree. It also reduces the height of the heavy side by one, restoring balance locally.
Key idea
Detect the first unbalanced ancestor, classify it into one of four cases, and rotate to drop its height while keeping keys in order.