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.
Insert 10, 20, 30, 40, 50, 60, 70, 80 into a red-black tree. Red nodes are outlined red, black nodes are plain. Every new node arrives red, so the only rule it can break is that a red node must have black children; the fixup repairs that with recolouring and at most two rotations per insert.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.
z = 30, p = 20, g = 10, uncle null is black. Which case is it?
Answer: Black uncle, z outside: recolour p and g, rotate at g. A red uncle is always case 1; otherwise it depends on whether z bends inwards under g.
z = 40, p = 30, g = 20, uncle 10 is red. Which case is it?
Answer: Red uncle: recolour p, u, g and move z up to g. A red uncle is always case 1; otherwise it depends on whether z bends inwards under g.
z = 50, p = 40, g = 30, uncle null is black. Which case is it?
Answer: Black uncle, z outside: recolour p and g, rotate at g. A red uncle is always case 1; otherwise it depends on whether z bends inwards under g.
z = 60, p = 50, g = 40, uncle 30 is red. Which case is it?
Answer: Red uncle: recolour p, u, g and move z up to g. A red uncle is always case 1; otherwise it depends on whether z bends inwards under g.
z = 70, p = 60, g = 50, uncle null is black. Which case is it?
Answer: Black uncle, z outside: recolour p and g, rotate at g. A red uncle is always case 1; otherwise it depends on whether z bends inwards under g.
z = 80, p = 70, g = 60, uncle 50 is red. Which case is it?
Answer: Red uncle: recolour p, u, g and move z up to g. A red uncle is always case 1; otherwise it depends on whether z bends inwards under g.
z = 60, p = 40, g = 20, uncle 10 is black. Which case is it?
Answer: Black uncle, z outside: recolour p and g, rotate at g. A red uncle is always case 1; otherwise it depends on whether z bends inwards under g.
How it runs, step by step
Insert 10, 20, 30, 40, 50, 60, 70, 80 into a red-black tree. Red nodes are outlined red, black nodes are plain. Every new node arrives red, so the only rule it can break is that a red node must have black children; the fixup repairs that with recolouring and at most two rotations per insert.
Building a red-black tree from 8 values.
Insert 10 as an ordinary BST insert, coloured red. It is the root.
Inserted 10 as a red leaf.
The root 10 ended up red, so it is coloured black: rule 2. That adds one to every path's black count equally.
Root 10 set black.
Insert 20 as an ordinary BST insert, coloured red under 10, which is black: nothing is broken.
Inserted 20 as a red leaf.
Insert 30 as an ordinary BST insert, coloured red under 20, which is red: two reds in a row, so the fixup runs.
Inserted 30 as a red leaf.
z = 30 is red under a red parent p = 20. Grandparent g = 10, uncle u = null, which counts as black. Case 3, black uncle and z is the outer child: colour p black and g red, then rotate at g so p takes g's place. That ends the loop.
Case 3 at 30.
20 turns black and 10 red, then rotate left at 10: 20 takes 10's place with 10 and 30 as its red children. Black counts are unchanged on every path and no red has a red parent, so the fixup is over.
Rotated at 10; 20 is the black top.
Insert 40 as an ordinary BST insert, coloured red under 30, which is red: two reds in a row, so the fixup runs.
Inserted 40 as a red leaf.
z = 40 is red under a red parent p = 30. Grandparent g = 20, uncle u = 10. Case 1, red uncle: colour p and u black and g red. Every path through g still has the same black count, and the problem moves up to g.
Case 1 at 40.
30 and 10 are black, 20 is red. z moves up to 20, the root, which will be set black at the end.
Recoloured; z is now 20.
The root 20 ended up red, so it is coloured black: rule 2. That adds one to every path's black count equally.
Root 20 set black.
Insert 50 as an ordinary BST insert, coloured red under 40, which is red: two reds in a row, so the fixup runs.
Inserted 50 as a red leaf.
z = 50 is red under a red parent p = 40. Grandparent g = 30, uncle u = null, which counts as black. Case 3, black uncle and z is the outer child: colour p black and g red, then rotate at g so p takes g's place. That ends the loop.
Case 3 at 50.
40 turns black and 30 red, then rotate left at 30: 40 takes 30's place with 30 and 50 as its red children. Black counts are unchanged on every path and no red has a red parent, so the fixup is over.
Rotated at 30; 40 is the black top.
Insert 60 as an ordinary BST insert, coloured red under 50, which is red: two reds in a row, so the fixup runs.
Inserted 60 as a red leaf.
z = 60 is red under a red parent p = 50. Grandparent g = 40, uncle u = 30. Case 1, red uncle: colour p and u black and g red. Every path through g still has the same black count, and the problem moves up to g.
Case 1 at 60.
50 and 30 are black, 40 is red. z moves up to 40, whose parent 20 is black: done.
Recoloured; z is now 40.
Insert 70 as an ordinary BST insert, coloured red under 60, which is red: two reds in a row, so the fixup runs.
Inserted 70 as a red leaf.
z = 70 is red under a red parent p = 60. Grandparent g = 50, uncle u = null, which counts as black. Case 3, black uncle and z is the outer child: colour p black and g red, then rotate at g so p takes g's place. That ends the loop.
Case 3 at 70.
60 turns black and 50 red, then rotate left at 50: 60 takes 50's place with 50 and 70 as its red children. Black counts are unchanged on every path and no red has a red parent, so the fixup is over.
Rotated at 50; 60 is the black top.
Insert 80 as an ordinary BST insert, coloured red under 70, which is red: two reds in a row, so the fixup runs.
Inserted 80 as a red leaf.
z = 80 is red under a red parent p = 70. Grandparent g = 60, uncle u = 50. Case 1, red uncle: colour p and u black and g red. Every path through g still has the same black count, and the problem moves up to g.
Case 1 at 80.
70 and 50 are black, 60 is red. z moves up to 60, whose parent 40 is red too: another round.
Recoloured; z is now 60.
z = 60 is red under a red parent p = 40. Grandparent g = 20, uncle u = 10. Case 3, black uncle and z is the outer child: colour p black and g red, then rotate at g so p takes g's place. That ends the loop.
Case 3 at 60.
40 turns black and 20 red, then rotate left at 20: 40 takes 20's place with 20 and 60 as its red children. Black counts are unchanged on every path and no red has a red parent, so the fixup is over.
Rotated at 20; 40 is the black top.
8 nodes, height 4, after 4 rotations and 19 recolourings. The rules keep the longest root-to-leaf path at most twice the shortest, so the height is at most 2 log2(n + 1), about 6 here, and every operation stays O(log n).
Red-black tree with 8 nodes and height 4.
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