Visual walkthrough — AVL tree — balance factor, rotations (LL, RR, LR, RL), insert, delete

We assume only that you know what a Binary Search Tree is: a tree where every left descendant is smaller and every right descendant is larger than a node. Everything else we build here.

---

Step 1 — What "height" even means

WHAT. We must pin down a single number that measures "how tall is this tree?" before we can bound it.

WHY. The entire promise of an AVL tree is fast search, and search cost = how many nodes you walk from the top to the bottom = the height. If we can't measure height we can't bound the search cost. (See Big-O Notation for why "cost" and "height" are the same story here.)

PICTURE. Look at the figure. The height of a node is the number of edges on the longest downward path from that node to a leaf.

That $-1$ convention is not a random choice — it is the only value that makes the formula $height=1+\max (\text{children})$ agree with "a leaf has height 0". The parent note's first common mistake is precisely forgetting this.

---

Step 2 — The balance rule, drawn

WHAT. State the one constraint every AVL node obeys.

WHY. We need a precise rule to feed into a counting argument. "Almost balanced" is a feeling; "$|BF|\le 1$" is a number we can do algebra with.

PICTURE. For any node, subtract the two children's heights. That difference is the balance factor.

So the two children of any node may differ in height by at most one. Keep that single sentence — the whole derivation is squeezing juice out of it.

---

Step 3 — Flip the question: sparsest tree, not tallest

WHAT. Instead of asking "how tall can a tree of $n$ nodes get?", ask the mirror question: "what is the fewest nodes a tree of height $h$ can possibly have?"

WHY. These two questions are two sides of the same coin, but the second one is constructive — we can literally build the sparsest tree and count it. Call that minimum count $N(h)$.

• If a height-$h$ AVL tree is forced to contain many nodes even at its sparsest, then a tree with only $n$ nodes cannot afford to be tall. That is the whole logical trick.

PICTURE. The sparsest height-$h$ tree: a root, one subtree as tall as possible ($h-1$), and the other subtree made as short as the AVL law still permits.

Why can the shorter subtree be $h-2$ and not shorter? Because the root's balance factor is $height(h-1)-height(\text{other})$, and the AVL law caps this at $1$. So $\text{other}\ge (h-1)-1=h-2$. Making it exactly $h-2$ uses the fewest nodes while staying legal.

---

Step 4 — Write the recurrence for the sparsest tree

WHAT. Turn the picture from Step 3 into an equation.

WHY. A picture of "root + two sub-trees" is an addition waiting to happen. Counting nodes across the whole tree = 1 (the root) + nodes in the left sub-tree + nodes in the right sub-tree.

PICTURE. Each of the two triangles below is itself a sparsest tree of its own height — so it contributes $N(h-1)$ and $N(h-2)$ nodes.

Let us actually crank a few values so the pattern is undeniable:

$h$	$N(h)=1+N(h-1)+N(h-2)$
$-1$	$0$
$0$	$1$
$1$	$1+1+0=2$
$2$	$1+2+1=4$
$3$	$1+4+2=7$
$4$	$1+7+4=12$

---

Step 5 — Spot the hidden Fibonacci

WHAT. Show that $N(h)$ is the Fibonacci sequence wearing a disguise.

WHY. Fibonacci numbers are the sequence whose recurrence is "add the previous two" — and they have a famous closed form involving the golden ratio. If we can pin $N(h)$ to Fibonacci, we inherit that closed form for free and finish the height bound.

PICTURE. Add $1$ to every $N(h)$ and the ugly "$+1$" in the recurrence vanishes, leaving pure Fibonacci.

Watch the algebra. Define $M(h)=N(h)+1$. Substitute into the recurrence: $N(h)=1+N(h-1)+N(h-2)$ $\underset{M(h)}{\underbrace{N(h)+1}}=\underset{M(h-1)}{\underbrace{N(h-1)+1}}+\underset{M(h-2)}{\underbrace{N(h-2)+1}}$

• Left side: $N(h)+1=M(h)$.
• Right side: the stray $+1+1+1=+3$ from the three "+1"s? No — we added $1$ to each term, and $1=1+1-1$: the constant $1$ on the right plus the two $+1$s equals the single $+1$ we need on the left. The bookkeeping works out to exactly $M(h)=M(h-1)+M(h-2)$. That is the Fibonacci recurrence.

Checking against our table, $M(h)=N(h)+1$ gives $1,2,3,5,8,13$ for $h=-1,0,1,2,3,4$ — the Fibonacci numbers $F_2,F_3,F_4,\dots$

---

Step 6 — Golden ratio ⇒ logarithmic height

WHAT. Convert "$N(h)$ grows like Fibonacci" into "$h$ grows like $\log n$".

WHY. Fibonacci numbers grow exponentially — each is about $\varphi \approx 1.618$ times the last. Exponential growth in $N(h)$ means, read backwards, logarithmic growth in $h$. That backwards read is the punchline.

PICTURE. $N(h)$ shoots up like ${\varphi }^h$; invert that curve and height flattens into a logarithm.

The closed form of Fibonacci is $F_k\approx {\varphi }^k/\sqrt{5}$ with $\varphi =\frac{1+\sqrt{5}}{2}\approx 1.618$. So: $N(h)=F_{h+3}-1\approx \frac{{\varphi }^{h+3}}{\sqrt{5}}$

• ${\varphi }^{h+3}$ — grows by a factor of $\varphi$ for each extra unit of height.
• dividing by $\sqrt{5}$ — a constant fudge factor; irrelevant to growth rate.

Now the reversal. A real tree with $n$ nodes and height $h$ has $n\ge N(h)$ (it can't be sparser than the sparsest). So: $n\ge \frac{{\varphi }^{h+3}}{\sqrt{5}}⟹{\varphi }^h\le \sqrt{5}\cdot {\varphi }^{-3}\cdot n⟹h\le {\log }_{\varphi }n+C$

Convert the base with ${\log }_{\varphi }n=\frac{{\log }_{2}n}{{\log }_2\varphi }$ and ${\log }_2\varphi \approx 0.694$: $\boxed{h\le \frac{1}{0.694}{\log }_{2}n\approx 1.44{\log }_{2}n}$

• ${\log }_{2}n$ — height of a perfectly balanced tree.
• $1.44$ — the price of AVL's slight looseness: an AVL tree is at worst $44\%$ taller than perfect. Still $O(\log n)$.

That is the theorem the parent note stated. Search, insert, and delete each walk one root-to-leaf path, so all three cost $O(h)=O(\log n)$. Compare with a naive Binary Search Tree which can hit $h=n$.

---

Step 7 — The degenerate cases (do the edges break it?)

WHAT. Check the two smallest trees and the "empty" case, where any argument can silently fail.

WHY. Contract rule: cover every case. A bound that is true for tall trees but false for $h=0$ is a broken bound.

PICTURE. Three tiny trees drawn explicitly against the formula.

• Empty tree ($h=-1$): $N(-1)=0$. Correct — zero nodes. The recurrence's base case, not derived, is chosen to make this consistent.
• Single leaf ($h=0$): $N(0)=1$, and $F_3-1=2-1=1$. ✅ The formula survives its smallest non-trivial input.
• Height 1: $N(1)=2$ — a root with exactly one child. Note this child must be a leaf, and the root's $BF=0-(-1)=+1$, which is legal. If we demanded $BF=0$ everywhere, height-1 with 2 nodes would be illegal and the whole Fibonacci count would collapse — this is why AVL allows $\pm 1$, not just $0$.

The bound therefore holds from the tiniest tree upward, with no gap.

---

The one-picture summary

Everything on this page in one arc: the AVL law ($|BF|\le 1$) forces the sparsest tree into a recursive "root + tall + short" shape, that shape's node-count is Fibonacci, Fibonacci grows like ${\varphi }^h$, and inverting exponential growth gives logarithmic height. Unlike a Red-Black Tree (whose bound is $2{\log }_{2}n$ via a different colouring argument), AVL's tighter $1.44{\log }_{2}n$ falls straight out of Fibonacci.

Recall Feynman retelling — say it to a friend

"Suppose I want an AVL tree to be as tall as possible using as few blocks as I can. I make one side tall, and — since the two sides can only differ by one floor — the other side just one floor shorter. Count the blocks: it's the root plus the blocks in each side, so $N(h)=1+N(h-1)+N(h-2)$. That 'add the previous two' rule? That's Fibonacci! And Fibonacci numbers blow up by about $1.6\times$ every step. So even the skinniest legal tree still packs in exponentially many nodes as it gets taller. Turn that around: if I only have $n$ nodes, the tree simply cannot get taller than about $1.44{\log }_{2}n$. That's why searching an AVL tree is always fast."

Recall Quick self-test

Why is empty-tree height defined as $-1$? ::: So a leaf comes out to height $0$ from $1+\max (-1,-1)$; it keeps every balance-factor formula clean. What recurrence counts the fewest nodes in a height-$h$ AVL tree? ::: $N(h)=1+N(h-1)+N(h-2)$, with $N(0)=1,N(-1)=0$. Which famous sequence does $N(h)$ equal? ::: $N(h)=F_{h+3}-1$, the shifted Fibonacci numbers. Where does the number $1.44$ come from? ::: From $1/{\log }_2\varphi \approx 1/0.694$, the base-change of ${\log }_{\varphi }n$ into ${\log }_{2}n$.

---

Prerequisites & neighbours: Binary Search Tree · Tree Rotations · Fibonacci Numbers · Big-O Notation · Red-Black Tree · Heap