Red-Black Tree
An AVL tree tracks heights exactly and rotates often. A red-black tree tracks something looser, one bit of colour per node, and gets a guarantee that is almost as good: no root-to-leaf path is more than twice as long as any other, so the height stays within 2 log n. Every new node is red, which cannot disturb the count of black nodes on any path. The only thing it can break is a red node under a red parent, and the fixup handles that with a look at the uncle: a red uncle means push the blackness up a level and keep going; a black uncle means one or two rotations and the tree is legal again. The rules lesson walks a tree bottom-up computing black heights, which is exactly how you would verify one by hand. Deletion is the harder half: removing a black node leaves every path through its place one black short, and the fixup pushes that missing black upward, recolouring a sibling here and rotating there, through four cases, until a red node absorbs it or a rotation moves a black across. At most three rotations, and the successor of a two-child node inherits the colour of the node it replaces.
Check this tree against the red-black rules. Rule 2: the root is black. Rule 4: a red node has only black children. Rule 5: from any node, every path down to a null leaf passes the same number of black nodes. Rules 1 and 3 hold by construction: every node has a colour and null leaves count as black.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.
Rule 2 says the root is black. Does 50 pass?
Answer: Yes, it is black. The root is recoloured black at the end of every insert.
20 is red with black heights 1 and 1 below. What does it report?
Answer: Fine, black height 1. Equal sides and no red-red pair means the node's black height is the side count plus one if it is black.
40 is red with black heights 1 and 1 below. What does it report?
Answer: Fine, black height 1. Equal sides and no red-red pair means the node's black height is the side count plus one if it is black.
30 is black with black heights 1 and 1 below. What does it report?
Answer: Fine, black height 2. Equal sides and no red-red pair means the node's black height is the side count plus one if it is black.
60 is red with black heights 1 and 1 below. What does it report?
Answer: Fine, black height 1. Equal sides and no red-red pair means the node's black height is the side count plus one if it is black.
80 is red with black heights 1 and 1 below. What does it report?
Answer: Fine, black height 1. Equal sides and no red-red pair means the node's black height is the side count plus one if it is black.
70 is black with black heights 1 and 1 below. What does it report?
Answer: Fine, black height 2. Equal sides and no red-red pair means the node's black height is the side count plus one if it is black.
50 is black with black heights 2 and 2 below. What does it report?
Answer: Fine, black height 3. Equal sides and no red-red pair means the node's black height is the side count plus one if it is black.
How it runs, step by step
Check this tree against the red-black rules. Rule 2: the root is black. Rule 4: a red node has only black children. Rule 5: from any node, every path down to a null leaf passes the same number of black nodes. Rules 1 and 3 hold by construction: every node has a colour and null leaves count as black.
Checking the red-black rules.
Rule 2: the root 50 is black.
Root 50 is black.
At 20 (red): black height 1 on the left, 1 on the right. Equal, and its children are black: black height 1 here.
20: black heights 1 and 1.
At 40 (red): black height 1 on the left, 1 on the right. Equal, and its children are black: black height 1 here.
40: black heights 1 and 1.
At 30 (black): black height 1 on the left, 1 on the right. Equal, and it is black, so it adds one: black height 2 here.
30: black heights 1 and 1.
At 60 (red): black height 1 on the left, 1 on the right. Equal, and its children are black: black height 1 here.
60: black heights 1 and 1.
At 80 (red): black height 1 on the left, 1 on the right. Equal, and its children are black: black height 1 here.
80: black heights 1 and 1.
At 70 (black): black height 1 on the left, 1 on the right. Equal, and it is black, so it adds one: black height 2 here.
70: black heights 1 and 1.
At 50 (black): black height 2 on the left, 2 on the right. Equal, and it is black, so it adds one: black height 3 here.
50: black heights 2 and 2.
All rules hold: black height 3 at the root. With 3 black nodes on every path and no two reds in a row, no path is longer than 6 nodes, which is what bounds the height to 2 log2(n + 1).
Valid red-black tree.
Remember
- New nodes are red; the root is black; a red node never has a red child; every path from a node to its null leaves has the same black count.
- Fixup: red uncle means recolour p, u, g and move up; black uncle means rotate (twice if z is an inner child) and recolour, then stop.
- Black height h gives a shortest path of h and a longest of at most 2h, so the height is at most 2 log2(n + 1).
Where this is used
Operating systemsLinux kernel rbtree
The kernel ships one generic implementation in lib/rbtree.c and reuses it wherever an ordered set changes constantly: the scheduler's runqueue ordered by virtual runtime, the high-resolution timer queue, and the deadline scheduler's pending work. Those sets are inserted into and removed from on almost every interrupt, so the cheap rebalancing matters far more than the last fraction of height. The kernel also offers rb_root_cached, a tree that keeps a pointer to its leftmost node, so a timer queue answers 'what expires first' with a pointer fetch instead of a walk down the left spine.
Language runtimesJava's TreeMap and treeified HashMap bins
java.util.TreeMap and TreeSet are red-black trees, which is what buys them sorted iteration and a logarithmic worst case that HashMap cannot offer. Since Java 8, HashMap itself converts a bucket into a red-black tree once that bucket holds more than eight entries and the table has grown to at least 64 buckets, so keys that all collide degrade to O(log n) rather than to a linear scan. That change was a direct answer to hash-collision denial of service: an attacker who can choose keys can no longer turn one bucket into a list to walk.
Standard librariesstd::map and std::set
The C++ standard demands ordered iteration, logarithmic worst-case lookup, and something a hash table cannot give: a pointer or iterator to an element stays valid when other elements are inserted or erased. A node-based balanced tree satisfies all three, because rebalancing only rewires pointers and never moves an element's storage, and every major implementation uses a red-black tree for it. This is also why std::map is slower than std::unordered_map on raw lookup and still the right choice when you need range queries or stable references.
Web infrastructurenginx timers and cache index
nginx holds every pending timeout in a red-black tree keyed by expiry, and the shared-memory cache index in another. Each pass of the event loop reads the leftmost node to decide how long epoll_wait may block, then expires everything that has come due. Every connection adds and removes timers as it progresses, so the structure has to absorb a constant churn of inserts and deletes while still answering 'what expires first' in logarithmic time.
Why it works this way
Why a new node is red and never black
Adding a black node breaks rule 5 immediately and everywhere: every root-to-leaf path that runs through it now carries one more black than the paths that miss it. There is no local repair for that, because compensating means adding a black to every path in the tree that avoids the new node. Red costs nothing on any path, so the damage is confined to the single edge you are already standing on, between the new node and its parent. The design is that trade: give up an invariant that is expensive to restore for one that is cheap.
Why flipping three colours leaves every black count unchanged
In the red-uncle case the parent and the uncle are both red, which forces the grandparent to be black. Any path descending through the grandparent must enter either the parent or the uncle, so painting both of them black adds exactly one black to that path, and painting the grandparent red takes exactly one away. Paths that never reach the grandparent are untouched, so rule 5 survives without a rotation, and the only thing left to check is whether the now-red grandparent has landed under a red parent of its own.
Red-black or AVL, and why systems code picks this one
AVL holds its height under roughly 1.44 log2 n against red-black's 2 log2 n, so an AVL lookup touches fewer nodes and wins on a table that is mostly read. The gap is on the write side: an AVL deletion can rotate at every level on the way back to the root, while a red-black deletion rotates at most three times and does the rest of its work by recolouring, which touches no pointers and invalidates no cached positions. Kernels and standard libraries mutate these trees on nearly every operation, so they take the shorter rebalance over the shorter path.
Deletion turns on a node you did not ask to remove
When z has two children, nothing deletes z: the successor y is lifted into its place, so the node that actually leaves the structure is y's old position, and the fixup has to be driven by the colour y had before the move. Reading z's colour instead is the classic bug, because the result still looks like a sensible tree and only a black-height check catches it. One more trap: x, the child that slides into the vacated place, is very often null, and the fixup still needs x's parent and sibling, which is why CLRS gives every leaf a single shared black sentinel rather than a null pointer.
Read more
- Red-black treeWikipedia
- Red-black trees in the kernelLinux kernel · kernel.org
- TreeMapJava SE 21 · docs.oracle.com
- Left-leaning red-black treesSedgewick
- Red-black tree visualisedUSF