A strictly balanced tree
An AVL tree is a binary search tree that adds a strict balance rule: for every node, the heights of its left and right subtrees may differ by at most one. This rule keeps the whole tree's height small, so searches never degenerate into a long chain.
Tracking and detecting imbalance
Each node stores its balance factor, the height of its left subtree minus its right. After an insertion or deletion, the tree walks back up updating these factors. If any node's factor reaches plus or minus two, that node is out of balance and must be repaired.
Rotations restore balance
A rotation is a local rewiring that lifts one node and lowers another while preserving the search order. There are four cases, named by the direction of imbalance:
- Left left and right right are fixed by a single rotation.
- Left right and right left need a double rotation, one to straighten the zig zag, then one to balance.
Each rotation touches only a few pointers, so rebalancing is cheap and the tree stays balanced after every operation.
Key idea
An AVL tree caps every node's left right height difference at one and uses single or double rotations after each change to restore balance, guaranteeing a short tree.