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

Before you can read the parent note (topic overview), you need every symbol it throws at you to already feel obvious. This page builds each one from nothing, in an order where each idea leans on the one before it.

1. A node — the single block

Picture one box with the number written inside and two little hooks hanging off the bottom — a left hook and a right hook. That's the atom everything else is built from.

Why the topic needs it: everything in an AVL tree — heights, balance, rotations — is just rules about how these boxes hook to each other.

2. Left and right children — the two hooks

In code the parent note writes node.left and node.right. Read those as "follow the left hook" and "follow the right hook". If the hook points to nothing, node.left is None.

Why the topic needs it: rotations are literally about re-hooking — taking the arrow that pointed one way and making it point another way.

3. Binary Search Tree — the ordering rule

Look at the figure: from any box, go left → numbers shrink, go right → numbers grow. That's the whole rule of a Binary Search Tree.

Why the topic needs it: AVL is a BST that also stays short. The ordering rule must survive every rotation — that's the promise a rotation must never break.

4. Height — how tall a subtree is

Why $-1$ for empty? Because we want a leaf to come out as $0$. A leaf's height is "1 more than its tallest child". Its children are both empty. If empty $=-1$, then leaf $=1+(-1)=0$. Clean.

Why the topic needs it: "stays short" means "small height." We can't talk about balance until we can measure height.

5. The $\max$ and the vertical bars $|\cdot |$

Two tiny bits of notation the parent uses without pausing:

Why the topic needs it: the balance rule is written $|BF|\le 1$ — meaning "off by at most one, doesn't matter which side." Without the bars you'd have to write two rules ($BF\le 1$ and $BF\ge -1$); the bars fold both into one.

6. Balance factor — the lean of a node

Now we can build the star of the show.

Read the sign like a see-saw tipping:

Why the topic needs it: this single number is the alarm bell. The parent's entire algorithm is "walk up, look at $BF$, if $|BF|>1$ ring the alarm and rotate."

7. Rotation — re-hooking three boxes

You don't need the full machinery here (the parent covers LL, RR, LR, RL) — just the concept: it's local surgery on 3 nodes, studied on its own in Tree Rotations. The key promise it must never break is the BST ordering from section 3.

Why the topic needs it: when $|BF|=2$, a rotation is the tool that pushes it back to $\le 1$.

8. $O(\log n)$ — the "stays fast" label

Think of ${\log }_{2}n$ as "how many times can I halve $n$ before reaching 1." $8\to 4\to 2\to 1$ is 3 halvings, so ${\log }_{2}8=3$.

Why the topic needs it: the whole reason AVL exists is to guarantee height stays $O(\log n)$ instead of degenerating to $O(n)$ (a straight line of boxes = a linked list). Contrast with a plain BST, and with a Red-Black Tree which trades a looser balance rule for faster inserts.

9. $\varphi$ and Fibonacci — why the guarantee holds

The parent proves the height bound using Fibonacci Numbers and the golden ratio.

Why the topic needs it: the sparsest possible AVL tree of height $h$ has $N(h)=1+N(h-1)+N(h-2)$ boxes — the Fibonacci pattern. Because Fibonacci grows like ${\varphi }^h$, having $n$ boxes forces height $h\le 1.44{\log }_{2}n$. That's the entire proof that AVL is fast. (Not a Heap, which balances shape but not order — different tool for a different job.)

Prerequisite map

Equipment checklist

Self-test — can you answer each before revealing?