AVL Trees — System Engineer

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:

Pattern	Shape	Fix
Left-Left	heavy-left, then heavy-left	Right rotation
Right-Right	heavy-right, then heavy-right	Left rotation
Left-Right	heavy-left, then heavy-right	Left-Right double rotation
Right-Left	heavy-right, then heavy-left	Right-Left double rotation

        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. After removing a leaf, propagate up the path to the root, rotating wherever the factor exceeds the limit. 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).

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

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