[B] AVL Tree

Step 1 -- The everyday picture. A plain binary search tree files each new key by going left when it is smaller and right when it is bigger. That is wonderfully fast -- until the keys happen to arrive already in order. Then every key turns the same way and the tree grows into one long, lopsided chain, as slow to search as an ordinary list. An AVL tree is the same idea with a habit of self-tidying: after every insert it quietly straightens itself so that neither side of any node ever grows much taller than the other.

Step 2 -- Name the quantities, then one rule. Give every node a height (how many levels hang below it) and a balance factor $BF = h_{\text{left}} - h_{\text{right}}$. The single rule that defines an AVL tree is to keep $|BF| \le 1$ at every node. Insert the keys $1, 2, 3$ in that order. After $1$ and $2$ the root ($1$) leans right with $BF = -1$ -- still legal. Add $3$ and the root's balance factor falls to $BF = -2$: too lopsided. The tree responds with a rotation, a small local rearrangement that lifts $2$ up to become the new root with $1$ and $3$ as its children. The height drops from $2$ back to $1$ and searching is quick again.

Step 3 -- The precise version and the payoff. Heights are stored in each node (with the convention $h(\text{null}) = -1$) and updated only along the path back to the root, so restoring balance costs $O(\log n)$. There are exactly four imbalance shapes: LL and RR are fixed by a single rotation, while LR and RL need two. The reward is a proven height bound $h \le 1.44\,\log_2(n+2)$, which holds the cost of search, insert, and delete at $O(\log n)$ regardless of the order keys arrive -- compared with $O(n)$ for an unbalanced BST. In the controls above, the $n$ slider sets how many keys are used and the preset chooses their order: "Sorted" and "Reverse" are precisely the inputs that wreck a naive tree.

Step 4 -- Try this in the sim above. Set the preset to "Sorted" and drag $n$ to its maximum: that ordering would build a degenerate height-$(n-1)$ chain in a naive BST -- the exact disaster AVL is built to prevent (Section 3 shows why the AVL height instead stays near $1.44\,\log_2 n$). Switch between "Random" and "Sorted" and watch the Comparisons counter change. Then walk through with the Next and Prev buttons to follow the AVL-INSERT pseudo-code line by line, including the branch into each of the four rotation cases.

Step 1 -- AVL Invariant. For every node v: |height(v.left) - height(v.right)| <= 1. Called the balance factor (BF). After every insert or delete, BF must be restored via rotations.

Step 2 -- Height Bound. An AVL tree with n nodes has height h <= 1.44 log2(n+2) - 0.328. Proof: minimum nodes N(h) for height h satisfies N(h) = N(h-1) + N(h-2) + 1 (Fibonacci-like). N(h) grows as phi^h/sqrt(5). Inverting: h = O(log n).

Step 3 -- Four Rotation Cases. LL (left-left): single right rotation. RR (right-right): single left rotation. LR (left-right): left rotate child, then right rotate root. RL (right-left): right rotate child, then left rotate root.

Step 4 -- Insert Cost. Standard BST insert O(log n) + update heights O(log n) + at most ONE double or single rotation O(1). Total: O(log n) per insert.

Step 5 -- Delete Cost. BST delete O(log n) + at most O(log n) rotations propagating up the path. Total: O(log n). Deletions may require more rotations than insertions.

Step 6 -- vs Red-Black Tree. AVL: stricter balance (|BF|<=1), faster lookups (lower height ~1.44 log n vs RB ~2 log n), more rotations on insert/delete. Red-Black: fewer rotations (at most 3 total per insert), better for write-heavy workloads. Both O(log n).