Five tasks.

---

1. Break it in exactly one place

Three sabotages, one line each. Apply them one at a time and run the whole suite after each.

A. Step 3's trap — do not take the result:

n.left = insert(n.left)   // correct
insert(n.left)            // A

B. Delete one case from rebalance — the left-right one.

C. After a rotation, call fix only on the node that moved up, not on both.

Here is what happens:

A  --- FAIL: TestAVLStoresAndFinds
       Get("00000"): ok=false id=0, want id=1

B  --- FAIL: TestRotationsPreserveTheOrdering
       balance 2 after 98 inserts, want <= 1

C  --- FAIL: TestRotationsPreserveTheOrdering
       balance 14 after 98 inserts, want <= 1
   --- FAIL: TestHeightStaysBoundedOnSortedInput
       n=1000: height 170 exceeds the AVL bound 14.0

Explain each. B especially: why does it break the balance invariant while staying under the height bound? Run it and look at the height it produces for the zigzag order — the number is under the bound, and worse than the correct version's.

Then the question that matters: B is caught only by the test that checks during the build. Why would a check at the end not have been enough?

---

2. Which rotation fires when

Add four counters to rebalance — one per case — and build the tree in four insertion orders.

order              LL       LR       RR       RL      total
shuffled         1100     1191     1204     1118       6922
ascending           0        0     9986        0       9986
descending       9986        0        0        0       9986
zigzag           1880     3111     1865     3127      16221

Explain each row:

• why does ascending order need no double rotation at all?
• why is descending its exact mirror?
• why do the doubles dominate in the zigzag?
• and why is the zigzag total 16,221 rather than 9,986, with the same number of nodes? (Add up the columns — the answer is in there.)

---

3. The sparsest possible AVL tree

Step 2 derived the bound from N(h) = 1 + N(h−1) + N(h−2). Check whether it is tight.

Compute N(h) and feed it into the bound formula:

   h     N(h)   bound(N)
   4        7       4.24
   6       20       6.10
   8       54       8.04
  10      143      10.01
  12      376      12.01

The bound converges onto h. So the constant 1.4405 was not picked out of the air — it is the reciprocal of log₂(φ), where φ is the golden ratio.

Show that 1 / log2(1.618...) ≈ 1.4404. Explain why a Fibonacci sequence turns up in a tree that knows nothing about Fibonacci.

---

4. Relax the invariant

Change the condition from |balance| > 1 to |balance| > k and measure both inputs:

shuffled input                        sorted input
     k   height    rotations               k   height    rotations
     1       16         6922               1       14         9986
     2       17         3157               2       15         9985
     3       19         1802               3       16         9984
     5       22          682               5       18         9982
    10       28           67              10       23         9977

On shuffled input k = 2 halves the rotations for the price of one level. That looks like a good deal.

On sorted input it saves nine rotations out of 9,986, and the height grows.

Explain why relaxing helps where no help was needed, and does nothing where the whole thing was bought for. Then answer: is k = 2 a good idea?

---

5. Where this tree still loses

In step 6 the AVL won on lookup and lost on insertion. But lesson 11 had a third contender — a sorted slice with a binary search.

Measure all three at n = 10,000 on shuffled input: build, lookup, memory, and what one insertion into the middle costs.

Then name the single column where the AVL beats the slice — and explain why that one column is enough for a library index and not enough for transit's departure table.