Red-black trees: balanced search by recoloring

Table of Contents

Data structures: the self-balancing search tree

A binary search tree stays fast only while it stays bushy, and the red-black tree is the balancing scheme that won: it sits inside C++ std::map, Java TreeMap, the Linux kernel’s rbtree, and countless schedulers and indexes. Instead of the AVL tree’s strict height arithmetic, it gives every node one extra bit — a colour, red or black — and enforces five colouring rules. Those rules are looser than AVL’s, so updates do less restructuring, yet they still cap the longest root-to-leaf path at twice the shortest, and that single fact forces the height to stay logarithmic. This page builds the whole mechanism: the five invariants, the two repair moves (rotation and recolouring), every insert and delete fix-up case, and the proof at the end.

The one-sentence idea. Colour every node red or black so that no path from a node down to a leaf ever contains more black nodes than any other path from that node — then no path can be more than twice as long as another, and the tree can never degenerate into a chain.

1 — The five invariants

A red-black tree is a binary search tree in which every node carries a colour, and the colours obey five rules. Four of them are about red; the fifth is the one that does the real work. To make the rules airtight, every missing child is drawn as a special leaf called a NIL node: it holds no key, counts as black, and terminates every path. Counting NILs is what lets rule 5 compare paths of different shapes fairly.

Rule 1: Every node is colouredEach node is exactly one of red or black. The colour is one bit of storage per node.
Rule 2: The root is blackNo exceptions, even for a one-node tree. Fix-up routines may temporarily redden the root; they always blacken it again before finishing.
Rule 3: Every NIL leaf is blackAll NIL nodes share one colour by definition: black. They are the leaves every path ends at.
Rule 4: Red nodes have black childrenA red node’s children — real or NIL — are both black. Equivalently: no red node ever has a red parent, so reds are always separated by at least one black. This is the rule insertions most often break, and the one every insert fix-up case is about.
Rule 5: Equal black counts on every pathFor every node, all simple paths from that node down to NIL leaves contain the same number of black nodes. The shared count is called the node’s black-height:
Black-heightbh(x)=black nodes on a path fromxdown to a NIL leaf, counting the NIL,but not countingxitselfbh(NIL)=0bh(leaf)=1(a leaf’s one comes from the NIL below it)

The tree below satisfies all five rules — it is the tree you get by inserting 20, 10, 30, 5, 15, 25, 35 in that order. Click any node to see its colour, its black-height worked out along an actual path, and the live verdict on each rule. Then try the sabotage switch: painting node 10 red breaks two rules at once, and the checklist shows exactly which.

Figure 1: A valid red-black tree, click a node to inspect it

red node black node NIL leaf (always black)label under a node: its black-height
    Figure 1. Black-height of the root is 2: every root-to-NIL path passes exactly two black nodes below the root: one of {10, 30} and the NIL itself. The red leaves contribute height but no black-height, which is precisely the slack the rules allow: paths can differ in length, but never in black count.

    How to read this

    • Rule 5 is the guarantee; rules 2–4 protect it. Equal black counts alone would still permit a chain of red nodes stretching one path. Rule 4 caps how many reds can pad a path: at most one red between consecutive blacks.
    • New nodes are born red. A red leaf cannot break rule 5 (it adds no black), so an insert can only ever break rule 4, or rule 2, if it becomes the root. Fix-up is correspondingly narrow.
    • NILs are usually one shared sentinel. Real implementations allocate a single black NIL object and point every empty child at it, so rule 3 costs no memory per leaf.

    2 — The only two moves: rotation and recolouring

    Every fix-up in this page is assembled from exactly two moves. A rotation is the same constant-time pointer rearrangement as in a plain BST: a node and its child swap levels, the child’s inner subtree (labelled β below) is handed across, and the inorder sequence — hence the BST property — is preserved exactly. A rotation changes no colours by itself. A recolouring is the opposite extreme: it changes no pointers at all, only colour bits, so it cannot disturb the BST property or the tree’s shape — it can only move black-height between paths, which is exactly what several fix-up cases need.

    Step through a left rotation below. The pivot is 10, its right child 20 rises, and β (the inner subtree, everything between 10 and 20 in key order) is handed down to become 10’s right subtree. The right rotation is the mirror image; the buttons switch between them.

    Figure 2: Left rotation at 10

    pivot: the node that rotates down child that rotates uptriangles α, β, γ are whole subtrees, carried along unchanged

    Figure 2. Three pointers change: the rising child takes the pivot’s place, the pivot becomes its inner child, and β changes parent. Colours travel with their nodes — note that 20 stays red and 10 stays black throughout; when a fix-up wants new colours, it recolours as a separate, explicit step.
    Rotationpointer changes=3colours changed=0inorder sequenceunchanged, so the BST property is preserved
    Recolouringpointer changes=0shape and inorder sequenceunchangedblack-heightredistributed between the recoloured nodes’ paths
    Why β can always be handed acrossEvery key in β lies between the pivot’s key and the rising child’s key — that is what “inner subtree” means. So β qualifies as the pivot’s new inner subtree under the BST ordering, on either side. This one handover is the entire content of every rotation in this page.

    Recolouring is the cheap move, rotation the decisive one. Insert fix-up tries recolouring first (Case 1) and rotates only when recolouring cannot help. Delete fix-up is the reverse temperament: it recolours the sibling when it can (Case 2) and rotates when a red nephew gives it something to work with. Watch for that pattern in the next two steps.

    3 — Insert fix-up: three cases, told by the uncle

    Insertion is an ordinary BST insert with the new node coloured red. As Step 1 noted, a red leaf adds no black to any path, so rule 5 survives automatically; the only possible damage is a red-red edge — the new node’s parent is also red, breaking rule 4, or a red root, breaking rule 2. Fix-up walks upward from the new node repairing red-red edges, and which case applies at each level is decided by one node: the uncle, the grandparent’s other child.

    Case 1: Uncle is redRecolour only: parent and uncle go black, grandparent goes red. The red-red edge is gone at this level, but the grandparent is now red, so the problem may reappear two levels up. Repeat from the grandparent. No rotation, and the subtree’s black-height is unchanged — the two new blacks below exactly balance the grandparent’s lost black on every path through it.
    Case 2: Uncle is black, new node is an inner grandchildThe new node sits on the inside — a right child of a left child, or the mirror. Rotate the parent away from the grandparent: the new node rises into the parent’s place and the shape becomes the straight line of Case 3. Nothing is fixed yet; this case only converts.
    Case 3: Uncle is black, new node is an outer grandchildThe growth is a straight line. Rotate the grandparent toward the short side, then recolour: the risen parent goes black, the grandparent goes red. The red-red edge is gone, black-height is preserved, and fix-up ends — this case always terminates the loop.

    Pick a case and step through it. Each walkthrough starts from a valid tree, inserts one red node, and repairs what breaks. A NIL uncle counts as black, which is why Case 3 below needs no visible uncle at all.

    Figure 3: Insert Case 1: red uncle, recolour and climb

    the new node / current node of the fix-up red node black node

    Figure 3. Case 1 is the only insert case that can repeat: each recolouring climbs two levels, so it runs at most half the height many times. Cases 2 and 3 together cost at most two rotations per insert, ever — one to straighten, one to settle.
    // insertFixup(z): z is the red node that may have a red parent
    while parent(z) is red:
        g = grandparent(z);  u = uncle(z)
        if u is red:                          // Case 1: recolour and climb
            colour(parent(z)) = colour(u) = black
            colour(g) = red;  z = g
        else:                                 // uncle black (NIL counts)
            if z is an inner grandchild:     // Case 2: straighten
                z = parent(z);  rotate away from g at z
            colour(parent(z)) = black         // Case 3: rotate and settle
            colour(g) = red;  rotate toward u at g
            break
    colour(root) = black                      // restore rule 2

    The demonstration sequence in the playground (Step 5), inserting 41, 38, 31, 12, 19, 8, exercises all three cases in six inserts, including a Case 2 that converts into a Case 3 on the very same key.

    4 — Delete fix-up: the doubly-black node and four cases

    Deletion is where red-black trees earn their reputation for subtlety. Removing a red node is free: it sits on no path’s black count and has black children, so splicing it out breaks nothing. Removing a black node is different — every path through it loses one black, and rule 5 breaks. The standard bookkeeping trick is to pretend the node that slides into the deleted node’s place inherits the lost black as an extra black: it becomes doubly black. A doubly-black node is drawn below as a black square marked DB. If it is a real red node it becomes “red-and-black” and simply ends black; the interesting situation is a doubly-black NIL, which is what all four cases below start from. Fix-up’s whole job is to shed that extra black — by pushing it up, or by borrowing black-height from the sibling’s subtree through a rotation.

    Which case applies is decided by the sibling of the doubly-black node and the colours of the sibling’s children (its nephews). The four cases, for a doubly-black node on the left (mirror everything if it is on the right):

    Case 1: Sibling is redRecolour the sibling black and the parent red, then rotate the parent toward the doubly-black side. The doubly-black node gains a new sibling — the old sibling’s inner child — which is guaranteed black. This case only converts into Case 2, 3, or 4; it never finishes the job itself.
    Case 2: Sibling is black, both nephews blackRecolour the sibling red. Its subtree loses one black on every path, which exactly compensates: the extra black can move up to the parent. If the parent was red it just ends black and fix-up stops; if the parent was black it becomes the new doubly-black node and the loop repeats one level up. This is the delete analogue of insert Case 1: recolour and climb.
    Case 3: Sibling is black, near nephew red, far nephew blackRecolour the near nephew black and the sibling red, then rotate the sibling away from the doubly-black node. The near nephew rises into the sibling’s place — and it is now positioned as a red far nephew. This case only converts into Case 4.
    Case 4: Sibling is black, far nephew redThe decisive case. The sibling takes the parent’s colour, the parent goes black, the far nephew goes black, and the parent rotates toward the doubly-black side. The rotation moves one black across to the short side, the extra black is absorbed, and fix-up ends — always.

    Each walkthrough below starts at the moment a black leaf has been deleted and its NIL replacement has become doubly black, and steps through one case’s transformation. Cases 1 and 3 end by handing over to a later case, exactly as the real algorithm does.

    Figure 4: Delete Case 1: red sibling, rotate to convert

    DB: doubly-black NIL; it carries one extra black node recoloured or rotated in this step red node black node

    Figure 4. Count blacks on the paths through the doubly-black node before and after each case: the transformations are designed so that the tall side lends exactly one black to the short side, or the deficit climbs one level intact. Case 2 is the only case that can repeat, and it climbs — so the loop runs at most height-many iterations, with at most three rotations in total (one each from Cases 1, 3, and 4).
    // deleteFixup(x): x is doubly black; w is its sibling
    while x is not the root and x is black (carrying the extra black):
        w = sibling(x)
        if w is red:                                // Case 1: convert
            colour(w) = black; colour(parent(x)) = red
            rotate toward x at parent(x); w = sibling(x)
        if both children of w are black:            // Case 2: recolour, climb
            colour(w) = red; x = parent(x)
        else:
            if far child of w is black:             // Case 3: convert
                colour(near child of w) = black; colour(w) = red
                rotate away from x at w; w = sibling(x)
            colour(w) = colour(parent(x))           // Case 4: settle
            colour(parent(x)) = colour(far child of w) = black
            rotate toward x at parent(x); x = root
    colour(x) = black                               // absorb any leftover extra black

    Why delete is harder than insert

    • The deficit can climb the whole tree. Insert’s red-red edge is a local surplus that recolouring pushes up two levels at a time; delete’s missing black is a deficit that Case 2 pushes up one level at a time, potentially to the root — where it harmlessly evaporates, because the root’s extra black can simply be dropped.
    • Two children means a successor swap first. Deleting a node with two children copies its inorder successor’s key into it and deletes the successor instead — and the successor, having no left child, is always one of the easy shapes. The colour that matters for fix-up is the successor’s original colour.
    • Rotations are rarer than recolourings. Across a whole delete there are at most three rotations; everything else is colour flips on the climb. This is the concrete sense in which red-black updates are cheaper than AVL’s.

    5 — Playground: the real algorithm, live

    Everything so far, running. The tree below is maintained by this page’s own red-black implementation — BST insert and delete, then the exact fix-up loops from Steps 3 and 4, and it narrates every case it fires. After each operation the whole tree is re-audited against all five invariants. Try the demo sequence first: six inserts that between them trigger Case 1, a Case 2 that converts into Case 3, and another Case 1. The tree is capped at 31 nodes so every node stays readable.

    Figure 5: Playground tree, 0 nodes, black-height 0

    red node black node node touched by the last operation

    Insert a key to begin, or run the demo sequence — the six keys from the classic textbook example, exercising every insert case.

    Figure 5. Duplicate inserts and deletes of missing keys are reported, not silently ignored. Deleting a black node narrates the doubly-black fix-up case by case; deleting a red node needs no fix-up at all, and the readout says so.

    Key to insert or delete

    6 — Why the height stays logarithmic

    The proof has two halves, and both come straight from the invariants. First, rule 5 forces any tree with a given black-height to contain exponentially many nodes: a subtree whose paths all carry bh blacks cannot be a scrawny chain, it must branch enough to hold at least 2bh − 1 nodes. Second, rule 4 caps how much taller than the black-height the tree can be: reds can pad a path, but never two in a row, so at least half the nodes on any root-to-leaf path are black and the height is at most twice the black-height. Chain the two halves together and the height is at most twice a logarithm.

    Lemma: black-height forces sizeThe subtree rooted at any node x contains at least:2bh(x)−1internal (real) nodes
    Why: induction on black-height, no step skippedbase:bh(x)=0meansxis NIL, holding20−1=0nodesstep: each child ofxhas black-height at leastbh(x)−1(equal tobh(x)if the child is red,bh(x)−1if black)so each child subtree holds at least2bh(x)−1−1nodestotal≥2×(2bh(x)−1−1)+1total≥2bh(x)−2+1total≥2bh(x)−1as claimed, the final+1countsxitself
    Second half: height versus black-heightOn the longest root-to-leaf path, red nodes are never adjacent (rule 4) and the root is black (rule 2), so at least half of the path’s nodes are black. Counting the NIL at the path’s end as well gives:bh(root)≥h2where h is the height in edges, root to deepest leaf.

    Now combine the two halves for a tree of n nodes and height h, one manipulation per line:

    The bound, step by stepn≥2bh(root)−1by the lemman+1≥2bh(root)add 1 to both sidesn+1≥2h/2sincebh(root)≥h/2and powers of 2 growlog2(n+1)≥h2takelog2of both sidesh≤2×log2(n+1)multiply both sides by 2: done
    A million keys, worked in full2bh≤n+1=1000001bh≤log2(1000001)≈19.93sobh≤19(it is a whole number)h≤2×log2(1000001)≈39.86soh≤39

    The slider below drives the comparison. It steps through perfect-tree sizes: n = 2e − 1, where the perfect tree’s height is exactly e − 1 and the red-black guarantee is exactly 2e, so you can watch the guarantee stay within a factor of about two of perfect while a degenerate chain runs away exponentially. Bar lengths are drawn on a log scale; the labels are exact.

    Figure 6: With n = 1,023 keys, the height is guaranteed at most 20

    Figure 6. Three heights for the same number of keys: a degenerate BST (a chain), the red-black guarantee from the proof above, and a perfect tree. The chain’s bar would run off any honest linear scale — that is the point of the log scale.

    Choose the number of keys

    1,023keys n = 2^e − 1
    1,022chain height (worst BST)
    20red-black height guarantee
    9perfect tree height
    Keys nDegenerate BST, worst heightPerfect tree heightRed-black worst height (guaranteed at most)
    10936
    10099613
    1,000999919
    1,000,000999,9991939
    1,000,000,000999,999,9992959

    Read the last two columns together: the red-black worst case is never more than about twice the perfect height, at any size — the constant 2 is rule 4’s fingerprint, the price of letting red nodes pad paths. A billion keys still fit within 59 levels, so a search touches at most 60 nodes. That is the entire content of “the height stays logarithmic”: height is Θ(log n), with a small, proved constant.

    7 — Costs, comparisons, and where red-black trees earn their keep

    OperationCostWhy
    SearchO(log n)One root-to-leaf path; height at most 2 log2(n + 1) by Step 6.
    InsertO(log n)Descend O(log n); fix-up recolours on the climb and rotates at most twice.
    DeleteO(log n)Descend O(log n); fix-up climbs with recolourings and rotates at most three times.
    RotationO(1)Three pointer changes, independent of subtree size.
    RecolouringO(1)Colour-bit flips only; no pointers move.
    Space overheadOne bit per nodeThe colour. Often packed into a spare bit of a pointer or a flags word, so the real overhead can be zero bytes.

    Red-black versus AVL. Both guarantee logarithmic height; they strike the bargain at different points. AVL’s rule — subtree heights within one — is stricter, so AVL trees are a little shorter (worst case about 1.44 log2 n against red-black’s 2 log2 n) and pure lookups a little faster. Red-black’s looser colour rules buy cheaper updates: bounded rotations per operation (at most two for insert, three for delete), with most fix-up work done by recolouring, and no heights to maintain — one bit instead of a stored height or factor per node. The usual rule of thumb follows: read-heavy workloads favour AVL; write-heavy ones favour red-black. Practice agrees: red-black trees are the default ordered map in C++ (std::map) and Java (TreeMap), the Linux kernel’s intrusive rbtree orders everything from virtual memory areas to timers, and database and filesystem code reaches for them whenever a balanced ordered structure must survive heavy mutation.

    Where the pieces recur. The doubly-black bookkeeping is the same deficit-tracking idea as the borrow in subtraction, and the “recolour first, rotate only when forced” pattern recurs in AA trees (a red-black variant where reds lean one way), left-leaning red-black trees (the form Sedgewick popularised, used in several standard libraries), and the balancing of B-tree nodes on disk, where a “rotation” is a page split and recolouring’s role is played by separator-key changes.

    The arc, in one breath. Colour every node red or black, keep the root and the NIL leaves black, never let a red node touch another red, and insist every downward path carries the same number of blacks. Insert red and repair red-red edges by asking about the uncle — recolour if he is red, rotate if he is black. Delete black and track the missing black as a doubly-black node, repairing by asking about the sibling and its nephews. And because equal black counts force exponential size while reds at most double a path, the height is at most twice a logarithm — balance maintained not by rebuilding, but by bookkeeping.

    Red-black tree: Bayer, 1972 (as symmetric binary B-trees); the red-black colouring and terminology are due to Guibas & Sedgewick, 1978. Heights on this page count edges: a leaf has height 0. Black-height counts black nodes on a path from a node down to a NIL leaf, including the NIL but not the node itself. Every tree drawn here is produced or audited by the page’s own red-black implementation.