Step 1 -- The everyday picture. A plain binary search tree files each key by going left when it is smaller and right when it is bigger -- wonderfully fast, until the keys happen to arrive already in order. Then every key turns the same way and the tree stretches into one long, lopsided chain, as slow to search as an ordinary list. A red-black tree is the same search tree with a self-tidying habit, but instead of measuring heights it simply paints every node either red or black and obeys a few colouring rules. Those rules quietly guarantee that the longest path down the tree is never more than twice the shortest, so it can never grow badly out of shape.
Step 2 -- Name the rules, then the one that matters. Every node is red or black; the root is black; the leaves (the empty NIL slots) count as black; a red node may never sit directly above another red node; and -- the crucial one -- every path from a given node down to a leaf passes through the same number of black nodes. That number is the node's black-height $bh$. Put the last two rules together: because reds cannot stack, an all-black path is the shortest a route can be, and a strictly alternating red-black path is the longest. So if every route from the root passes, say, $3$ black nodes, the shortest path is $3$ steps and the longest is at most $6$ -- never worse than double.
Step 3 -- The precise version and the payoff. That doubling argument gives the height bound $h \le 2\log_2(n+1)$ for $n$ keys. Inserting a key colours it red first (cheap, and usually already legal); the only thing to repair is a red-above-red clash. If the new node's "uncle" is also red the fix is pure recolouring; otherwise it takes at most two rotations. Deletion is the hardest case but still needs at most three rotations. Every operation therefore stays $O(\log n)$ no matter what order the keys arrive in -- versus $O(n)$ for an unbalanced tree. In the controls above, the $n$ slider sets how many keys are used and the preset chooses their order; "Sorted" and "Reverse" are exactly the orders that wreck a naive tree.
Step 4 -- Try this in the sim above. Set the preset to "Sorted" and drag $n$ to its maximum: that ordering would build a degenerate height-$(n-1)$ chain in a naive BST -- the very disaster the colouring rules prevent (Section 3 derives the $2\log_2(n+1)$ ceiling). Switch between "Random" and "Sorted" and watch the Comparisons counter respond. Then walk through with the Next and Prev buttons to follow the RB-INSERT and FIXUP lines step by step, including the branch between simply recolouring and performing a rotation.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity function
h
Height or depth of structure
k
Key or rank parameter
W(n)
Worst-case complexity
A(n)
Average-case complexity
Step 1 -- Five Properties. 1. Nodes colored red or black. 2. Root is black. 3. All NIL leaves are black. 4. Red node has two black children (no two consecutive reds). 5. All simple paths from node to descendant NIL have same number of black nodes (black-height bh).
Step 2 -- Height Bound. A red-black tree with n internal nodes has height h <= 2 log2(n+1). Proof: by property 5, any path has >= bh black nodes. By property 4, path length <= 2*bh. Minimum n for bh: n >= 2^bh - 1. So bh <= log2(n+1) => h <= 2 log2(n+1).
Step 3 -- Insert O(log n). BST insert, color new node red. Fix violations: if parent is also red (violates property 4). Cases: (a) Uncle is red -- recolor, recurse up. (b) Uncle is black -- 1-2 rotations + recolor. At most 2 rotations total per insert.
Step 4 -- Delete O(log n). Most complex tree operation. BST delete, then fix 'double-black' violations. Four cases based on sibling color and sibling's children colors. At most 3 rotations total per delete.
Step 5 -- vs AVL. AVL: height <= 1.44 log2 n (better). RB: height <= 2 log2 n (worse). But: AVL keeps a stricter balance, so updates rebalance more often -- an AVL delete can cascade O(log n) rotations up the tree -- while RB insert does at most 2 rotations and RB delete at most 3. RB better for write-heavy workloads. AVL better for read-heavy.
Step 6 -- Real-world usage. C++ std::map, std::set: red-black tree. Java TreeMap: red-black tree. Linux kernel CFS scheduler: red-black tree for runqueue. Nginx event timer: red-black tree. Virtually all production ordered map implementations use red-black trees.
Section 4 -- FAQ
What is black-height? concept+
Black-height bh(v) = number of black nodes on any path from v (not inclusive) to a leaf. Property 5 says all such paths have the same count. This guarantees balance without perfectly equal heights.
Why can we always fix violations with at most 2 rotations on insert? complex+
Insert adds one red node. Violation occurs only if parent is red (double red). Three cases: uncle red (recolor, no rotation, propagate up), uncle black+straight (1 rotation), uncle black+bent (2 rotations). The bent case terminates after 2 rotations -- no further propagation.
Why does C++ std::map use red-black trees? applied+
Red-black trees guarantee O(log n) worst case for all operations with low rotation constants. They are also relatively simple to implement correctly. AVL trees have better height but more complex rebalancing. The trade-off favors red-black for general-purpose ordered containers.
What happens during deletion? nonobv+
Deleting a black node creates a 'double-black' deficit on that path -- black-height is violated. Fix by borrowing blackness from a sibling or parent, propagating up if necessary. Four cases based on sibling's color and children. At most 3 rotations per delete.
How are red-black trees related to 2-3-4 trees? deep+
A red-black tree is an isometry of a 2-3-4 tree. Red edges represent merged keys inside a 4-node. Every 2-3-4 tree operation maps to a red-black operation and vice versa. This equivalence provides intuition for why the 5 properties work.
Can a red-black tree have two consecutive red nodes? concept+
No -- property 4 forbids it. New nodes are colored red on insert. If the parent is also red, this is a violation that must be fixed via recoloring and/or rotations.
Section 5 -- Common Misconceptions
Conceptual Misconceptions
X Red-black tree is always height log2 n.
O Height can be up to 2 log2(n+1) -- alternating red-black path is twice as long as all-black path.
X Invariants can be checked by color alone.
O Black-height (property 5) requires counting black nodes on a path -- not just checking colors locally.
X Insert always requires rotations.
O Uncle-is-red case only needs recoloring (no rotation). Rotations only happen in uncle-is-black cases.
Implementation Errors
X Implementing delete by ignoring the double-black fix.
O Delete without fixup produces an invalid red-black tree with violated black-height, leading to incorrect search and undefined behavior.
X Setting NIL leaves to null instead of a sentinel node.
O NIL leaves must be BLACK (property 3). Using null requires null-checks everywhere. Use a sentinel NIL node: black, with parent/children pointing to itself.
X Recoloring parent without checking grandparent's uncle.
O Recoloring must check uncle's color. Recoloring parent and uncle to black may require recoloring grandparent to red and propagating up to fix new violations.