AVL Trees

The 10-second versionCopy Anchor Link

The previous page ended on a cliffhanger: a binary search tree is only fast while it stays bushy, and nothing in the structure enforces that. An AVL tree is a BST that polices its own height. It stores one extra number per node — the balance factor, the difference in height between the left and right subtrees — and requires that number to stay in -1, 0, 1. After every insert or delete, it checks the path it just touched and, where the balance has gone bad, performs a rotation: a local O(1) pointer shuffle that lowers the heavy side without disturbing the sorted order. The result is the first tree in history whose worst case is O(log n) — no matter what order you insert.

Why this existedCopy Anchor Link

Go back to the failure we just watched. Feed a BST the keys 10, 20, 30, 40, 50, already sorted, and you don't get a tree — you get a linked list. Search, which was supposed to be O(log n), collapses to O(n). That's not a rare edge case: sorted or nearly-sorted input is everywhere — log files, timestamps, IDs assigned by a sequence, anything that arrives in order.

So by 1960 the community had a structure whose headline promise — logarithmic everything — evaporated the moment real, ordered data walked in the door. Everybody could feel the gap. What they needed was a tree that could notice it was getting lopsided and fix itself.

In 1962, two mathematicians at the Soviet Academy of Sciences, Georgy Adelson-Velsky and Evgenii Landis, published "An algorithm for the organization of information" and closed the gap. Their structure — soon known simply as the AVL tree, after their initials — was the first self-balancing binary search tree. It didn't just happen to be balanced on average; it guaranteed logarithmic height as an invariant you could prove. It is still the reference point every other balanced tree is described against.

Why it mattered then: it turned "trees are usually fast" into "trees are always fast." That guarantee is what let people actually build symbol tables, dictionaries, and databases on a search tree without holding their breath.

Inside the inventor's headCopy Anchor Link

The problem is sharp and simple: keep the tree's height logarithmic, always. The obvious first idea is brute force — whenever the tree looks lopsided, flatten it into a sorted list and rebuild it perfectly balanced, picking the median as the root each time.

That works beautifully... and it's a disaster. Rebuilding is O(n), and you'd trigger it constantly — after almost every insert. The fix has to be local:

Watch the two attempts side by side:

// Naive: after an insert, throw the tree away and rebuild it perfectly balanced.// Correct, but it's O(n) every time — and it fires over and over. Too slow.function buildBalanced(keys, lo, hi) {  if (lo > hi) return null;  const mid = (lo + hi) >> 1;       // the median becomes the root  const n = new Node(keys[mid]);  n.left  = buildBalanced(keys, lo, mid - 1);  n.right = buildBalanced(keys, mid + 1, hi);  return n;}

// Improved: fix it in place with one pointer shuffle — O(1), no rebuild.function rotateRight(y) {  const x = y.left;  y.left  = x.right;      // x's right subtree moves under y  x.right = y;            // y becomes x's right child  return x;               // x is the new root of this subtree}

That's the pivot, and it's the heart of the whole page. A rotation is local (O(1)), it preserves the inorder sequence (so the sorted order never changes — only the shape), and it moves one subtree down while lifting its child up. You never re-sort; you just re-hang pointers.

The second insight is even cleverer. After you insert one key, which nodes could possibly be out of balance? Only the ones on the path from the root down to the new leaf — every other subtree is exactly as balanced as it was a moment ago. So you don't scan the tree. You recheck that single path as you unwind the recursion, and the first place balance breaks, a rotation fixes it. Two facts pinned down the whole algorithm:

• Height is the quantity to watch, and it can be maintained in O(1) per node from its children.
• Balance factor = height(left) − height(right). Spot-shuffle whenever it hits ±2.

The final approachCopy Anchor Link

The algorithm, as a flowCopy Anchor Link

Insert is a normal BST descent; the only new work happens while the recursion unwinds, on the way back up:

The four rotation casesCopy Anchor Link

A single insertion can only create two kinds of imbalance: heavy-left or heavy-right, and each has a "straight" and a "zig-zag" flavor. That's the famous LL, RR, LR, RL:

Here's the LL fix (a single right rotation) drawn out. Watch the inorder sequence — A · x · B · y · C — stay identical before and after; only the shape changed:

The zig-zag cases (LR and RL) need two rotations because a single one would just flip the imbalance to the other side. Rotate the child first (turning the zig-zag into a straight LL or RR), then rotate the node.

The invariants that make it correctCopy Anchor Link

1. The BST property still holds. Rotations relocate subtrees but never reorder the inorder sequence, so key order is preserved by construction.
2. The height-balance property. For every node, |height(left) − height(right)| ≤ 1 — the balance factor lives in -1, 0, 1.
3. Every node's height is stored and exact. height = 1 + max(height(left), height(right)), refreshed bottom-up.
4. Height stays logarithmic, always. An AVL tree of n nodes has height at most about 1.44 · log₂ n — so search, insert and delete are guaranteed O(log n), worst case, regardless of insertion order.

A worked traceCopy Anchor Link

Insert 30, 10, 20 into an empty AVL tree:

• 30 becomes the root.
• 10 is smaller → 30's left child. Balance factor at 30 is +1 — legal.
• 20 is smaller than 30, greater than 10 → 10's right child. Unwinding, 10's balance is -1 (fine), but 30 now has a left subtree of height 2 and nothing on the right: balance factor +2.
• 30 is heavy-left, and the key went inward (down-right from 10) → that's the LR case. Rotate 10 left (turning it into a straight chain 30 → 20 → 10), then rotate 30 right.
• The 20 ends up as the root, with 10 on the left and 30 on the right. Height 2, every balance factor in range.

Three keys, two rotations, and the tree is a perfect little triangle instead of a leaning chain.

It in codeCopy Anchor Link

A complete AVL tree: stored heights, both rotations, and an insert that rebalances as it unwinds.

class Node {  constructor(key) { this.key = key; this.height = 1; this.left = null; this.right = null; }}const height  = (n) => (n ? n.height : 0);const balance = (n) => (n ? height(n.left) - height(n.right) : 0);const update  = (n) => { n.height = 1 + Math.max(height(n.left), height(n.right)); };function rotateRight(y) {  const x = y.left;  y.left = x.right;  x.right = y;  update(y); update(x);          // y is now lower, so update it first  return x;}function rotateLeft(x) {  const y = x.right;  x.right = y.left;  y.left = x;  update(x); update(y);  return y;}function insert(n, key) {  if (!n) return new Node(key);  if (key < n.key)      n.left  = insert(n.left, key);  else if (key > n.key) n.right = insert(n.right, key);  else return n;                 // no duplicates  update(n);  const bf = balance(n);  if (bf >  1 && key < n.left.key)  return rotateRight(n);                           // LL  if (bf < -1 && key > n.right.key) return rotateLeft(n);                            // RR  if (bf >  1 && key > n.left.key)  { n.left  = rotateLeft(n.left);   return rotateRight(n); } // LR  if (bf < -1 && key < n.right.key) { n.right = rotateRight(n.right); return rotateLeft(n);  } // RL  return n;}

Cost tableCopy Anchor Link

The headline is the worst case column: unlike the plain BST, it never says O(n). That guarantee is what makes AVL the first usable balanced tree — and the price is a little extra bookkeeping and a rotation or two per write.

Where you meet it todayCopy Anchor Link

• Read-heavy ordered indexes. Because AVL keeps the tree as short as theoretically allowed, a lookup touches the fewest nodes of any BST. When your workload is mostly get with occasional put, that tighter balance literally means fewer comparisons per query.
• Order-statistic structures. AVL nodes are easy to augment — add a subtree size and you can answer "the k-th smallest key" or "rank of this key" in O(log n), the backbone of in-memory leaderboards and score tables.
• Reference balanced tree. Many libraries and hand-rolled "sorted container" implementations ship an AVL tree precisely because its correctness argument is short and its rotations are easy to get right — you'll implement one yourself in almost any algorithms course.

// Feed it keys in order — the exact input that destroys a plain BST.let root = null;for (let k = 1; k <= 1000; k++) root = insert(root, k);console.log("height =", height(root));    // ~10, not 1000

RecapCopy Anchor Link

• AVL is the first self-balancing BST (Adelson-Velsky & Landis, 1962): a BST that maintains a height invariant instead of hoping for random inserts.
• The invariant: every node's balance factor — height(left) − height(right) — stays in -1, 0, 1.
• Repair is local: a rotation is an O(1) pointer shuffle that preserves the inorder order while reshaping the tree.
• Four cases cover every insert: LL and RR (one rotation), LR and RL (two).
• The payoff is a hard O(log n) worst case; the cost is one stored height and a rotation or two per write. Some structures choose to relax this — that's the next page.

Next up: Red-Black Trees — a looser balance that does fewer rotations, at the price of a cleverer invariant.