Lesson 11 ended on this table:

insert order        n   height     log2 n    cmps/lookup  lookup time
shuffled        10000       30       13.3           16.7      2.488ms
-sorted         10000    10000       13.3         5000.5    532.978ms

Height 10,000. 5000.5 comparisons — exactly what lesson 1's linear scan cost.

The same command. The same two files. Only now there are two more rows at the bottom:

$ algo balance -shuffled s10k.jsonl -sorted s10k-sorted.jsonl

structure  insert            n   height     log2 n    cmps/lookup  lookup time
BST (11)   shuffled      10000       30       13.3           16.7      1.667ms
BST (11)   -sorted       10000    10000       13.3         5000.5    354.556ms
AVL (12)   shuffled      10000       16       13.3           12.5          1ms
AVL (12)   -sorted       10000       14       13.3           12.4        998µs

Read the last row again

Height 14. log2(10000) is 13.3.

The input that turned lesson 11's tree into a 10,000-level list now produces a tree one level off perfect.

And something you would not expect

Compare the two AVL rows against each other:

AVL  shuffled   height 16   12.5 comparisons
AVL  -sorted    height 14   12.4 comparisons

Sorted input is BETTER for an AVL tree than shuffled input.

That is not a fluke. Random order produces a lopsided tree that the rotations correct to "good enough"; strictly ascending order forces a rearrangement after every single insert, which drives the tree towards very nearly perfectly full.

Lesson 11's worst case is lesson 12's best case.

And one more row you were not expecting

BST  shuffled   height 30   16.7 comparisons
AVL  shuffled   height 16   12.5 comparisons

On shuffled input the BST was fine — that is why lesson 11 had no complaint about it. And the AVL still wins there by 25%.

So balancing is not only insurance against the bad case. It improves the average one too. But it is paid for, and step 6 measures where the cost hides — in a place your counter cannot see.

Guess before you read on

Height 14 at 10,000 records. What will it be at a million, if the input is still strictly ascending?

Write the number down. Step 5 has it in a table.