This lesson does not end with a solution. It ends with you knowing exactly what is broken.

What is NOT enough

Four obvious fixes, and why each is too weak:

"Shuffle the data before inserting." That fixes the initial build and nothing else. Afterwards Put is called by the program whenever a record appears, and you do not control the order of those calls. A user entering books alphabetically recreates the same problem within a week.

"Rebuild the tree when it gets too deep." Each rebuild is O(n). If the data arrives sorted this will happen over and over, and you end up with a structure that periodically stops in order to avoid the slowness it just caused.

"Use a sorted slice, like transit." Step 6 showed why that is a good idea — and where it breaks. Inserting into the middle of a slice is O(n). The trade just moves: from "lookup can degenerate" to "insertion is always slow".

"Go back to the hash table." Then you have no ordering, which is what this lesson was for. Step 1 returns you to the starting position.

What has to be true

Write down the requirements and they line themselves up:

1. the tree must rearrange itself during an insertion, not after it;
2. the rearrangement must cost no more than the insertion's own descent — O(log n), not O(n);
3. after rearranging, the BST invariant must still hold — step 2's sentence, with no exceptions;
4. and after any sequence of insertions the height must stay O(log n) — a guarantee, not a hope.

The fourth line is the important one, and the whole difference is in it. A randomly-built tree already gives about 2.3 × log2 n. That is not bad — but it is luck, not a promise. You noticed this in step 5: that number had to be measured, because nothing enforces it.

Lesson 11 built a structure that is usually O(log n). Lesson 12 builds one that is O(log n) always.

That difference — between "usually" and "always" — is the entire AVL tree.

What you have now

An ordered index that answers six questions instead of one, and that knows its own depth.

And a known defect that a test will not let you quietly forget: TestSortedInsertDegeneratesIntoAList requires Height() == n. As long as it passes, the tree is a plain BST.

In lesson 12 that test has to stop passing — one of the few times in this course when breaking a test is the goal.