AVL insertion

The problem it solves

The plain BST has one fatal weakness, demonstrated two pages back: feed it sorted input — which real data loves to be — and it degenerates into a linked list, dragging every O(log n) promise down to O(n). The AVL tree is the historical first fix (Adelson-Velsky and Landis, 1962) and still the conceptually cleanest: a BST that refuses to become unbalanced, restoring itself after every insertion with at most two local rotations, so that height — and therefore every operation — stays logarithmic no matter what order the data arrives in.

The default input in the visualization above is deliberately sorted: the exact sequence that destroys a plain BST builds, here, a bushy logarithmic tree, with the repair work visible each time the chain tries to form. That side-by-side (open BST insertion with the same preset) is the whole argument for self-balancing structures, compressed into one comparison.

The intuition — and where it breaks down

A mobile — the hanging sculpture. Each joint balances two arms; hang a new ornament and some joint may tip too far. You don’t rebuild the mobile: you re-hang one joint so the heavy arm’s weight redistributes, and balance returns. Crucially, the fix is local — grab the tipping joint, rotate the heavy side up into its place, let the old joint swing down the light side — and everything hanging below just comes along.

The AVL’s “tipping” measure is the balance factor: left subtree height minus right subtree height, tracked at every node, legal values −1, 0, +1. An insertion changes heights only along the path it walked, so only those nodes can tip — and here’s the theorem the algorithm rides on: fixing the lowest tipped node fixes everything above it, because the rotation restores that subtree to its pre-insertion height. One repair site per insertion, ever.

Where the analogy breaks, and it’s exactly where learners fall: a mobile joint rotates freely, but a BST rotation must preserve the ordering invariant — and a single rotation only does so when the heaviness runs in a straight line (left-left or right-right). When the heavy grandchild is on the inside (left-right / right-left), one rotation just moves the kink; the fix is to first rotate the child, straightening the kink into a line, then rotate the tipped node. Four cases, but really two shapes: straight line (one rotation), kink (two). The prediction prompt at every imbalance asks you to name the case — the skill is reading the shape of the heavy path.

Loading…

A walkthrough you can check

Insert 1, 2, 3 — the smallest sorted sequence that breaks a plain BST.

1. 1 becomes the root.
2. 2 is larger: right child. Balance factors: root −1. Legal.
3. 3 is larger, larger: right child of 2. Now root 1 has balance −2 — tipped, and the heavy path from 1 runs right (to 2) then right (to 3): right-right, straight line. One left rotation at 1: 2 rises to the root, 1 swings down as its left child, 3 stays right. Heights: perfectly balanced, and the in-order reading — 1, 2, 3 — is unchanged.

That last clause is the non-negotiable check: rotations rearrange parents, never order. Continue inserting 4, 5, 6... and watch the pattern repeat — each new chain-attempt triggers one rotation, and the tree grows in height only every roughly-doubling of nodes. By 12 sorted insertions, a plain BST is 11 levels deep; the AVL is 3.

The invariant

Every node’s balance factor is in [-1, 0, +1] — checked in this repo by a property test over random insertion orders, alongside the BST ordering invariant (bounds-checked) and the sorted-in-order-reading check. Together they pin the structure completely: search-ordered, height-bounded, and — via the AVL height theorem — h ≤ 1.44·log₂(n+2). The worst-case AVL tree (a Fibonacci tree, where every node tips maximally legal) is the shape that achieves the 1.44; a test inserts sorted runs and asserts the bound holds.

The one-repair-per-insertion fact deserves its own line, because implementations that “helpfully” rebalance every ancestor are doing wasted work that masks the theorem: after the lowest tipped node is rotated, its subtree’s height equals its pre-insertion height, so no ancestor’s balance changed after all. Insertion repairs are O(1) rotations; it’s deletion that can cascade rotations all the way up (still O(log n) of them) — and that asymmetry is a favourite senior-level probe.

Complexity, derived

The walk down is BST insertion: O(h). The walk back up updates heights and finds at most one repair site: O(h). Rotations are O(1) pointer surgery — three links move, and the visualization animates exactly those links so the “arc” you see is the actual pointer change. With h ≤ 1.44·log₂ n by the invariant, everything is O(log n), guaranteed — the word guaranteed being what separates this from the plain BST’s “O(log n) if you’re lucky”.

The comparison interviews actually want: AVL vs red-black. AVL balances tighter (1.44·log n vs 2·log n height bound), so lookups are faster; red-black tolerates more imbalance, so insertions/deletions do fewer rotations. Read-heavy → AVL; write-heavy or general-purpose → red-black, which is why standard libraries (Java’s TreeMap, C++’s map) chose red-black. Being able to give that one-sentence trade-off, with the height constants, is the payoff of this whole page.

What people get wrong

Rotating the wrong node in the kink cases. Left-right at node X means: rotate X’s child left first, then X right. Rotating X alone relocates the kink without removing it — the balance factor stays illegal one level down. The case-naming prompt in the visualization is rehearsal for exactly this.

Recomputing heights from scratch. Height must be a stored field updated on the path (1 + max(children)), or every insertion silently costs O(n) in recomputation and the log n promise is fiction.

Rebalancing every ancestor after insertion. Harmless-looking, wrong model — see above; one repair suffices, provably.

Conflating “balanced” definitions. AVL-balanced (per-node height difference ≤ 1) is stricter than “height is O(log n)” and different from weight-balanced or “complete”. In a validation question, state which definition you’re checking before checking it.

Implementation notes across languages

Nobody ships AVL in a mainstream standard library — the productized balanced trees are red-black (Java TreeMap, C++ std::map) or B-tree variants (databases, Rust’s BTreeMap) — so AVL lives in interviews and in systems with extreme read-to-write ratios. Implementation-wise: store height (not balance factor) per node — it makes update one line and the balance a subtraction; write rotateLeft/rotateRight as pure link-swapping functions returning the new subtree root, and let insertion re-link via return values (node.left = insert(node.left, v) — the pattern whose dropped return value is the classic silent bug). In Python/JavaScript, the recursive form is clear and depth-safe because the tree is balanced — the structure protects its own recursion. The final connective fact: B-trees are the same balancing instinct generalized to disk pages, which is the one sentence that links this page to every database index you’ll ever meet.