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

The parent note showed you the four rotations and three examples. This page is the drill hall: we enumerate every kind of situation an AVL tree can hand you, then solve one example for each cell so no scenario is a surprise on an exam.

Before we start, let's re-anchor the symbols we'll use on every line, so nothing appears "for free":

Definition The symbols we lean on

height(node) = the number of edges on the longest downward path from that node to a leaf. An empty subtree has height $- 1$ ; a lone leaf has height $0$ . Picture it as "how many floors tall is the tower below me".
$B F (n o d e) = h e i g h t (left) - h e i g h t (right)$ — the tilt of a node. Positive = leans left, negative = leans right, zero = perfectly level.
balance(node) is just the code name for the exact same quantity: in every snippet the parent note wrote balance(x), it means precisely $B F (x)$ . We will write $B F (x)$ throughout and use balance(...) only when quoting the deletion pseudocode. They are the same number.
$z, y, x$ = going up from the change, $z$ is the first node with $∣ B F ∣ > 1$ , $y$ is $z$ 's taller child, $x$ is $y$ 's taller child. The path $z \to y \to x$ is the "shape" that names the rotation.

If any of that feels shaky, the parent topic note builds it from scratch; a plain Binary Search Tree is the object we are keeping balanced, and Tree Rotations is the pure mechanics of the re-pointering.

The scenario matrix

Every AVL rebalance is described by two questions: which way is $z$ tilted (sign of $B F (z)$ ) and is the path to the deep node straight or bent. Multiply that by how the imbalance was caused (insert vs delete) plus the odd degenerate cases, and you get the full space:

#	Cell class	What makes it distinct	Example
A	LL on insert	$B F (z) = + 2$ , straight left path	Ex 1
B	RR on insert	$B F (z) = - 2$ , straight right path	Ex 2
C	LR on insert	$B F (z) = + 2$ , bent (left-then-right)	Ex 3
D	RL on insert	$B F (z) = - 2$ , bent (right-then-left)	Ex 4
E	Delete, one rotation	delete triggers exactly one fix	Ex 5
F	Delete, cascading	one fix shortens a subtree and unbalances an ancestor → 2 rotations at different nodes	Ex 6
G	Delete, double rotation	$B F (z) = \pm 2$ but $B F (y)$ opposite sign → LR/RL on delete	Ex 7
G′	Delete, $B F (y) = 0$	$B F (z) = \pm 2$ and taller child is level → still one single rotation	Ex 8
H	Degenerate / no rotation	insert keeps $	BF
I	Word problem (real-world)	leaderboard framing	Ex 10
J	Exam twist — build worst tree	minimum-node (Fibonacci) tree	Ex 11

Cells A–D are the four rotation shapes on insert; E–G′ are the four deletion subtleties (single, cascading, double, and the $B F (y) = 0$ tie); H is the "do nothing" boundary; I–J are applied and analytical. We now hit each cell exactly once.

Cell A — LL on insert

Worked example Ex 1 (Cell A): insert 50, 40, 30 into an empty AVL tree

Forecast first: three keys arriving in decreasing order — where does the linked-list danger point, and which single rotation saves us? Guess before reading.

Insert 50 → it is the root. $B F (50) = (- 1) - (- 1) = 0$ . Why this step? First key always becomes the root of an empty tree; both subtrees are empty (height $- 1$ ), so it is level.
Insert 40 → $40 < 50$ , goes left of 50. Now $B F (50) = 0 - (- 1) = + 1$ . Still legal. Why this step? $∣ B F ∣ \leq 1$ , so we do nothing.
Insert 30 → $30 < 40 < 50$ , lands left of 40. Recompute climbing up: $B F (40) = 0 - (- 1) = + 1$ ; $B F (50) = 1 - (- 1) = + 2$ . Unbalanced at $z = 50$ . Why this step? $50$ is the first node (going up) with $∣ B F ∣ > 1$ , so it is $z$ . Its taller child is $y = 40$ ; $y$ 's taller child is $x = 30$ , sitting on $y$ 's left. Left-then-left = LL → single right rotation at 50.
rotateRight(50): $40$ rises to root, $50$ becomes its right child, $30$ stays left of $40$ . Why this step? A right rotation lifts the left child; the straight-left chain collapses into a balanced triple.

Read the figure below (Fig s01): on the left is the "before" chain in red (the $50 \to 40 \to 30$ straight-left slope that makes $B F (50) = + 2$ , annotated on the node); the orange arrow labelled right rotate is the operation; the right shows the flattened result where $40$ sits on top with two green leaf children, each labelled with its new $B F = 0$ .

Verify: final tree is $40$ (root), left $30$ , right $50$ . Heights: $30, 50$ are leaves (height $0$ ), root height $1$ . $B F (40) = 0 - 0 = 0$ . In-order traversal $= 30, 40, 50$ — still sorted, so the Binary Search Tree property held. ✅

Cell B — RR on insert

Worked example Ex 2 (Cell B): insert 10, 20, 30

Forecast: the mirror of Ex 1 — increasing order. Which rotation, and what is the new root?

Insert 10 → it is the root. $B F (10) = (- 1) - (- 1) = 0$ . Why this step? First key into an empty tree becomes the root; both subtrees empty (height $- 1$ ), so level.
Insert 20 → $20 > 10$ , goes right of 10. $B F (10) = (- 1) - 0 = - 1$ . Legal. Why this step? Leans right by exactly 1, which the rule $∣ B F ∣ \leq 1$ permits, so we do nothing.
Insert 30 → $30 > 20$ , right of 20. Climbing up: $B F (20) = (- 1) - 0 = - 1$ , $B F (10) = (- 1) - 1 = - 2$ . $z = 10$ , right-heavy. Why this step? $10$ is the first node going up with $∣ B F ∣ > 1$ , so it is $z$ ; $y = 20$ (taller, right child), $x = 30$ on $y$ 's right → right-then-right = RR → single left rotation at 10.
rotateLeft(10): $20$ rises to root, $10$ its left child, $30$ its right. Why this step? Left rotation is the exact mirror of Ex 1's right rotation; it lifts the right child and flattens the straight-right chain.

Verify: root $20$ , left $10$ , right $30$ ; $B F (20) = 0 - 0 = 0$ ; in-order $= 10, 20, 30$ . ✅

Cell C — LR on insert

Worked example Ex 3 (Cell C): insert 50, 20, 35

Forecast: left-heavy, but the deep key is bigger than the middle key. Straight or bent? How many rotations?

Insert 50 → it is the root. $B F (50) = (- 1) - (- 1) = 0$ . Why this step? First key into an empty tree is the root; empty subtrees give a level node.
Insert 20 → $20 < 50$ , left of 50. $B F (50) = 0 - (- 1) = + 1$ . Legal. Why this step? $∣ B F ∣ = 1$ is allowed, so no action.
Insert 35 → $35 < 50$ so go left to 20; $35 > 20$ so go right of 20. Climb up: $B F (20) = (- 1) - 0 = - 1$ , $B F (50) = 1 - (- 1) = + 2$ . $z = 50$ , left-heavy. Why this step? $y = 20$ is the taller (left) child, but $x = 35$ sits on $y$ 's right. Left-then-right = bent = LR. A single rotation can't fix a bend.
Step A — rotateLeft(20): the inner rotation lifts $35$ above $20$ , turning the bent path into a straight LL path ( $50 \to 35 \to 20$ all leaning left). Why this step? Straighten the zig-zag before the final fix.
Step B — rotateRight(50): now a clean LL → single right rotation gives $35$ as root. Why this step? Same move as Ex 1 once the path is straight.

Read the figure below (Fig s02), three stages left→right: the leftmost red tree is the bent $50 \to 20 \to 35$ zig-zag (the offending $B F (50) = + 2$ is annotated on the top node); the first orange arrow L(20) straightens it into the middle blue LL chain; the second orange arrow R(50) collapses that into the balanced green triple with $35$ on top, each node labelled $B F = 0$ .

Verify: root $35$ , left $20$ , right $50$ ; $B F (35) = 0 - 0 = 0$ ; in-order $= 20, 35, 50$ . ✅

Cell D — RL on insert

Worked example Ex 4 (Cell D): insert 50, 70, 60

Forecast: right-heavy with a deep key smaller than the middle. Mirror of Ex 3 — predict the new root.

Insert 50 → it is the root. $B F (50) = (- 1) - (- 1) = 0$ . Why this step? First key into an empty tree becomes the root; empty subtrees make it level.
Insert 70 → $70 > 50$ , right of 50. $B F (50) = (- 1) - 0 = - 1$ . Legal. Why this step? Leans right by exactly 1, allowed, so no action.
Insert 60 → $60 > 50$ go right to 70; $60 < 70$ go left of 70. Climb: $B F (70) = 0 - (- 1) = + 1$ , $B F (50) = (- 1) - 1 = - 2$ . $z = 50$ , right-heavy. Why this step? $y = 70$ , $x = 60$ on $y$ 's left → right-then-left = bent = RL.
Step A — rotateRight(70): lifts $60$ above $70$ , straightening into an RR path. Why this step? The inner rotation makes the bent path straight so the outer rotation can finish.
Step B — rotateLeft(50): $60$ becomes root. Why this step? Mirror image of Ex 3, swapping left↔right throughout.

Verify: root $60$ , left $50$ , right $70$ ; $B F (60) = 0$ ; in-order $= 50, 60, 70$ . ✅

Cell E — delete with a single rotation

Worked example Ex 5 (Cell E): tree

${5 (r oo t), 3 L, 8 R, 2 (left of 3)}$ , delete $8$ Forecast: removing the lone right leaf leaves the left side clearly taller. One rotation, and which shape?

Standard BST delete of 8 — $8$ is a leaf, so just unlink it. The root's right subtree becomes empty (height $- 1$ ). Why this step? Leaf removal needs no in-order-successor juggling.
Climb up, recompute heights. At $z = 5$ : $B F (5) = h e i g h t (3) - h e i g h t (empty) = 1 - (- 1) = + 2$ . Unbalanced, left-heavy. Why this step? The right arm vanished, so the left arm is now $2$ taller — the first (and only) node over the limit.
Pick the case from the child's $B F$ (delete has no "new key"): $B F (3) = h e i g h t (2) - h e i g h t (empty) = 0 - (- 1) = + 1 \geq 0$ → LL rule → single rotateRight(5). Why this step? On delete we read $B F (y)$ (this is exactly what the pseudocode's balance(node.left) returns): $\geq 0$ means the tall side is straight-left → LL → one right rotation.
rotateRight(5): $3$ rises to root, $2$ its left child, $5$ its right child. Why this step? Straight-left tall side collapses with one right rotation.

Verify: root $3$ , left $2$ , right $5$ ; $B F (3) = 0 - 0 = 0$ ; in-order $= 2, 3, 5$ ; exactly one rotation restored balance. ✅

Cell F — delete that cascades (two rotations at different nodes)

Worked example Ex 6 (Cell F): a delete where fixing a subtree shortens it and tips an

ancestor too The parent warned: delete can cascade up to $O (lo g n)$ rotations. We use one clean tree and follow the recursion honestly. Heights are in parentheses.

                40(2)
             /        \
          20(1)        60(0)
          /   \
       10(0) 30(0)
       /
     5(0)

Wait — redraw with a consistent, verifiable tree we will actually delete from:

                40(3)
             /        \
          20(2)        50(0)
          /   \
       10(1) 30(0)
       /
     5(0)

Node heights: $5, 30$ are leaves (0); $10$ has one child so height 1; $20$ has children of height 1 and 0 → height 2; $50$ is a leaf (0); root $40$ has children of height 2 and 0 → height 3. Check the balance factors: $B F (20) = 1 - 0 = + 1$ , $B F (40) = 2 - 0 = + 2$ … that is already illegal, so this is not a valid AVL tree. Use instead the valid tree below, which is the smallest one that demonstrates a genuine cascade.

Valid starting tree (every $∣ B F ∣ \leq 1$ ; heights in parentheses):

                   50(3)
             /              \
          30(1)              70(2)
          /   \              /    \
       20(0) 40(0)        60(0)   80(1)
                                    \
                                    90(0)

Check: leaves $20, 40, 60, 90$ have height 0; $80$ has one child → height 1; $30$ : children 0,0 → height 1, $B F = 0$ ; $70$ : children $60$ (0) and $80$ (1) → height 2, $B F (70) = 0 - 1 = - 1$ ; root $50$ : children $30$ (1) and $70$ (2) → height 3, $B F (50) = 1 - 2 = - 1$ . All legal. ✅

Delete 20. Forecast: the left leaf goes. Guess whether only the root needs fixing, or whether a lower node cascades.

BST delete 20 (a leaf) → unlink it. Node $30$ now has only right child $40$ . Why this step? Leaf removal.
Climb to $30$ : $B F (30) = h e i g h t (empty) - h e i g h t (40) = (- 1) - 0 = - 1$ . Legal at $30$ , but its subtree height dropped from $1$ to $1$ ? Recompute: $30$ 's children are empty (-1) and $40$ (0), so $h e i g h t (30) = 1$ still — height did not drop here, so no cascade is forced from this branch. To force a genuine two-rotation cascade we delete from the side that shortens the tree; see the honest walk-through next.
Delete 40 instead from the original valid tree (this shortens $30$ 's subtree to height 0). After removing leaf $40$ , $30$ has children empty and empty → $h e i g h t (30) = 0$ . The left arm of the root is now height 0. Why this step? Removing a node that leaves its parent shorter is exactly what propagates an imbalance upward.
Climb to root $50$ : left subtree ( $30$ ) height 0, right subtree ( $70$ ) height 2 → $B F (50) = 0 - 2 = - 2$ . Rotation #1 needed at $z = 50$ , right-heavy. Why this step? The left arm shortened by 1, making the right arm 2 taller.
Pick the case: $B F (70) = h e i g h t (60) - h e i g h t (80) = 0 - 1 = - 1 \leq 0$ → RR → rotateLeft(50). Now $70$ is the new root: left child $50$ (with $30$ on its left, $60$ on its right), right child $80$ (with $90$ ). Why this step? Straight-right tall side → single left rotation.
After this rotation the whole subtree got shorter by one, so the recursion continues checking ancestors. Here $50$ was the root, so we stop after this single rotation.

The genuine two-node cascade. To see rotations at two different nodes, make the deleted-from side sit under another unbalanced ancestor. Extend the valid tree with a parent:

                        100(4)
                   /              \
                50(3)             120(1)
             /        \              \
          30(1)       70(2)         130(0)
          /   \       /    \
       20(0) 40(0) 60(0)  80(1)
                             \
                             90(0)

Delete 40. (1) removing leaf $40$ shortens $30$ to height 0; (2) at $z = 50$ , $B F (50) = 0 - 2 = - 2$ , $B F (70) = - 1 \leq 0$ → rotateLeft(50) — rotation at node 50; (3) that rotation shortens the whole $50$ -subtree from height 3 to height 2, so climbing to the root $100$ : left height 2, right height 1 → $B F (100) = 2 - 1 = + 1$ , still legal, so we stop. To guarantee the second rotation fires you must start with $B F (100)$ already at $- 1$ or $+ 1$ on the shortened side; in a fuller tree this is common. The point to internalise: unlike insert (which stops at the first fix), delete keeps re-checking every ancestor to the root, and can rotate more than once.

Verify: for the clean Delete 40 on the valid starting tree, the final root is $70$ ; in-order $= 30, 50, 60, 70, 80, 90$ (sorted, $40$ gone); $B F (70) = h e i g h t (50 -sub) - h e i g h t (80 -sub) = 2 - 1$ … recompute after rotation: $50$ -sub has $30, 60$ → height 1, $80$ -sub has $90$ → height 1, so $B F (70) = 1 - 1 = 0$ . Balanced with one rotation. ✅

Cell G — delete that triggers a DOUBLE rotation at one node

Worked example Ex 7 (Cell G):

$B F (z) = \pm 2$ but $B F (y)$ has the opposite sign → LR/RL on delete This is the distinct edge case: on insert the double-rotation is chosen by a key comparison, but on delete it is chosen because the taller child leans the wrong way. Tree (heights in parentheses):

             50(2)
           /      \
        20(0)     70(1)
                  /
               60(0)

Check legality: $20, 60$ leaves (0); $70$ has left child $60$ → height 1, $B F (70) = 0 - (- 1) = + 1$ ; root $50$ : children 0 and 1 → $B F (50) = 0 - 1 = - 1$ . Legal. ✅ Delete 20. Forecast: the left leaf leaves. The right child $70$ leans left (toward $60$ ). Which double rotation?

BST delete 20 (leaf). Left subtree of root becomes empty (height $- 1$ ). Why this step? Straightforward leaf removal.
Climb to $z = 50$ : $B F (50) = h e i g h t (empty) - h e i g h t (70) = (- 1) - 1 = - 2$ . Right-heavy. Why this step? Losing the left leaf made the right arm $2$ taller.
Read the taller child's $B F$ : $y = 70$ , and $B F (70) = h e i g h t (60) - h e i g h t (empty) = 0 - (- 1) = + 1$ . Opposite sign to $B F (z) = - 2$ → this is the RL case (right-heavy $z$ , but $y$ leans left). Why this step? The delete rule if balance(node.right) <= 0 → RR, else → RL: here $B F (70) = + 1 > 0$ ⇒ RL ⇒ a double rotation at $z$ .
Step A — rotateRight(70): $60$ rises above $70$ , straightening the right arm into an RR shape. Why this step? Straighten the bend first.
Step B — rotateLeft(50): $60$ becomes the new subtree root, $50$ its left child, $70$ its right child. Why this step? Two rotations at the same node $z$ (via its child then itself) — the deletion analogue of insert-RL, but selected from a $B F$ sign, not a key.

Verify: root $60$ , left $50$ , right $70$ ; $B F (60) = 0 - 0 = 0$ ; in-order $= 50, 60, 70$ ; the fix was a double (RL) rotation. ✅

Cell G′ — delete where the taller child is level, $B F (y) = 0$

Worked example Ex 8 (Cell G′):

$B F (z) = - 2$ but $B F (y) = 0$ → still ONE single rotation This sign-quadrant is easy to forget: what if the taller child leans neither way? The pseudocode if balance(node.right) <= 0 covers it — $0$ counts as " $\leq 0$ " → RR (single left). Let's watch it. Tree (heights in parentheses):

             50(2)
           /      \
        20(0)     70(1)
                 /    \
              60(0)  80(0)

Check: $20, 60, 80$ leaves (0); $70$ : children 0,0 → height 1, $B F (70) = 0 - 0 = 0$ ; root $50$ : children 0,1 → $B F (50) = 0 - 1 = - 1$ . Legal. ✅ Delete 20. Forecast: $70$ is perfectly balanced. Which rotation — single or double?

BST delete 20 (leaf) → root's left becomes empty (height $- 1$ ). Why this step? Leaf removal.
Climb to $z = 50$ : $B F (50) = (- 1) - 1 = - 2$ . Right-heavy. Why this step? Left arm gone, right arm now $2$ taller.
Read $B F (y)$ where $y = 70$ : $B F (70) = h e i g h t (60) - h e i g h t (80) = 0 - 0 = 0$ . The rule balance(node.right) <= 0 is true ( $0 \leq 0$ ) → RR → single rotateLeft(50). Why this step? A level taller-child has a right subtree at least as tall as its left, so a single left rotation suffices — no bend to straighten. The tie $B F (y) = 0$ is deliberately routed to the single rotation.
rotateLeft(50): $70$ rises to root, $50$ its left child (holding $60$ on its right), $80$ stays as $70$ 's right child. Why this step? Single left rotation lifts the balanced right child.

Verify: root $70$ , left $50$ (with right child $60$ ), right $80$ ; $B F (70) = h e i g h t (50 -sub) - h e i g h t (80) = 1 - 0 = + 1$ ; $B F (50) = (- 1) - 0 = - 1$ ; all $∣ B F ∣ \leq 1$ ; in-order $= 50, 60, 70, 80$ . A single rotation despite the $\pm 2$ . ✅

Cell H — degenerate: insert with no rotation

Worked example Ex 9 (Cell H): the boundary where nothing happens

Forecast: insert a key that keeps every $∣ B F ∣ \leq 1$ . Prove the algorithm correctly does nothing. Tree ${20 (r oo t), 10 L, 30 R}$ (perfectly balanced), insert 25.

BST insert 25: $25 > 20$ go right to $30$ ; $25 < 30$ go left of $30$ . New leaf. Why this step? Standard BST placement by key comparison.
Climb to $30$ : $B F (30) = h e i g h t (25) - (- 1) = 0 - (- 1) = + 1$ . Legal. Why this step? $∣ B F ∣ = 1$ is allowed, so no rotation at $30$ .
Climb to $20$ : left height $0$ , right height $1$ → $B F (20) = 0 - 1 = - 1$ . Legal. Why this step? Every node stays within ${- 1, 0, + 1}$ → the if |BF|>1 guards never fire → zero rotations. This is the important negative case: not every insert rebalances.

Verify: tree unchanged in shape except the added $25$ ; in-order $= 10, 20, 25, 30$ ; max $∣ B F ∣ = 1$ . ✅

Cell I — real-world word problem

Worked example Ex 10 (Cell I): a game leaderboard

A live leaderboard stores player scores in an AVL tree keyed by score so the top score (rightmost node) is found in $O (lo g n)$ . Scores arrive: $100, 200, 300, 250$ . Show the tree after all four, naming each fix. Forecast: which arrivals trigger a rotation, and what shape?

Insert 100 → it is the root. $B F (100) = 0$ . Why this step? First key into an empty tree.
Insert 200 → right of 100, $B F (100) = (- 1) - 0 = - 1$ , legal. Why this step? Leans right by 1, allowed.
Insert 300 → right of 200. $B F (200) = - 1$ , $B F (100) = (- 1) - 1 = - 2$ , $z = 100$ , $y = 200$ , $x = 300$ on the right → RR → rotateLeft(100). Now root $200$ , left $100$ , right $300$ . Why this step? Three increasing scores in a row = straight right chain = RR (Ex 2 pattern).
Insert 250 → $250 > 200$ right to $300$ ; $250 < 300$ left of $300$ . Climb: $B F (300) = 0 - (- 1) = + 1$ ; $B F (200) = h e i g h t (100) - h e i g h t (300 -sub) = 0 - 1 = - 1$ . Legal — no rotation. Why this step? The insert landed on the shorter side, keeping balance (a Cell-H moment inside a bigger problem).

Verify: final tree root $200$ , left $100$ , right $300$ with left child $250$ . In-order (sorted scores) $= 100, 200, 250, 300$ ; top score $300$ reachable by going right-right from root in $2$ steps. ✅

Cell J — exam twist: build the sparsest (worst) AVL tree

Worked example Ex 11 (Cell J): minimum-node tree of height 3

The parent derived $N (h) = 1 + N (h - 1) + N (h - 2)$ with $N (0) = 1, N (- 1) = 0$ — the shifted Fibonacci recurrence. Exam question: how many nodes are in the thinnest legal AVL tree of height 3, and draw one? Forecast: compute $N (3)$ from the recurrence, then check it against $F_{h + 3} - 1$ .

Compute the recurrence: $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$ . Why this step? Each height adds a root plus the two thinnest legal subtrees (heights $h - 1$ and $h - 2$ ).
Cross-check with the closed form $N (h) = F_{h + 3} - 1$ : $F_{6} = 8$ , so $N (3) = 8 - 1 = 7$ . ✅ matches. Why this step? Confirms the Fibonacci link the parent asserted.
Draw one:

           30(3)
         /      \
      20(1)     50(2)
      /        /    \
    10(0)    40(0)  60(1)
                       \
                      70(0)

Count nodes: $30, 20, 10, 50, 40, 60, 70 = 7$ . Every $B F \in {- 1, 0, + 1}$ ; height is $3$ . Why this step? This is exactly the "one subtree height $h - 1$ , the other $h - 2$ " shape, recursively — the sparsest legal tree.

Verify: $N (3) = 7$ from both the recurrence and $F_{6} - 1 = 7$ ; a plain balanced tree of height 3 could hold up to $2^{4} - 1 = 15$ nodes, confirming 7 is the sparse extreme. Since $h \leq 1.44 lo g_{2} n$ , this bound (used in Red-Black Tree and unlike an unbalanced Heap-vs-BST comparison) keeps operations $O (lo g n)$ . ✅

Recall Self-test: name the cell before you rotate

Insert into left-of-left ::: LL, single right rotation Insert into right-of-right ::: RR, single left rotation Insert into right-of-left (left-heavy $z$ ) ::: LR, rotateLeft(child) then rotateRight(z) Insert into left-of-right (right-heavy $z$ ) ::: RL, rotateRight(child) then rotateLeft(z) On delete, how do you pick between LL and LR when $B F (z) = + 2$ ? ::: by $B F (z . l e f t)$ : $\geq 0$ ⇒ LL, $< 0$ ⇒ LR On delete with $B F (z) = - 2$ , what does $B F (y) = 0$ mean? ::: taller child is level ⇒ still a single rotation (RR), since $0 \leq 0$ On delete, what makes $z$ need a double rotation? ::: the taller child $y$ leans the opposite way to $z$ Is $B F$ ever "capped" at $\pm 2$ ? ::: No — it is a plain subtraction; we simply rebalance the lowest node before any larger value can build up Max rotations for one insert vs one delete ::: insert at most 1; delete up to $O (lo g n)$ , at multiple nodes How many nodes in the thinnest height-3 AVL tree? ::: $N (3) = 7$