← Back to the section

A plain binary search tree is fine while it stays balanced, but it degenerates into a linked list when keys arrive in sorted order — and lookup drops from O(log N) to O(N). A red-black tree solves exactly that: it balances itself on every insert and delete, guaranteeing O(log N) whatever the order of the data. The price is a more complicated algorithm.

The idea: never let the tree lean

Balancing means the tree must not become too "one-sided" — branches should stay roughly the same depth. Levelling the tree completely on every insert is expensive, so a red-black tree settles for a compromise: it is not perfectly balanced, but it guarantees that the longest branch is at most twice the shortest one. That is enough to keep O(log N).

To track the balance, every node carries a color — red or black. The color is not data, it is a bookkeeping mark that tells the tree when it is time to rebuild.

The red-black rules

A tree counts as balanced while five rules hold:

  1. every node is either red or black;
  2. the root is always black;
  3. the ends of branches — the empty stubs standing in for missing children — count as black;
  4. a red node has two black children (no two reds in a row);
  5. every path from a node down to an end contains the same number of black nodes.

The third rule looks like a formality, but the fifth does not work without it: if the ends of branches were not nodes, it would be unclear what exactly we count black nodes up to. Implementations usually do not store those stubs as objects — they simply agree that null is black.

The point is in the last rule: it stops one branch from growing much longer than another. As soon as an insert breaks the rules, the tree restores them — and restores the balance along the way.

Two repair tools

Recoloring (color flip) is just swapping node colors. It is the cheap operation: sometimes repainting the node's parent and "uncle" is enough to get rid of two reds in a row.

Rotation rebuilds the shape of the tree. A node moves down while one of its children moves up into its place, and the "left is smaller, right is bigger" rule still holds. Rotations come in left and right flavors; they physically straighten a skewed branch, making the tree lower and more even.

left rotation around 10 root 20 is black 10 30 20

The rotation levels the height (3 → 2), the recoloring brings back the five red-black rules, and lookup stays O(log N).

What happens on insert

A new node is always inserted red (so that the black-count rule is not broken) at its ordinary place in the search tree. If its parent is black, the job is done. If the parent is red, two reds end up in a row (rule 4 is broken), and the tree repairs that with recolorings and rotations, walking up from the insertion point to the root. At the end the root is painted black if needed. The number of such repairs is small — proportional to the height of the tree, that is O(log N).

This is easy to measure: give the tree a comparator with a counter, pour in a thousand keys in ascending order — the worst input for a search tree — and look the last one up.

live example

import java.util.Comparator;
import java.util.TreeMap;

public class SortedInsert {
    static int compares = 0;

    public static void main(String[] args) {
        Comparator<Integer> counting = (a, b) -> { compares++; return Integer.compare(a, b); };
        TreeMap<Integer, String> tree = new TreeMap<>(counting);
        for (int key = 1; key <= 1000; key++) tree.put(key, "order " + key);
        compares = 0;
        tree.get(1000);
        System.out.println("comparisons to find the last of " + tree.size() + " keys: " + compares);
    }
}
Run

Running examples is part of paid access. There the same code runs inside the article: editor, run and check next to the paragraph. Three free days →

Seventeen comparisons instead of a thousand: the path to the farthest key fits into roughly two logarithms. A plain search tree on this input would have degenerated into a list and walked all 1000 nodes.

How it is done in Java

A red-black tree is not textbook exotica: the ordered maps and sets of standard libraries are built on it. And at the same time it is that rare case where "write it yourself" is bad advice even as an exercise: rotations and recolorings have a dozen symmetric cases, it is easy to get one wrong, and hard to notice — the tree keeps answering correctly, it just quietly stops being balanced. Understanding how it works is still worth it: otherwise it is unclear what you are paying extra for when you pick an ordered collection over a hash table.

The reference implementation is TreeMap (and TreeSet, which is just a TreeMap without values inside). It is literally the tree described above: besides the key, the value and three links (left, right, parent), every node has a color field — a single boolean flag. An insert goes as in a plain search tree and then walks up to the root, repairing violations with the very same recolorings and left-right rotations. The color is not visible from outside: balancing has no settings and no methods — it is simply there.

The complexity that follows is honest, with no "on average" caveat: get, put and remove are guaranteed O(log n) for any insertion order. The cost of the balancing itself is more interesting. There can be up to O(log n) recolorings on insert — they climb toward the root — but no more than two rotations, and no more than three on delete. A rotation is pricier than a recoloring: it relinks several nodes at once. The fact that rotations always stay in single digits is why libraries settled on the red-black tree rather than a more strictly balanced one (AVL, say): that one would be slightly lower and slightly faster on lookup, but would pay with rotations on every write.

You pay for the ordering with memory and with the constant factor. Every TreeMap entry is a separate object with six fields scattered across the heap, and reaching it means several jumps along references. For point access by key a hash table is noticeably faster. So TreeMap is not taken "just in case", but when order or range queries are genuinely needed.

The trap. Loading already sorted data into the tree one entry at a time is the most expensive way to build it: every insert first searches for the place and then runs the balancing. If the source is already ordered, the tree can be built ready-made:

SortedMap<Long, Order> source = ...;
Map<Long, Order> copy = new TreeMap<>(source);

The constructor taking a SortedMap (and putAll into an empty TreeMap) walks the source in order and lays the nodes out correctly right away, without comparing keys at all: a linear pass instead of n inserts with rebuilds. One by one, those same 1000 keys cost about 14,500 comparisons; the wholesale copy costs zero. On a hundred entries the difference is invisible, on a million it is not.

In short

  • A plain search tree degenerates on sorted data; a red-black tree balances itself and holds O(log N) for any insertion order.
  • Balance is tracked through node colors (red/black) and five rules; the key one is the same number of black nodes on every downward path.
  • Rules broken by an insert are repaired with recoloring and rotations on the way up to the root; that costs O(log N).
  • It gives fast lookup/insert/delete while keeping the order of keys; it is hard to implement, so ready-made ones from libraries are the norm.