AVL & Red-Black Trees Simulator: self-balancing.

Why balanced trees? When trees turn into linked lists

When a tree quietly turns into a linked list.

A balanced binary search tree keeps its height O(log n) so search, insert, and delete stay logarithmic. Without balancing, an unlucky insertion order degrades the tree to a linked list. AVL trees (Adelson-Velsky & Landis, 1962) maintain a strict height invariant; red-black trees (Bayer, 1972 — Guibas & Sedgewick, 1978) use a coloured-edge invariant. Linux's CFS scheduler, Java's TreeMap, and C++'s std::map are all red-black trees.

A binary search tree is a beautifully simple structure: every node holds a key, every left descendant has a smaller key, every right descendant has a larger one. Search, insert, and delete all walk one path from the root, comparing as they go, and finish in time proportional to the tree's height. For a tree of a million nodes that height is around twenty if the tree is well-shaped — twenty comparisons to find any key.

The trouble is the words "if the tree is well-shaped." Imagine you build the tree by inserting keys one at a time, and the keys happen to arrive sorted. 1, 2, 3, 4, 5. Each new key is bigger than every existing key, so it lands as the rightmost descendant. The tree becomes a single right-leaning chain — every level has exactly one node. Searching for the largest element in such a tree of a million sorted-inserted keys takes a million comparisons, not twenty. Inserting the next sorted key takes another million. The asymptotic cost has degraded from O(log n) to O(n); the data structure is now indistinguishable from a linked list with two pointer fields per node instead of one.

This is not an exotic edge case. Sorted insertion happens whenever a system pulls keys from another sorted source: a database loaded from a CSV by primary key, a log file replayed in chronological order, an iterator over an already-sorted external collection. It is more common than the balanced case in real production systems. A binary search tree that promises O(log n) only sometimes is dangerously misleading; the worst case is the case you eventually meet.

A self-balancing tree solves this by spending a tiny amount of extra work on every write to keep the tree shape close to the ideal. The structure noticed each insert and, if the tree starts to lean, performs a small local rotation that re-balances three or four nodes in O(1) time. Two of the most popular variants — AVL (Adelson-Velsky & Landis, 1962) and red-black trees (Bayer 1972, Guibas & Sedgewick 1978) — guarantee a height of at most 2 log₂ n regardless of insertion order. The simulator above lets you watch the difference: insert 1..15 with AVL off and the tree turns into a fifteen-deep stick; turn AVL on and you get a four-deep balanced binary tree even though the inputs are still in sorted order.

Concretely: searching the unbalanced fifteen-element stick takes up to fifteen comparisons; the balanced version takes at most four. Scaling to a billion elements, the balanced tree takes thirty comparisons; the stick takes a billion — the difference between a microsecond and a minute. The price for the guarantee is small: each insert performs at most two rotations and updates two or three node fields. Reads are unchanged. Memory grows by one byte per node (a colour bit for red-black) or one int (a height counter for AVL). For most sorted-key workloads, this is the cheapest insurance you'll ever buy.

AVL tree — the height-balanced rule

AVL: no subtree may be taller than its sibling by more than 1.

An AVL tree maintains the invariant that for every node, the heights of its left and right subtrees differ by at most 1. The signed difference is the balance factor (bf): +1 means left is taller, 0 means equal, −1 means right is taller. Anything outside [−1, +1] triggers a rotation.

After an insert, you walk the path from the new leaf back to the root, updating heights as you go. At each ancestor you check the balance factor. If it stays within [−1, +1] you continue. If it exceeds the bound, you perform one of four rotations — Left-Left, Right-Right, Left-Right, or Right-Left — which restore the invariant at that node in O(1) time. Crucially, an insert needs at most one rotation (or one double-rotation), so the total cost is O(log n): a path walk plus a constant fix.

function insert(n, key) {
  if (n === null) 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);
  update(n); // recompute height

  const bf = height(n.left) - height(n.right);
  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;
}

A single rotation rearranges three nodes' parent pointers in O(1):

      y                        x
     / \                      / \
    x   T3   ----rotR(y)-->  A   y
   / \                          / \
  A   T2                      T2   T3

The keys in A < x < T2 < y < T3 stay in left-to-right order — the BST property is preserved exactly. Only the parent-child wiring changes, and the heights of x and y are recomputed.

AVL trees keep the worst-case height to about 1.44 · log₂(n + 2) — only 44% taller than a perfectly balanced tree. That's the tightest bound of any practical balanced tree. The cost: AVL has slightly more rebalancing on inserts and deletes than red-black trees, because the strict bound triggers more rotations on average.

Red-black tree — a colour instead of a height

Red-black: a colour instead of a height.

Red-black trees relax AVL's strict height balance in exchange for fewer rotations. Each node is coloured either red or black, and the tree maintains four invariants:

1. Every node is either red or black.
2. The root is black.
3. No two red nodes are adjacent (a red parent cannot have a red child).
4. Every root-to-leaf path passes through the same number of black nodes (the black-height).

These rules together guarantee that the longest root-to-leaf path is at most twice as long as the shortest. Worst-case height: 2 · log₂(n + 1) — looser than AVL's 1.44 multiplier but still O(log n). The pay-off is on rebalancing: most red-black inserts need only a colour flip (no rotation), and the upper bound on rotations per insert is 2. AVL needs the same bound but does more work to maintain stricter heights.

Implementing red-black correctly is famously fiddly. Sedgewick's left-leaning red-black tree (LLRB, 2008) reduces the case analysis from "ugly" to "manageable" by enforcing that every red link leans left. The simulator uses LLRB. The three operations are colour-flip, rotate-left, and rotate-right; insert is short:

function insert(h, key) {
  if (h === null) return new Node(key, RED);
  if (key < h.key) h.left = insert(h.left, key);
  else if (key > h.key) h.right = insert(h.right, key);

  if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
  if (isRed(h.left)  && isRed(h.left.left))  h = rotateRight(h);
  if (isRed(h.left)  && isRed(h.right))      flipColors(h);
  return h;
}

Red-black trees are the workhorse of standard libraries: C++'s std::map and std::set, Java's TreeMap and TreeSet, the Linux kernel's process scheduler (CFS) and many of its data structures, and Python's sortedcontainers backbone. The reason is operational: they stay fast under heavy mixed workloads, the colour bit costs only one extra bit per node, and rebalancing is cheap on average even if the formal bound is the same as AVL.

AVL vs red-black — same Big-O, different constants

Same Big-O, different constants.

The mental model: AVL is read-optimised, red-black is write-optimised. AVL keeps the tree maximally balanced so search is fastest, at the cost of more rebalancing on writes. Red-black tolerates a slightly taller tree (longer searches) in exchange for cheaper writes. The difference shows up on workloads with very high write-to-read ratios; in mostly-read workloads, AVL is marginally faster.

Both pale in cache-friendliness next to a B-tree when the dataset is large. Each node-to-child traversal in a binary balanced tree is a likely cache miss. A B-tree's wide nodes pack many keys into a single cache line and reduce the number of pointer chases dramatically. That's why every database index is a B-tree (or B+tree variant), not an AVL or red-black tree, even though they all give O(log n) writes. See the B-tree simulator for the comparison in motion.

In-memory, where everything fits in a few cache lines anyway, the binary balanced trees win because their per-node overhead is trivial. That's why std::map uses red-black, not B-tree.

Tree rotations — four rotations, two of them composite

Four rotations, two of them composite.

An imbalance after insert is always one of four shapes, named by the path from the parent to the inserted node. The first two are simple single rotations; the second two are double rotations (a bottom-level rotation followed by a top-level one). The simulator's rotation counter increments by 1 for each, so a Left-Right insert shows up as 2 rotations.

A rotation runs in O(1) — three pointer assignments and two height updates. But the path-walk to find the imbalance is O(log n). So an AVL insert in total: O(log n) walk + O(1) rotation = O(log n), with a small constant.

Try it in the simulator. With AVL selected, insert 30, 20, 10 in order. After 30 the tree is just one node; after 20 it's a left child; after 10 the chain becomes left-left, balance factor at the root hits +2, and a single right rotation fixes it. Now insert 40, 50 — the right side grows; 50 triggers a right-right imbalance and a left rotation rebalances. Insert 25: that's a left-right shape (left from 30, right from 20) and the tree does the double rotation. The rotation counter ticks up by 2.

Delete is half the story — the case AVL textbooks skip

Insert is half the story. Delete is the rest.

Most balanced-tree tutorials show insert and stop. Delete is harder — and writing a correct delete is what separates a practitioner from a textbook implementer. The simulator's insert is fully animated; delete is left out only because the case analysis would clutter the screen. Here is the code-level overview.

For a plain BST, deletion has three cases:

1. Leaf: just unlink it.
2. One child: replace the node with its only child.
3. Two children: find the in-order successor (the smallest node in the right subtree, found by going right once and then left as far as possible), copy its key into the deleted node, recurse to delete that successor in the right subtree. The successor always has zero or one child, so the recursion bottoms out in case 1 or 2 immediately.

For an AVL tree, you do the BST delete first, then walk back up the path rebalancing — exactly as on insert. The catch: an AVL delete may require multiple rotations on the path, not just one. After each rotation, the subtree's height may drop, which can re-trigger imbalance at the next ancestor up. So while AVL insert needs at most one (possibly double) rotation, AVL delete needs O(log n) rotations in the worst case.

function avlDelete(n, key) {
  if (n === null) return null;
  if (key < n.key) n.left = avlDelete(n.left, key);
  else if (key > n.key) n.right = avlDelete(n.right, key);
  else {
    // Found it — handle three cases
    if (n.left === null || n.right === null) {
      n = n.left ?? n.right;            // case 1 / case 2
    } else {
      const succ = minNode(n.right);    // case 3: in-order successor
      n.key = succ.key;
      n.right = avlDelete(n.right, succ.key);
    }
  }
  if (n === null) return null;
  update(n);
  // Same four-case rotation logic as insert
  return rebalance(n);
}

Red-black delete is famously the worst part of red-black trees. There are six rebalance cases (three on each side), each with sub-cases involving sibling colours and nephew colours. The reason is the black-height invariant: when you delete a black node, you're changing the black-height of the path it was on, and the invariant says all paths must have the same black-height. The fix involves either re-colouring siblings, performing rotations, or "borrowing a black" from elsewhere — each case picking the cheapest legal restoration.

Because red-black delete is so error-prone, many implementations use a different trick: top-down deletion (Sedgewick's variant) pushes the rebalancing logic into the descent, eliminating the post-delete fix-up. The downside is the descent is slightly more complex; the upside is no separate fix-up routine to test. The simulator and most textbooks use the recursive bottom-up form because it parallels insert.

A practical observation: many production codebases avoid implementing balanced-tree deletion altogether and instead use tombstones — mark the node deleted but leave the structure in place, and rebuild the tree (or the subtree) when tombstones exceed a threshold. This trades correctness simplicity for occasional rebuild cost. SQL Server's index pages do this; so do many in-memory caches.

Other balanced trees — Treap, splay tree, B-tree, Tango

Three siblings worth knowing by name.

AVL and red-black aren't the only self-balancing trees. Three other variants surface often enough that they deserve a mention.

Splay trees (Sleator & Tarjan, 1985) take a radical position: don't bother with explicit balance metadata at all. Instead, every operation — search, insert, delete — performs a splay that brings the accessed node to the root via a sequence of rotations. The amortised cost of any sequence of m operations is O(m log n), even though individual operations can be O(n). The compelling property: recently accessed nodes are near the root, giving excellent cache behaviour for skewed access patterns. Splay trees show up in compilers (symbol tables for tracking variable lookups), in some kernel data structures, and in any system where access locality is high. They're not the right choice when worst-case latency matters because individual operations can still be linear.

Treaps (Aragon & Seidel, 1989) marry a binary search tree (ordered by key) with a heap (ordered by a random priority). Each node has both a key and a priority; the keys form a BST and the priorities form a heap. Because the priorities are random, the resulting tree shape is what a randomly-built BST would look like — depth O(log n) with high probability. Insertion is "BST insert, then rotate up while priority is greater than parent's." Treaps are dramatically simpler to implement than red-black or AVL — about 50 lines for a complete treap with insert, delete, and split — yet give you O(log n) expected operations. They are the workhorse of competitive programming for this reason. The downside: O(n) worst case (if you're unlucky with the random source) and the random source must be repeatable for tests.

Scapegoat trees (Galperin & Rivest, 1993) use a different rebalancing strategy entirely. After insert, walk up the path; at the first ancestor where the subtree is "too unbalanced" by some weight ratio, rebuild that entire subtree from scratch in O(k) where k is the subtree size. Amortised insertion is O(log n) and the implementation is simpler than red-black. The interesting property: no per-node metadata at all (no colour, no height, no priority) — the only state is the global tree size. Scapegoat trees fit applications where compact node memory matters more than worst-case latency.

A useful classification:

A short curriculum for tree fluency

A short curriculum for tree fluency.

If you want to internalise these structures rather than memorise them, work through this list. Each step deliberately exposes a different sharp edge.

1. Implement a plain BST. Insert, search, delete (the three-case delete is the hard one). Print in-order to verify sorted output. Now insert sorted input and observe the degenerate stick.
2. Add height tracking. After each insert/delete, recompute heights bottom-up. Confirm height(empty) = 0, height(leaf) = 1.
3. Implement single rotations. rotateLeft and rotateRight as standalone functions. Test them by hand: build a small tree, rotate, verify in-order is unchanged.
4. Build AVL. Start from the BST; after every insert, walk back up updating heights and applying one of the four rotation cases. Insert 1..100 in order; verify the resulting height is around 7 (log₂ 100 ≈ 6.6).
5. Implement AVL delete. The trick: after deletion, rebalancing may need more than one rotation (unlike insert). Walk all the way to the root.
6. Build red-black (LLRB variant). Sedgewick's algorithms book has clean code. Insert 1..100; verify height is 12-14 (looser bound).
7. Compare empirically. Insert 1M random keys into both AVL and red-black, time the throughput. Then do 1M random deletes. Plot both: AVL is slightly faster on read, red-black slightly faster on write.
8. Range queries. Add range(lo, hi) that returns all keys in [lo, hi]. The traversal walks just the relevant subtree, O(log n + k) where k is the result size.
9. Order statistics. Augment each node with the size of its subtree. Now kthSmallest runs in O(log n). Useful for streaming median calculation.

Where balanced trees silently break — concurrency, memory layout

Where it silently breaks.

Forgetting to update heights upward. The single most common AVL bug: after insert, you must walk from the new leaf back to the root recomputing heights. Forget any node and its balance factor goes wrong; the tree drifts out of balance silently and the next operation may corrupt things further. Recursive implementations get this for free; iterative versions need an explicit parent stack.

Confusing balance factor and height. Height is non-negative; balance factor is signed (-1, 0, +1 for AVL). Some textbooks use the opposite sign convention (right minus left). Pick one and stick with it across your code.

Not normalising the root colour after red-black insert. The recursive LLRB insert can return a red root. The convention is that the root is always black, so do root.color = BLACK after every top-level call. The simulator does this.

Iterators that survive mutation. Standard library trees (std::map, TreeMap) invalidate iterators on insert/delete. Code that holds an iterator across a write is undefined behaviour in C++ and a ConcurrentModificationException in Java. Take a snapshot if you need to iterate during writes.

Comparing keys with floating-point equality. NaN poisons everything: NaN < x, x < NaN, and x === NaN are all false. Don't use floats as tree keys unless you sanitise NaN out first.

Further reading on balanced trees

Primary sources, in order.

• Adelson-Velsky & Landis · 1962
  An Algorithm for the Organization of Information
  Doklady Akademii Nauk SSSR. The original AVL paper, four pages and translatable in an afternoon. Foundational.
• Sedgewick · 2008
  Left-Leaning Red-Black Trees
  The paper that simplified red-black insert/delete by 60%. The simulator's red-black mode follows this design.
• Sleator & Tarjan · 1985
  Self-Adjusting Binary Search Trees
  JACM. The splay tree paper. Amortised O(log n) without explicit balance metadata.
• CLRS · 4th ed., 2022
  Introduction to Algorithms — Chapter 13
  The canonical academic treatment of red-black trees. Heavy but thorough; the case-by-case proof of insert and delete is the gold standard.
• Sedgewick & Wayne · 2011
  Algorithms, 4th ed. — Chapter 3.3
  The gentlest readable introduction, including LLRB. Free Java code on the book site.
• Aragon & Seidel · 1989
  Randomized Search Trees (Treaps)
  FOCS 1989. 50 lines of code, expected O(log n), randomised priority. The competitive programmer's favourite.
• Knuth · TAOCP Vol. 3
  Sorting and Searching, Section 6.2.3
  The most exhaustive treatment of balanced search trees ever written. Cited by every paper above.
• Sedgewick · Coursera
  Algorithms, Part I — Princeton
  Free MOOC. Week 4 covers BSTs and balanced search trees with the LLRB construction. The clearest pedagogical path.
• MIT 6.006 · OCW
  Introduction to Algorithms — Lectures 6–8
  Erik Demaine on AVL trees, augmentation, and amortised analysis. Free MIT lectures.
• Semicolony simulator
  B-tree
  Wider fan-out, disk-resident, the right shape when nodes don't fit in cache. Same O(log n) story, different constants.
• Semicolony simulator
  Heap
  A different balanced-tree shape that gives priority queue semantics — “the smallest” rather than “by key.”