AVL trees: self-balancing binary search
A binary search tree is only fast while it stays bushy. Insert sorted keys into a plain BST and it quietly degenerates into a linked list: search becomes a walk down a chain of n nodes. The AVL tree — named for Adelson-Velsky and Landis, who described it in 1962 — refuses to let that happen. Every node stores the height of its subtree, and after each insert or delete the tree checks one number per node, the balance factor. If any factor drifts outside −1, 0, +1, a local rearrangement called a rotation restores it on the spot. The payoff is a hard guarantee, proved at the end of this page: the height can never exceed about 1.44 times the height of a perfect tree, so search, insert, and delete are logarithmic — always, not just on average.
The one-sentence idea. Keep every node’s two subtrees within one level of each other in height. That single local rule, repaired by rotations after every update, is enough to force the whole tree’s height to stay within a constant factor of optimal.
1 — A BST with a second promise: stay balanced
An AVL tree is first of all a binary search tree: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. On top of that it adds the AVL invariant: at every node, the heights of the left and right subtrees differ by at most one. Height here counts edges on the longest downward path — a leaf has height 0, and an empty subtree has height −1. Each node caches its height, so checking the invariant at a node is a single subtraction.
| Height of a node | |
|---|---|
| Balance factor | |
| Reading the sign | A positive factor means the left subtree is taller (left-heavy); negative means right-heavy; zero means the two sides are exactly level. The factor says nothing about how many nodes each side holds — only about height, which is what search cost actually depends on. |
The tree below satisfies the invariant everywhere. Click any node to see its two subtree heights and its balance factor worked out in full. The badges can be switched off for a cleaner picture.
Figure 1: An AVL tree: click a node to inspect it
How to read this
- Height is cached, not recomputed. Each node stores its height; after an update, only the nodes on the path back to the root need their heights refreshed — everyone else’s subtree did not change.
- The invariant is local, the guarantee is global. Nothing in the rule mentions the whole tree, yet Step 7 shows it caps the total height at about 1.44 log2 n.
- Balance factor 0 is not required. Factors of ±1 are perfectly legal and extremely common; only ±2 triggers a repair.
2 — Heights and the balance factor, up close
Strip a node down to its essentials: a key, and two subtrees whose internal structure does not matter for the factor — only their heights do. The figure below replaces each subtree with a triangle labelled by its height. Move the two sliders and watch the factor respond: it is a plain difference, so every extra level on one side moves it by exactly one. The legal band is just three values wide, which is what makes the AVL rule so strict — a subtree is allowed to outgrow its sibling by one level, never two.
Figure 2: Balance factor for left height 3 and right height 2
Two consequences are worth internalising before moving on. First, the factor is about height difference, not node counts: a left subtree can hold nearly twice as many nodes as the right and still have the same height, so a factor of 0 does not mean the tree is perfectly filled. Second, because heights only change along the path of an update, a single insert or delete can push a factor from +1 to +2, but never further in one step. The repair therefore always starts from a factor of exactly ±2, and the shape of the offending subtree tells us exactly which repair applies. That shape analysis is the whole content of the next step.
| What a factor means |
|---|
3 — Rotations: the only repair tool
When a node reaches factor ±2, the fix never rebuilds the subtree — it rotates it. A rotation is a constant-time rearrangement of two or three nodes that preserves the inorder sequence exactly, so the BST property survives untouched, while pulling the tall side down one level and lifting the short side up. Because the inorder sequence is preserved, a rotation can never break the search-tree ordering; it only redistributes height.
Which rotation applies depends on the shape of the imbalance, named by the two steps you take from the unbalanced node toward the new growth. If the growth is on the outside — left-left or right-right — the unbalanced node’s child is already leaning the same way, and one rotation settles it. If the growth is on the inside — left-right or right-left — the child leans the wrong way, and a single rotation would just move the problem; the child must first be rotated to straighten the bend, then the original node is rotated. Pick a case and step through it.
Figure 3: Left-left case: a single right rotation
| Right rotation (fixes LL) | |
|---|---|
| Left rotation (fixes RR) | The exact mirror image: the pivot’s right child rises, and that child’s old left subtree is handed to the pivot as its new right subtree. Recompute the pivot’s height first, then the risen child’s. |
| Double rotations | LR is a left rotation on the left child followed by a right rotation on the node itself. RL is the mirror: a right rotation on the right child, then a left rotation on the node. The first rotation converts the bent shape into a straight one; the second fixes it. |
| Cost of a rotation |
Why the middle subtree β is the whole story. In a right rotation, β is the subtree caught between x and y, larger than x, smaller than y, by the BST property. That is exactly the qualification needed to become y’s left subtree, which is why the handover preserves the ordering. Every rotation is this one handover, mirrored or doubled.
4 — Insert: descend, attach, climb back repairing
Insertion is an ordinary BST insert — descend comparing keys, attach the new node as a leaf — followed by a walk back up the same path. On the way up, each ancestor gets its height refreshed and its factor checked. The lowest ancestor that reaches ±2 is where the trouble is: one single or double rotation there restores that subtree’s height to what it was before the insert, which automatically re-validates every ancestor above it. That is why an insert never needs more than one repair: at most two rotations, total.
The sequence below inserts 10, 20, 30, 25, 22, 5, 3 into an empty tree. It is deliberately unkind — sorted-ish runs that would chain a plain BST — and it triggers three separate repairs of two different kinds. Step through it.
Figure 4: Inserting 10, 20, 30, 25, 22, 5, 3
// insert(x, key): BST insert, then rebalance on the way back up if x is empty: return new node(key) // attach as a leaf, height 0 if key < x.key: x.left = insert(x.left, key) else: x.right = insert(x.right, key) updateHeight(x) if BF(x) = +2: // left-heavy if key > x.left.key: x.left = rotateLeft(x.left) // LR: straighten first return rotateRight(x) if BF(x) = −2: // right-heavy, mirror image if key < x.right.key: x.right = rotateRight(x.right) // RL return rotateLeft(x) return x
5 — Delete: three shapes of removal, then a possibly long climb
Deletion starts as ordinary BST deletion, which has three shapes. A leaf is simply unlinked. A node with one child is spliced out and its child takes its place. A node with two children cannot be spliced, so its key is overwritten with its inorder successor — the smallest key in its right subtree — and that successor, which has at most one child, is deleted instead. After the structural removal, the walk back to the root refreshes heights and factors exactly as in insert — with one crucial difference: a rotation after a delete can leave the subtree shorter than before, so an ancestor that was fine a moment ago can tip to ±2 as well. Repairs can cascade all the way to the root, up to one rotation per level.
There is also one case that only delete can produce: the child of the unbalanced node has factor 0. A single rotation still fixes it (the subtree keeps its height, so the cascade stops there). The sequence below starts from an 11-node tree and deletes 5, 70, 60, 40 — covering a leaf, another leaf, a one-child splice that forces a rotation at the root, and a two-children delete that ends in a rotation too.
Figure 5: Deleting 5, 70, 60, 40
Insert repairs once; delete may repair at every level
- Insert: the rotation restores the subtree’s pre-insert height, so ancestors see no change. At most one single or double rotation per insert.
- Delete: the rotation may reduce the subtree’s height by one, which can unbalance the parent, whose repair can unbalance its parent. Worst case is one rotation per level — still logarithmic, because the height is.
- The factor-0 child: unique to delete. If the tall child has BF 0, do the single rotation anyway; the subtree’s height is unchanged by it, so the cascade stops immediately.
6 — Playground: run your own updates
Everything so far, live. Choose a key, insert or delete it, and the page’s own AVL code does the rest — BST update, height refresh, factor checks, rotations — and reports exactly what it did. Try inserting 1 through 15 in order: the pattern a plain BST turns into a 15-node chain stays at height 3 here. The tree is capped at 31 nodes so every node stays readable.
Figure 6: Playground tree: 0 nodes, height −1
Insert a key to begin, or build the sorted-insert worst case with “Insert 1…15 in order” — fifteen keys a plain BST would chain, held here at height 3.
7 — Why the height stays logarithmic
The guarantee does not come from watching the tree grow. It comes from the opposite question: what is the fewest nodes an AVL tree of a given height can possibly have? If even the sparsest legal tree of height h needs exponentially many nodes, then turning the statement around, a tree with n nodes cannot be very tall — its height is forced to be logarithmic in n. So build the sparsest tree: to reach height h as cheaply as possible, the root needs one subtree of height h − 1 (to set the height) and — because the factor may not exceed 1 — the other subtree must be at least height h − 2. Making both as sparse as possible gives the recurrence, where N(h) is the minimum number of nodes in any AVL tree of height h.
| Base cases | |
|---|---|
| The recurrence | |
| Worked values, no step skipped |
That recurrence should look familiar — it is Fibonacci in disguise. Add 1 to both sides and the trailing +1 is absorbed, step by step:
| Unmasking Fibonacci |
|---|
Fibonacci numbers grow like the golden ratio raised to the index, so N(h) grows exponentially in h: roughly φh divided by √5. Exponential in one direction means logarithmic in the other: solving N(h) ≤ n for h gives the famous bound. The sparsest trees are called Fibonacci trees; the figure below draws the exact sparsest tree for heights up to 5 and the recursive schematic beyond that, and pairs it with the capacity of a perfect tree of the same height. One slider drives both halves.
Figure 7: The sparsest AVL tree of height 4 has 12 nodes
Now invert it, with every step shown, for a million keys. The two Fibonacci values bracketing a million are:
| A million keys, bounded exactly | |
|---|---|
| The closed form |
Counted in levels (a leaf is level-height 1), the closed form gives at most 28 levels for a million keys — the same answer as the Fibonacci count above, which said 27 edges. A degenerate BST holding the same million keys can be 999,999 edges tall. The AVL invariant buys a factor of about 37,000 in worst-case search length at that size, and the factor itself grows with n.
| Keys n | Degenerate BST, worst height | Perfect tree height | AVL worst height |
|---|---|---|---|
| 10 | 9 | 3 | 3 |
| 100 | 99 | 6 | 8 |
| 1,000 | 999 | 9 | 13 |
| 1,000,000 | 999,999 | 19 | 27 |
Read the last two columns together: the AVL worst case is never more than about 44% taller than the perfect tree, at any size, and that ratio is exactly the 1.4405 constant. That is the entire content of “the height stays logarithmic”: height is Θ(log n), with a small, known constant.
8 — Costs, comparisons, and where AVL trees earn their keep
| Operation | Cost | Why |
|---|---|---|
| Search | O(log n) | One root-to-leaf path; the height is at most about 1.44 log2 n. |
| Insert | O(log n) | Descend O(log n), then at most one single or double rotation on the climb. |
| Delete | O(log n) | Descend O(log n); repairs may cascade, but at most one rotation per level. |
| Rotation | O(1) | Three pointer changes and two height recomputes, independent of subtree size. |
| Space overhead | One height (or factor) per node | The factor fits in two bits; many implementations store it instead of the full height. |
AVL versus red-black. Both guarantee logarithmic height, but they strike the balance bargain differently. AVL’s rule is stricter — heights within one level — so its trees are a little shorter (worst case about 1.44 log2 n against red-black’s 2 log2 n) and lookups a little faster. The price is paid on updates: red-black trees bound the number of rotations per insert and delete by a small constant with a looser invariant, while AVL deletes can rotate at many levels, and AVL inserts rebalance more often in practice. The usual rule of thumb follows: read-heavy workloads favour AVL; write-heavy ones favour red-black — which is why red-black trees sit inside most standard-library maps (C++ std::map, Java TreeMap), while AVL trees show up where lookup latency must be as tight and predictable as possible, and throughout textbooks, because the height-and-factor machinery is the cleanest way to see why balancing works at all.
Where the pieces recur. The stored-height trick reappears in B-trees and their variants that index databases and filesystems — there the “rotation” becomes a node split or merge, but the idea is identical: keep a cheap local measure, check it on the path back up, repair locally. Learn AVL and the rest of the balanced-tree family reads as variations on one theme.
The arc, in one breath. Store heights, subtract to get balance factors, and insist each factor stays in {−1, 0, +1}. Repair violations with rotations — single for straight growth, double for bent growth — on the climb back from every insert and delete. The sparsest tree obeying the rule is a Fibonacci tree, its node count grows like φh, and so every AVL tree with n nodes has height O(log n). Balance is not maintained by luck or by rebuilding; it is maintained by arithmetic.
