Red-Black Tree

Start with the search problem

A binary search tree is useful because it turns ordered data into a decision process. At each node, the value is either equal, smaller, or larger. If the tree is balanced, one comparison removes about half of the remaining possibilities.

That is the whole reason logarithms appear here. O(log n) does not mean magic speed. It means the remaining work shrinks by a constant factor each step. With 31 sorted keys, a balanced shape needs only about five levels to decide where a value is.

Why this tree exists

A normal binary search tree is only fast when it stays balanced. If values arrive in sorted order, the tree can collapse into a linked list, and search moves from logarithmic time toward linear time.

A red-black tree is a binary search tree with a small amount of color metadata. The colors do not store application data. They are a bookkeeping trick that keeps the tree approximately balanced while allowing insert and search to remain efficient.

The failure mode

The sorted insertion example is the important warning. A binary search tree does not automatically balance itself. If every new value is larger than the previous value, each insert walks right, attaches a new right child, and creates a long chain.

Searching that chain is no better than scanning a linked list. The reader can see this by searching for the last sorted value: the search path visits almost every node, so the behavior becomes O(n) instead of O(log n).

The rules

Red-black trees use five rules. The root is black. Every node is red or black. Every missing child, usually called a NIL leaf, is treated as black. A red node cannot have a red child. Finally, every path from a node down to its NIL leaves must contain the same number of black nodes.

Those rules are enough to prevent one side of the tree from growing wildly taller than the other. The tree is not perfectly balanced, but it is balanced enough that lookup, insertion, and deletion stay bounded by O(log n).

Insertion intuition

New values are inserted like a regular binary search tree node, and the new node starts red. Starting red is less disruptive because it does not immediately change the black count on every path.

The problem appears when the new red node has a red parent. That creates a red-red violation. The fix depends on the uncle node. If the uncle is red, the tree recolors parent and uncle black, pushes red upward to the grandparent, and checks again higher in the tree. If the uncle is black, the tree rotates around the grandparent and recolors the parent/grandparent pair.

Rotations

A rotation is a local pointer change that preserves sorted order. A left rotation moves a right child up. A right rotation moves a left child up. The inorder sequence is unchanged, which means the binary search tree property remains intact.

before:
  x.right = y
  y.left  = b

after left rotate at x:
  y.left  = x
  x.right = b

Rotations are why a red-black tree can repair itself without moving every node. Most fixes touch only a small neighborhood: node, parent, uncle, and grandparent.

Black height

Black height is the count of black nodes on any path from a node to a NIL leaf. The important part is equality: from the same starting node, every downward path must have the same black height.

This does not mean every path has the same total number of nodes. Red nodes can appear between black nodes, but because red nodes cannot be adjacent, the longest path cannot be more than about twice as long as the shortest path.

Where it shows up

Red-black trees are useful when the workload needs ordered keys, predictable worst-case behavior, and fast updates. They are common in systems code, language runtimes, schedulers, memory managers, and map/set implementations.

They are not always the best answer. Hash tables are often faster for direct lookup, B-trees are better for disk and page-oriented storage, and arrays can win when the data is small and cache locality dominates. A red-black tree shines when order and stable logarithmic updates matter at the same time.

Summary

• Colors: metadata used to enforce balance rules.
• Recoloring: moves a violation upward when parent and uncle are both red.
• Rotations: local pointer changes that preserve sorted order while repairing shape.
• Guarantee: search, insert, and delete remain O(log n) because the tree height stays bounded.