AVL trees: self-balancing binary search

Table of Contents

Data structures — the self-balancing search tree

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 nodeh(empty)=−1h(x)=1+max(h(left(x)),h(right(x)))
Balance factorBF(x)=h(left(x))−h(right(x))BF(x)∈{−1,0,+1}at every node, always
Reading the signA 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

selected node small badge: balance factorlabel under a node: its height
Figure 1. Every balance factor in this tree is −1, 0, or +1, so no repair is needed. Node 20 is the most lopsided node here: its left subtree has height 1 and its right subtree has height 0, so BF(20) = 1 − 0 = +1, left-heavy, but legal. Click any node and the readout recomputes its factor from the real subtree heights.

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

Figure 2. The triangles stand for whole subtrees; their drawn size grows with the height you set. The height labels travel with the triangles as they resize. An empty subtree (height −1) is drawn as a stub and labelled “empty”.

Set the two subtree heights

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 meansBF=+1left subtree one level taller — legalBF=0subtrees exactly level — legalBF=−1right subtree one level taller — legalBF=±2invariant broken — rotate now

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

unbalanced node (factor ±2) node that rotates uptriangles α, β, γ, δ are whole subtrees, carried along unchanged

Figure 3. In every case the inorder sequence of the whole subtree — read the triangles and letters left to right — is identical before and after. Only the heights change: the subtree that was two levels too tall ends exactly one level shorter.
Right rotation (fixes LL)pivoty,its left childxrises to takey’s placex’s old right subtreeβbecomesy’s new left subtreeheights are recomputed foryfirst, then forx
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 rotationsLR 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 rotationpointer changes=3height recomputes=2time=O(1)

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

newly inserted node factor hit ±2 node lifted by the rotation

Figure 4. Seven inserts into a plain BST in this order would already lean hard to the right; here every factor stays in {−1, 0, +1} after each step, and the final tree has height 2 — the same as a perfectly balanced tree with 7 nodes.
// 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

node being deleted (or the successor copied into it) factor hit ±2 node lifted by the rotation

Figure 5. Watch the root across the four deletes: 40 holds until the splice of 60 tips it to +2, a right rotation promotes 20, and the tree finishes at height 3 with 7 nodes — still perfectly legal, every factor in {−1, 0, +1}.

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

node touched by the last operation node lifted by a rotation

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.

Figure 6. Duplicate inserts and deletes of missing keys are reported, not silently ignored. After every operation the whole tree is re-checked: if any factor ever left {−1, 0, +1}, the readout would say so. It will not.

Key to insert or delete

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 casesN(0)=1a single nodeN(1)=2a root with one child
The recurrenceN(h)=N(h−1)+N(h−2)+1the+1is the root itself
Worked values, no step skippedN(2)=N(1)+N(0)+1=2+1+1=4N(3)=N(2)+N(1)+1=4+2+1=7N(4)=N(3)+N(2)+1=7+4+1=12N(5)=N(4)+N(3)+1=12+7+1=20

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 FibonacciN(h)+1=N(h−1)+N(h−2)+1+1N(h)+1=N(h−1)+N(h−2)+2N(h)+1=(N(h−1)+1)+(N(h−2)+1)so withM(h)=N(h)+1:M(h)=M(h−1)+M(h−2),M(0)=2,M(1)=3N(h)=Fib(h+3)−1withFib(1)=Fib(2)=1

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

Figure 7. Left: the sparsest legal tree — every root takes the sparsest subtree of height h − 1 on one side and of height h − 2 on the other, so every balance factor is +1 or −1 and nothing can be removed without breaking either the height or the invariant. Right: how the minimum node count grows against the perfect-tree capacity of the same height (bar lengths on a log scale; labels are exact).

Choose the height

12minimum nodes N(h)
Fib(7) − 1 = 13 − 1Fibonacci check
11height of a chain with N(h) nodes
31perfect tree capacity, height h

Now invert it, with every step shown, for a million keys. The two Fibonacci values bracketing a million are:

A million keys, bounded exactlyN(27)=Fib(30)−1=832040−1=832039N(28)=Fib(31)−1=1346269−1=1346268832039≤1000000<1346268so a height-28 AVL tree needs more nodes than we haveh≤27for any AVL tree withn=1000000
The closed formh≤1.4405×log2(n+2)−0.3277when height is counted in levelsthe constant1.4405=1log2φis the golden ratio’s fingerprint

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 nDegenerate BST, worst heightPerfect tree heightAVL worst height
10933
1009968
1,000999913
1,000,000999,9991927

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

OperationCostWhy
SearchO(log n)One root-to-leaf path; the height is at most about 1.44 log2 n.
InsertO(log n)Descend O(log n), then at most one single or double rotation on the climb.
DeleteO(log n)Descend O(log n); repairs may cascade, but at most one rotation per level.
RotationO(1)Three pointer changes and two height recomputes, independent of subtree size.
Space overheadOne height (or factor) per nodeThe 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.

AVL tree: Adelson-Velsky & Landis, 1962. Heights on this page count edges: a leaf has height 0 and an empty subtree height −1. Every tree drawn here is produced by the page’s own AVL implementation, and every factor shown is computed from the real subtree heights.