Don't memorize AVL rotations — watch the tree rebalance itself. An AVL tree is a binary search tree that refuses to get lopsided. After every insert it walks back up checking each node's balance factor, and the instant one tips to ±2 it rotates to fix it. Straight-line imbalances take a single rotation; zigzags take a double. That keeps the height O(log n) forever — so search never decays into a linked-list crawl.
balance factor = h(left) − h(right) · rotate at ±2 · single or double · height O(log n)
BALANCED BST
A binary search tree kept short on purpose, so height is always O(log n).
BALANCE FACTOR
bf = height(left) − height(right). AVL keeps it in {−1, 0, +1}.
ROTATION
A local O(1) re-link that rebalances while preserving the sorted order.
FOUR CASES
LL and RR need one rotation; LR and RL are zigzags that need two.
avl.sim — insert 10, 20, 30, 5, 7
Ready
Each node shows its balance factor. Insert like a normal BST; when a node reaches ±2 (red), the tree rotates to fix it. Press Step to watch a single rotation, then a double.
A binary search tree is only fast when it is bushy. Feed it sorted keys — 10, 20, 30, 40 — and it degenerates into a single leaning chain, a glorified linked list where search is O(n). The AVL tree, named after Adelson-Velsky and Landis, fixes this by enforcing one invariant: at every node, the left and right subtrees may differ in height by at most one. It tracks that difference as a balance factor. Insert as usual, then retrace the path to the root updating heights; the first node whose balance factor hits ±2 is the pivot of a rotation. A rotation just re-points three or four links — an O(1) operation — and crucially it preserves the in-order sequence, so the tree stays a valid BST. One rotation cures a straight-line lean; a zigzag needs the child straightened first, hence two.
01
Insert like a BST
Place the key by the usual less-than / greater-than comparisons, then walk back up updating heights.
02
Find the tipping point
The first node with |bf| = 2 on the way up is unbalanced and must be rotated.
03
Pick the case
Same-side lean (LL / RR) → single rotation. Zigzag (LR / RL) → rotate the child, then the node.
04
Stay sorted, stay short
Rotations are O(1) and keep the in-order order, so the tree remains a BST of height O(log n).
Search / insert / delete
O(log n)
Space
O(n)
Invariant
|bf| ≤ 1
Height
≤ 1.44 log n
The pay-off is a guarantee: no matter the insert order, an AVL tree is never more than about 1.44·log n tall, so lookups can never decay. Its close cousin the red-black tree allows a bit more slack and so rotates less on each update — a better fit for write-heavy workloads, and the balancing scheme behind many standard-library maps. AVL, being more tightly balanced, wins on read-heavy ones. Both descend from the humble binary search tree; the rotation is simply the price of keeping it honest.
Check yourself
1 · What is a node's balance factor?
AVL keeps every balance factor in {−1, 0, +1}. When an insert pushes it to ±2, that node is rebalanced with a rotation.
2 · A node reaches bf = −2 and the new key went into the right child's right subtree. Which fix?
Right-right is a straight line, so one left rotation at the unbalanced node restores balance. Zigzags (LR/RL) are the ones needing a double.
3 · Why are rotations safe to apply?
A rotation only re-points a few links and leaves the left-to-right ordering intact, so the tree stays a valid BST — just shorter.
Questions
AVL tree vs red-black tree?
Both are self-balancing BSTs with O(log n) operations. AVL is more strictly balanced, so lookups are slightly faster — good for read-heavy use. Red-black trees tolerate a little more imbalance and do fewer rotations per update, which suits write-heavy use and is why they back many standard-library maps and sets.
Why not just use a plain BST?
A plain BST has no balance guarantee. Insert already-sorted data and it becomes a single chain of height n, making search O(n). AVL rotations keep the height O(log n) no matter the insertion order.
When is a double rotation needed?
When the imbalance is a zigzag: the heavy child leans one way and its heavy child leans the other (left-right or right-left). You first rotate the child to straighten the line into an LL or RR shape, then rotate the unbalanced node.
Sorted, and never lopsided.
Track a balance factor at each node, rotate the moment it hits ±2, and a binary search tree stays O(log n) tall for every insert order.