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

Before we start, one shared reminder — every solution leans on these two facts:

Level 1 — Recognition

Goal: read a tree and report balance factors and legality. No rotations yet.

Exercise 1.1 — Compute every balance factor

Here is a tree. Compute the balance factor of every node and state whether the tree is a valid AVL tree.

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

The keys and shape are: 50 is the root; its left child is 30, its right child is 70. 30 has a left child 20 (a leaf). 70 has a right child 80 (a leaf).

Recall Solution 1.1

Work bottom-up, because a node's height needs its children's heights first.

20 — leaf → height $0$ , $B F = (- 1) - (- 1) = 0$ .
80 — leaf → height $0$ , $B F = 0$ .
30 — left child 20 (height $0$ ), right child empty (height $- 1$ ). Height of 30 $= 1 + max (0, - 1) = 1$ . $B F (30) = 0 - (- 1) = + 1$ .
70 — left empty (height $- 1$ ), right child 80 (height $0$ ). Height $= 1$ . $B F (70) = (- 1) - 0 = - 1$ .
50 — left child 30 (height $1$ ), right child 70 (height $1$ ). Height $= 2$ . $B F (50) = 1 - 1 = 0$ .

Every $B F \in {- 1, 0, + 1}$ → valid AVL tree. ✅

Exercise 1.2 — Name the case from a picture

A node $z$ has $B F (z) = + 2$ . Its taller child $y$ has $B F (y) = - 1$ . Which of LL / RR / LR / RL is this, and how many rotations does it need?

Recall Solution 1.2

$B F (z) = + 2$ is positive → $z$ is left-heavy → the problem is on the left (first letter L). $y$ is $z$ 's left child. $B F (y) = - 1$ is negative → $y$ is right-heavy → the trouble sits in $y$ 's right subtree (second letter R). Left then Right → LR case → needs two rotations: rotateLeft(y) first (straightens the zig-zag), then rotateRight(z).

Level 2 — Application

Goal: perform single inserts/rotations and report the resulting tree.

Exercise 2.1 — RR insert

Start empty. Insert 10, then 20, then 30 in that order. Show the final AVL tree.

Recall Solution 2.1

Insert 10 → root. Tree: 10.
Insert 20 → $20 > 10$ , becomes right child. $B F (10) = (- 1) - 0 = - 1$ . Legal.
Insert 30 → $30 > 10$ go right, $30 > 20$ go right → right child of 20. Now update up:
- $B F (20) = - 1$ (legal),
- $B F (10) = h e i g h t (empty) - h e i g h t (subtree 20) = (- 1) - 1 = - 2$ → unbalanced, right-heavy.
The new key 30 > 20 (= right child's key) → went into the right of the right → RR → single left rotation at 10.
Result: 20 root, 10 left, 30 right, height $1$ . ✅

Exercise 2.2 — LR insert, step by step

Start empty. Insert 30, then 10, then 20. Show both rotation steps.

Recall Solution 2.2

Insert 30 → root.
Insert 10 → left child of 30.
Insert 20 → $20 < 30$ go left, $20 > 10$ → right child of 10.
Update up: $B F (30) = h e i g h t (left = 1) - h e i g h t (right = - 1) = + 2$ → left-heavy. But new key $20 > 10$ (the left child's key) → it went into the right of the left → LR.
Step A — rotateLeft(30.left) i.e. rotate at 10: 20 rises above 10. Left subtree of 30 is now a clean straight line 20 → 10 (an LL shape).
Step B — rotateRight(30): 20 becomes the root, 10 its left child, 30 its right child.
Final: 20 root, 10 left, 30 right. All $B F = 0$ . ✅

Level 3 — Analysis

Goal: reason about heights, minimum node counts, and multi-step processes.

Exercise 3.1 — Minimum nodes of a height-4 AVL tree

Using $N (h) = 1 + N (h - 1) + N (h - 2)$ with $N (0) = 1$ and $N (- 1) = 0$ , compute $N (4)$ . Then verify $N (h) = F_{h + 3} - 1$ for $h = 4$ (using $F_{1} = 1, F_{2} = 1, F_{3} = 2, \dots$ ).

Recall Solution 3.1

Build the recurrence up from the base cases:

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

Fibonacci check: with $F_{1} = 1, F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5, F_{6} = 8, F_{7} = 13$ , the formula says $N (4) = F_{4 + 3} - 1 = F_{7} - 1 = 13 - 1 = 12$ . ✅ Matches.

Meaning: the sparsest possible AVL tree of height 4 still has 12 nodes, so 12 nodes can force at most height 4 — height grows only logarithmically. This is exactly why AVL search is $O (lo g n)$ (see Big-O Notation).

Exercise 3.2 — Height bound in practice

An AVL tree stores $n = 1, 000, 000$ keys. Using the bound $h \leq 1.44 lo g_{2} n$ , give the maximum possible height (rounded down). Compare to the worst-case height of an unbalanced Binary Search Tree with the same keys.

Recall Solution 3.2

$lo g_{2} (1, 000, 000) \approx 19.93$ . $h \leq 1.44 \times 19.93 \approx 28.7 \Rightarrow h \leq 28$ . So no search ever touches more than about 29 nodes (height + 1 levels).

A plain BST built from sorted input degenerates into a chain of height $n - 1 = 999, 999$ → up to a million comparisons. The AVL bound of ~29 is roughly 34,000× fewer in the worst case. That is the whole point of self-balancing.

Level 4 — Synthesis

Goal: combine insert/delete with rebalancing across several operations.

Exercise 4.1 — RL rotation triggered by deletion

Tree: 50 root, 30 left, 70 right, and 60 as the left child of 70. Delete 30. Show the rebalancing.

Recall Solution 4.1

Heights before deleting: 60 is a leaf (height $0$ ); 70 has left child 60, right empty → height $1$ ; 30 is a leaf (height $0$ ); 50 has left height $0$ , right height $1$ → height $2$ .

BST delete 30: 30 is a leaf → just remove it. Now 50 has no left child.
Update up: $B F (50) = h e i g h t (left) - h e i g h t (right) = (- 1) - 1 = - 2$ → right-heavy.
On delete we pick the case from the child's BF, not a key. Look at $B F (70)$ : left child 60 (height $0$ ), right empty (height $- 1$ ) → $B F (70) = 0 - (- 1) = + 1 > 0$ . A right-heavy $z$ whose right child leans left → RL case.
Step A — rotateRight(50.right) i.e. rotate at 70: 60 rises above 70.
Step B — rotateLeft(50): 60 becomes root, 50 its left child, 70 its right child.
Final: 60 root, 50 left, 70 right, all $B F = 0$ . ✅

Exercise 4.2 — Two inserts, two different rotations

Start empty. Insert 40, 20, 60, 10, 30, then insert 25. Identify every rotation.

Recall Solution 4.2

Insert 40, 20, 60, 10, 30 first — trace it:

40 root. 20 → left of 40. 60 → right of 40. (40 balanced, height $1$ .)
10 → left of 20. Update: $B F (20) = + 1$ , $B F (40) = h e i g h t (left = 2 ?)$ — recompute: left subtree of 40 is 20 with child 10 → height $1$ ; right is 60 → height $0$ . $B F (40) = 1 - 0 = + 1$ . Legal, no rotation.
30 → $30 < 40$ left, $30 > 20$ right → right child of 20. Now 20 has children 10 and 30 → height $1$ ; 40 left height $1$ , right height $0$ → $B F (40) = + 1$ . All legal.
Tree now: 40(root); left 20 with children 10,30; right 60.

Now insert 25:

$25 < 40$ go left; $25 > 20$ go right to 30; $25 < 30$ → left child of 30.
Update up. 30 now has left child 25 → height $1$ . 20 has left 10(h0), right 30(h1) → $B F (20) = 0 - 1 = - 1$ , height $2$ . 40: left 20(h2), right 60(h0) → $B F (40) = 2 - 0 = + 2$ → unbalanced at 40, left-heavy.
First unbalanced node going up is $z = 40$ . Its taller child $y = 20$ . New key 25 > 20 (right of the left) → LR case.
Step A — rotateLeft(40.left) at 20: 30 rises above 20; 25 becomes 20's right child. (20 → 30 straightened.)
Step B — rotateRight(40): 30 becomes root, left child 20 (with children 10, 25), right child 40 (with child 60).
Final root is 30, balanced. ✅

Level 5 — Mastery

Goal: design inputs and prove properties — the "why," not just the "how."

Exercise 5.1 — Design an input that makes a plain BST degenerate but AVL stay short

Give an insertion order of the keys 1,2,3,4,5,6,7 that turns an ordinary Binary Search Tree into a height-6 chain, then state the height of the AVL tree built from the same order.

Recall Solution 5.1

Sorted order 1,2,3,4,5,6,7 is the killer: in a plain BST each key is larger than all before it, so every insert becomes the right child of the previous → a straight chain of height $6$ (7 nodes, 6 edges). Search is $O (n)$ .

Same order into an AVL tree: rotations fire repeatedly (each ascending run of 3 triggers an RR left-rotation) and the tree self-balances into a perfectly balanced tree with 4 at the root:

        4
      /   \
     2     6
    / \   / \
   1  3  5   7

Height $= 2$ . So the maximum balanced height for 7 nodes is $⌊ lo g_{2} 7 ⌋ = 2$ . The AVL machinery converted a doomed $O (n)$ chain into an $O (lo g n)$ tree with the exact same input. ✅

Exercise 5.2 — Minimum inserts to force a rotation

What is the fewest keys you must insert into an initially empty AVL tree to trigger the very first rotation? Give an example order, and explain why fewer is impossible.

Recall Solution 5.2

Three keys. Example: 1, 2, 3 → after inserting 3, node 1 has $B F = - 2$ → RR left rotation. Any strictly ascending or strictly descending triple works.

Why not two? With one node, $B F = 0$ . With two nodes, the root has one child and one empty side → $B F = \pm 1$ , still legal (an off-by-one is allowed). Imbalance means $∣ B F ∣ = 2$ , which needs a height difference of 2 between the two sides — impossible until one side has height $\geq 1$ (at least 2 nodes) while the other stays empty (height $- 1$ ). That first happens on the third insert. ✅

Exercise 5.3 — Why is delete potentially $O (lo g n)$ rotations but insert only one?

Explain, in terms of subtree height, why a single insert needs at most one rotation while a delete can cascade rotations all the way to the root.

Recall Solution 5.3

Insert: adding a leaf can raise a subtree's height by at most $1$ . After you rotate at the first unbalanced node $z$ , the rotation restores that subtree to its pre-insert height. From $z$ upward, every ancestor sees the same height it saw before the insert → nobody else is unbalanced → one rotation total.

Delete: removing a node can lower a subtree's height by $1$ . You rotate at the first unbalanced node — but a rotation that rebalances can itself shorten that subtree by $1$ . That shortening looks, to the parent, exactly like another deletion on that side, so the parent may now be unbalanced too. This can ripple up every level → up to $O (lo g n)$ rotations. This asymmetry — grow-then-fix stops, but shrink-then-fix can keep shrinking — is the key difference. (Contrast with a Red-Black Tree, which caps recoloring/rotations differently.)

Recall One-line self-check before you close the page

After any structural change, from the changed spot upward: update height, read $B F$ , and if $∣ B F ∣ = 2$ , use sign of $B F (z)$ for left/right and key (insert) or child's $B F$ (delete) for straight/bent → pick exactly one of LL, RR, LR, RL.