Red-Black Tree

A plain binary search tree gives you O(log n) search, insert and delete — but only on average, over random input. Insert a sorted sequence into one and it degrades into a linked list: every operation becomes O(n). A red-black tree is a BST with an extra rule that makes that worst case impossible, at the cost of a small amount of bookkeeping on every insert and delete.

The four invariants

Every node is coloured red or black, and the tree maintains four rules:

1. Every node is red or black.
2. The root is black.
3. Every red node has two black children (equivalently: no red node has a red parent — no two reds in a row on any path).
4. Every path from a node down to a null leaf passes through the same number of black nodes ("black-height").

Rule 4 is the one doing the real work. It doesn't say the tree is balanced by height — it says every root-to-leaf path has the same black count. Combined with rule 3 (no two reds in a row), that bounds how much a path can be stretched by red nodes: the longest possible path is at most twice the shortest, because the shortest path is all black and the longest alternates red and black. That ratio is the whole guarantee — height stays O(log n) regardless of insertion order, which is the property a plain BST doesn't have.

A concrete (and valid — every path below has exactly two black nodes under the root, satisfying rule 4) small example:

(NIL leaves — the implicit black children of 3, 7, 12 and 18 — are left off the drawing; every textbook does the same, since including them adds nothing but clutter.)

Why not just rebalance by height directly?

That's what an AVL tree does — track height, rebalance whenever a subtree drifts by more than one. AVL trees have a tighter balance guarantee than red-black trees, which means faster lookups. The trade-off shows up specifically on deletion: fixing one AVL subtree's balance can itself reduce that subtree's height by one, which can unbalance the next ancestor up — so an AVL delete can require a rotation at every level from the deleted node to the root, O(log n) in the worst case. Insertion doesn't have this problem for either structure — both AVL and red-black trees need only a small constant number of rotations to restore balance after an insert. A red-black tree's fix-up stays bounded by a small constant either way — at most two rotations for insert, three for delete — even though it may recolour several nodes on the way up. That asymmetry is why red-black trees are the more common default for something written and read roughly evenly — Java's TreeMap, and (though the C++ standard mandates only the ordering guarantee, not the implementation) every major std::map/std::set in practice, the Linux kernel's process scheduler — while AVL shows up more where lookups dominate and deletes are rare.

Insert: colour it red, then fix up

A new node is always inserted as a leaf, coloured red. That choice is deliberate: adding a red leaf can only ever violate rule 3 (a red node with a red parent) — it never touches the black-height that rule 4 depends on, since a red node contributes nothing to it. So the fix-up only has one kind of problem to solve: a red node sitting under a red parent.

There are three cases, checked in this order, walking up from the inserted node:

Uncle is red. Recolour the parent and uncle black and the grandparent red, then treat the grandparent as the newly-inserted node and repeat. This is the case that can cascade all the way to the root — but it's pure recolouring, no rotation, so each step is O(1) and there are at most O(log n) of them.

Uncle is black, "triangle" shape (new node is a right child of a left child, or vice versa). One rotation at the parent turns it into a "line" shape, then falls through to the next case.

Uncle is black, "line" shape (new node and parent are both left children, or both right children). One rotation at the grandparent plus a recolour, and the tree is balanced — this terminates the fix-up; it never needs to continue further up.

Deletion's fix-up is the same family of idea — cases on the colour and shape of a node's sibling — but has more of them, because removing a black node can violate rule 4 in ways an insert never can. It's usually taught, and asked about, only at the level of "it's O(log n) and bounded rotations, same as insert" rather than reproduced case by case.

What it's actually used for

You will not be asked to implement red-black insertion by hand in most interviews — it's the kind of thing you use, not the kind of thing you write live. What you're expected to know:

• Java's TreeMap/TreeSet are red-black trees by specification; C++'s std::map/std::set are red-black trees in every major implementation (the standard itself only mandates the ordering guarantee, not how it's achieved). If a problem wants sorted order maintained under insert/delete with O(log n) guarantees per operation — not just "sorted once" — these are what you reach for, and knowing why they're safe to use in a loop instead of a hash map is knowing this article's first section.
• "Why not always use a hash map?" — because a hash map has no order. The moment a problem needs "the next element greater than x" or "the k smallest remaining," you need an ordered structure, and a red-black tree is what gives you that in O(log n) rather than the O(n) a sorted array's insert costs.
• The worst-case argument itself. "What breaks if you use a plain BST here?" is a real follow-up, and "sorted or adversarial input degrades it to a linked list, O(n) per operation" is the answer that shows you understand why the structure exists rather than just its name.

Practice it

There's no problem in the catalogue that asks you to implement a red-black tree from scratch — real interviews rarely do either. What does show up: harder tree and ordered-map problems where recognising "this needs a balanced BST, and my language's standard library already gives me one" is the actual skill being tested.

Tree problemsBinary search tree problems