Lesson 11's node gains one new field — its own height — and the whole guarantee grows out of that.

The balance factor

balance(n) = height(n.left) − height(n.right)

The AVL invariant: for every node, balance(n) is −1, 0 or +1.

Not "the tree looks reasonable" — a condition you can check at every node. That is exactly why it can be guaranteed rather than hoped for.

Why that is enough

Why does a local condition bound the height of the whole tree? Turn it around: what is the smallest number of nodes that can still build an AVL tree of height h?

The root has at least one subtree of height h−1, and by the invariant the other cannot be shorter than h−2. So:

N(h) = 1 + N(h−1) + N(h−2)

That is Fibonacci. The node count grows exponentially in the height, so the height grows logarithmically in the node count. Precisely:

h ≤ 1.4405 · log2(n + 2) − 0.3277

Remember that line: the test checks exactly this, not a number somebody eyeballed.

A rotation

A rotation reassigns three pointers and changes the height without breaking the BST invariant. That is the whole reason it is useful.

      n                b
     / \              / \
    b   C    =>      A   n
   / \                  / \
  A   x                x   C

Follow the keys. Before, x is to the right of b, so x > b; and it is inside b's subtree under n's left, so x < n. After, x is to the left of n — still between b and n. The only place it can be, and that is where it goes.

The other direction is the mirror image.

Four cases, two of which are the same one twice

When a node breaks the invariant, the excess came from one of its four grandchildren. The two "outer" cases take a single rotation; the two "inner" ones are first turned into outer ones:

rebalance(n):
    fix(n)                                  // recompute n's height
    b ← balance(n)

    if b > 1  and balance(n.left) ≥ 0:      // left-left
        return rotateRight(n)

    if b > 1:                               // left-right
        n.left ← rotateLeft(n.left)         //   make it left-left
        return rotateRight(n)

    if b < −1 and balance(n.right) ≤ 0:     // right-right
        return rotateLeft(n)

    if b < −1:                              // right-left
        n.right ← rotateRight(n.right)      //   make it right-right
        return rotateLeft(n)

    return n

The inner cases are not new machinery — they are the same two rotations applied twice. There are four cases to write down and one operation plus its mirror to understand.

Where it gets called

Insertion becomes recursive, because the repair happens on the way back up:

insert(n, item):
    if n = nil:                     return a new leaf
    c.Hit()
    if item.Title < n.key:          n.left  ← insert(n.left, item)
    if item.Title > n.key:          n.right ← insert(n.right, item)
    else:                           n.item ← item; return n

    return rebalance(n)             // ← the entire difference from lesson 11

In lesson 11 that last line was return n. Everything else is the same function.

Having descended a path to a leaf, you come back up the same path and check every node on it. The path is O(log n) long, so there are O(log n) checks. Actual rotations are far fewer; how many, you measure in step 6.