The guarantee is not free. To see the price, measure where the BST was already doing fine — on shuffled input.

$ algo rotate -in s10k.jsonl
n = 10000, inserted in the order given

                 build cmps   build time    rotations     height
  BST (11)           157025       3.33ms            -         30
  AVL (12)           120660      4.551ms         6922         16

  rotations per insert: 0.692
  worst |balance| anywhere in the AVL tree: 1

  lookups: BST 16.703 cmps, AVL 12.540 cmps

The counter says the AVL is cheaper

BST  157,025 comparisons
AVL  120,660 comparisons

23% fewer. And that is true: the tree is shallower, so every insertion walks a shorter path, and the path length is the comparison count.

By the only instrument this course has used since lesson 1, balancing costs less than nothing.

The clock disagrees

The build time column in that output is one sample, and it is inside the noise — at 10,000 records both versions land between 2 and 3 ms and change places between runs. Lesson 6's rule applies: when the difference is small, one measurement means nothing.

So measure it properly:

$ go test -run XXX -bench 'Build|Lookup' -benchtime=20x -count=5

BenchmarkBuildBST-32       20    1859315 ns/op
BenchmarkBuildBST-32       20    1870065 ns/op
BenchmarkBuildBST-32       20    1800945 ns/op
BenchmarkBuildBST-32       20    1922465 ns/op
BenchmarkBuildBST-32       20    1940315 ns/op
BenchmarkBuildAVL-32       20    3202495 ns/op
BenchmarkBuildAVL-32       20    3352500 ns/op
BenchmarkBuildAVL-32       20    2894720 ns/op
BenchmarkBuildAVL-32       20    3288470 ns/op
BenchmarkBuildAVL-32       20    2817325 ns/op

Five runs each, and the ranges do not overlap: BST 1.80–1.94 ms, AVL 2.82–3.35 ms.

Building the AVL is about 1.65× slower — while doing 23% fewer comparisons.

Where the difference went

Into a column the counter cannot see:

rotations   6922

A rotation is four pointer assignments and two height recomputations. It is not a key comparison, so c.Hit() does not fire for it — and rightly does not: the counter measures comparisons, not all work.

Lessons 4, 6 and 11 each showed the counter running out of reach. This is the fourth, and the sharpest, because the two readings point in OPPOSITE directions:

The instrument said the AVL was cheaper. The clock said it was dearer. Both are right — they are measuring different things.

The counter is still the correct tool for an algorithm's complexity: it does not tie you to a machine and it does not change between runs. But it cannot see the constant, and the entire cost of balancing lives in the constant.

The other half: lookup

BenchmarkLookupBST-32      20    1514950 ns/op   (1.45–1.56 ms)
BenchmarkLookupAVL-32      20    1246885 ns/op   (1.25–1.33 ms)

Lookup in the AVL tree is about 1.16× faster, because the tree is shallower (16 against 30).

The trade, precisely

	BST (11)	AVL (12)
insert, shuffled input	1.80–1.94 ms	2.82–3.35 ms (1.65× slower)
lookup, shuffled input	1.45–1.56 ms	1.25–1.33 ms (1.16× faster)
height, shuffled input	30	16
height, -sorted	10,000	14
memory per node	88 B	96 B (the h field)

You pay on every insertion to avoid a case that may never arrive.

And that pays off if at least one of three things is true:

• you cannot guarantee the insertion order — and usually you cannot, because it comes from a database, a file or a user;
• you read more often than you write — then a 1.16× faster lookup sits on the scales against a 1.65× slower insert, and the ratio decides which way they tip;
• the worst case is unacceptable rather than merely unpleasant.

If none of them is true — if you generate the data yourself, shuffled, once, and only read it afterwards — lesson 11's tree is enough. Or, as that same lesson showed, a sorted slice is.