AVL trees (Adelson-Velsky and Landis, 1962) were the first self-balancing binary search trees. Every node stores a balance factor — the height difference between its left and right subtrees — and the invariant |balance| ≤ 1 guarantees the tree height stays O(log n) no matter what insertion order you feed it.

The Balance Invariant

Define height(node) as the longest downward path. For every node:

balance(node) = height(node.left) - height(node.right)

The tree is balanced when balance(node) ∈ {-1, 0, 1} for all nodes. This invariant bounds the height at 1.44 · log₂(n+2), so search, insert, and delete are all guaranteed O(log n) — worst case, not average.

Insert and Rotate

Insertion is a normal BST insert, then you walk back up recomputing balance factors. The first node whose balance becomes +2 or −2 is fixed with one of four rotations:

        y                x
       / \              / \
      x   C    =>      A   y
     / \                  / \
    A   B                B   C

A rotation is O(1) pointer surgery; the fix-up visits at most O(log n) ancestors, so insert stays O(log n).

Deletion Is Trickier

Deleting a node can unbalance several ancestors, not just one. The procedure:

1. BST delete — find the node, replace it with its in-order successor (or predecessor) if it has two children, then detach the physically-removed node.
2. Walk back up to the root, recomputing balance factors. The first node with balance +2 or −2 needs a rotation — and unlike insert, after fixing one node you must keep going up: the rotation shortens a subtree, which can unbalance a parent above it.
3. Delete has a distinct “inner-heavy” case. Insert only ever triggers rotations when the heavy child is also heavy in the same direction (or double-rotated). Delete can produce a node with balance +2 whose left child has balance 0 — the correct fix is a single right rotation, not a double rotation, and the resulting subtree ends at balance 0 rather than height-unchanged, so the imbalance may keep propagating upward.

A delete can need up to O(log n) rotations (insert needs at most one or two), though the amortized cost is still O(log n). The upshot for implementers: the insert fix is a bounded, local operation, while the delete fix is a loop from the deletion point to the root — which is exactly why practice item 4 is “the hard part.”

After deleting, walking up from the removed node:

  node balance  →  action
  −2 / +2, child heavy same direction  →  single rotation, then CONTINUE up
  −2 / +2, child heavy opposite        →  double rotation, then CONTINUE up
  −2 / +2, child balance 0 (delete only) → single rotation, then CONTINUE up
  in range                             →  recompute height, continue up
  at root                              →  done

Why a Strict Bound Matters

An ordinary BST fed sorted data degrades into a linked list — O(n) lookups. The AVL tree cannot degrade: the worst case is bounded by 1.44 · log₂(n). That strictness costs a little: rotations happen more often than in a Red-Black tree. AVL is better when lookups dominate; Red-Black is better when insertions/deletions dominate (it does fewer rotations).

Practice Trajectory

1. Insert a sequence that triggers all four rotation patterns; draw each rotation by hand.
2. Implement updateHeight and the four rotations, then insert with backtracking rebalance.
3. Verify the invariant: instrument every step and assert |balance| ≤ 1.
4. Implement delete-with-rebalance (this is the hard part).
5. Compare insertion counts and heights against a plain BST and a Red-Black tree.