From a plain BST to a worst-case guarantee

A BST built from sorted keys can degenerate into a chain of height n. A red-black tree preserves the BST property and constrains colors along paths: no path can become more than twice as long as another.

The five red-black invariants

1. 1

   Every node is either red or black.

2. 2

   The root is black.

3. 3

   Every NIL leaf—that is, every null pointer—is black.

4. 4

   A red node has black parent and children: two red nodes can never be consecutive.

5. 5

   Every path from a node to a descendant NIL contains the same number of black nodes: its black height.

Lab: watch the fix-up

Every new key enters red. Step through the trace to see which violation appears and how recoloring and rotations move or remove it.

Insert like a BST, then repair

1. Find a NIL leaf through ordinary BST search and attach the new node.
2. Color it red so every path keeps the same black height.
3. If its parent is black and the new node is not the root, every invariant already holds.
4. If its parent is red, inspect the uncle and geometry, then apply fix-up.
5. Finally, force the root to black.

Insertion: the three cases, step by step

Let z be the current node, p its parent, g its grandparent and u its uncle, the other child of g. Enter the loop only when p is red; g exists and is black. First assume p = g.left. A NIL pointer counts as a black uncle.

In the diagrams B = black, R = red; black NIL leaves are omitted. Intermediate states may temporarily violate invariants.

       20B                     20R ← z
      /   \                   /   \
    10R   30R      →        10B   30B
    /                       /
   5R ← z                  5R

      30B                   30B
      /                     /
    10R         →         20R
      \                   /
      20R ← z           10R ← z

      30B                  20B
      /                   /   \
    20R         →       10R   30R
    /
  10R ← z

Remember: case 1 can repeat O(log n) times; case 2 leads to case 3, which terminates. One insertion performs at most two rotations.

Complete insertion pseudocode

Use z.p for the parent. Sentinel NIL is black and the root’s parent is NIL. BST-INSERT attaches a new node and sets its parent; it returns NIL if the key already exists. Rotations also update parents and the root. Duplicate keys are ignored, as in the lab.

RB-INSERT(T, key)
    z ← BST-INSERT(T, key)
    if z = NIL
        return                  // duplicate key
    z.left ← NIL
    z.right ← NIL
    z.color ← RED
    RB-INSERT-FIXUP(T, z)

RB-INSERT-FIXUP(T, z)
    while z.p.color = RED
        if z.p = z.p.p.left
            u ← z.p.p.right
            if u.color = RED                 // case 1
                z.p.color ← BLACK
                u.color ← BLACK
                z.p.p.color ← RED
                z ← z.p.p
            else
                if z = z.p.right             // case 2
                    z ← z.p
                    LEFT-ROTATE(T, z)
                z.p.color ← BLACK            // case 3
                z.p.p.color ← RED
                RIGHT-ROTATE(T, z.p.p)
        else
            u ← z.p.p.left
            if u.color = RED                 // mirror 1
                z.p.color ← BLACK
                u.color ← BLACK
                z.p.p.color ← RED
                z ← z.p.p
            else
                if z = z.p.left              // mirror 2
                    z ← z.p
                    RIGHT-ROTATE(T, z)
                z.p.color ← BLACK            // mirror 3
                z.p.p.color ← RED
                LEFT-ROTATE(T, z.p.p)
    T.root.color ← BLACK

Why height stays logarithmic

Define bh(x) as the number of black nodes from x to a descendant NIL, excluding x and including NIL; bh(NIL) = 0. By induction, a subtree rooted at x contains at least 2^bh(x) − 1 internal nodes: each child has black height at least bh(x) − 1.

Let h be the number of edges on the longest root-to-NIL path, equivalently the number of internal nodes on that path. With no consecutive reds, at least half the nodes after the root are black: bh(root) ≥ h/2. Hence n ≥ 2^h/2 − 1 and:

The bound uses an inequality: bh(root) is not always equal to h/2. The lab’s black counter includes the root: for a nonempty valid tree, it displays bh(root) + 1.

Deletion: first the BST, then the black deficit

Distinguish z, whose key we want to delete, from y, the node physically detached. This distinction is essential when z has two children.

1. Zero or one non-NIL child: y = z. Attach its only child to the parent, or NIL if z has no real children.
2. Two non-NIL children: choose y = minimum(z.right), the successor. It has no left child, so detach it using the previous case. This version copies y’s key and data into z, keeping z’s color.
3. Call x the child replacing y, even if it is NIL. Save y’s original color: this, not necessarily z’s color, determines whether fix-up is needed.

Example: root 20B with children 10R and 30R. Deleting key 20 copies 30 into the root and detaches red node 30: no black is lost, even though the requested key was in a black node.

When does “double black” appear?

• y was red: no path loses a black node; no repair is needed.
• y was black and x is red: make x black and finish. In a valid RB tree, a node with one real child is black and that child is red.
• y was black and x is black or NIL: paths through x are short one black. Attribute an extra black to x, called “double black”, and resolve it with the fix-up loop.

Double black is a bookkeeping device, not a third stored color. If x is the root, discard the extra black: all paths lost the same contribution. If x is red, absorb the extra black by making it black.

RB-DELETE(T, z)
    if z.left = NIL or z.right = NIL
        y ← z
    else
        y ← TREE-MINIMUM(z.right)

    removedColor ← y.color
    if y.left ≠ NIL
        x ← y.left
    else
        x ← y.right

    x.p ← y.p                   // also when x = NIL
    if y.p = NIL
        T.root ← x
    else if y = y.p.left
        y.p.left ← x
    else
        y.p.right ← x

    if y ≠ z
        z.key ← y.key
        z.data ← y.data         // keep z.color unchanged
    if removedColor = BLACK
        RB-DELETE-FIXUP(T, x)
    return y                    // detached node

The four fix-up cases

Assume x is a left child. Let p be its parent and w = p.right its sibling. The near nephew is w.left and the far nephew is w.right. The notes label these A (x), B (p), D (w), C (near), E (far). NIL children are black.

          p
         / \
   x (+B)   w
           / \
        near far

If x is a right child: swap left and right throughout. The sibling is p.left, the near nephew w.right and the far nephew w.left; left rotations become right rotations and vice versa. Overall: at most three rotations (cases 1, 3 and 4), plus any upward steps in case 2.

Worked example: delete 10, cases 3 → 4

       20B             20B             20B              30B
      /   \           /   \           /   \            /   \
    10B   40B   →  NIL+B  40B   →  NIL+B  30B   →    20B   40B
          /               /                 \
        30R             30R                 40R
      DELETE 10               CASE 3              CASE 4

After detaching 10B, x is 20’s left NIL: w = 40B, near = 30R, far = NIL. Case 3 rotates at 40 and makes 30 the new sibling; case 4 rotates at 20, producing root 30B with children 20B and 40B. Every path again has the same black count.

RB-DELETE-FIXUP(T, x)
    while x ≠ T.root and x.color = BLACK
        if x = x.p.left
            w ← x.p.right
            if w.color = RED                 // case 1
                w.color ← BLACK
                x.p.color ← RED
                LEFT-ROTATE(T, x.p)
                w ← x.p.right

            if w.left.color = BLACK and w.right.color = BLACK
                w.color ← RED                // case 2
                x ← x.p
            else
                if w.right.color = BLACK     // case 3
                    w.left.color ← BLACK
                    w.color ← RED
                    RIGHT-ROTATE(T, w)
                    w ← x.p.right
                w.color ← x.p.color          // case 4
                x.p.color ← BLACK
                w.right.color ← BLACK
                LEFT-ROTATE(T, x.p)
                x ← T.root
        else
            w ← x.p.left
            if w.color = RED                 // mirror 1
                w.color ← BLACK
                x.p.color ← RED
                RIGHT-ROTATE(T, x.p)
                w ← x.p.left

            if w.right.color = BLACK and w.left.color = BLACK
                w.color ← RED                // mirror 2
                x ← x.p
            else
                if w.left.color = BLACK      // mirror 3
                    w.right.color ← BLACK
                    w.color ← RED
                    LEFT-ROTATE(T, w)
                    w ← x.p.left
                w.color ← x.p.color          // mirror 4
                x.p.color ← BLACK
                w.left.color ← BLACK
                RIGHT-ROTATE(T, x.p)
                x ← T.root
    x.color ← BLACK

The lab above visualizes insertion; the diagrams and pseudocode in this section describe deletion.

Build an RB tree from an unsorted array

Start with an empty tree and insert keys in array order, running fix-up after every insertion. The array does not need to be sorted first. The tree remains red-black after every prefix of the sequence, so the next insertion already benefits from logarithmic height.

RB-BUILD(A)
    T ← EMPTY-RB-TREE()          // root = NIL, NIL.color = BLACK
    for key in A
        RB-INSERT(T, key)       // includes fix-up after each insertion
    return T

An empty array produces root NIL. For duplicates, use set semantics: an existing key does not create another node. A multiset can store an occurrence counter in each node.

Example: A = [41, 38, 31, 12, 19, 8]

          38B
         /   \
       19R   41B
      /   \
    12B   31B
    /
   8R

Check: in-order is [8, 12, 19, 31, 38, 41]; no red node has a red child. Every root-to-NIL path contains three black nodes including the root and NIL, so bh(root) = 2 under the convention excluding the root. Changing insertion order may produce a different, still valid shape.

Cost and lower bound

For n distinct keys, insertion i costs O(log(i + 1)). Summing gives O(n log n) time and Θ(n) space for the tree. The upper bound is optimal in the worst case for arbitrary keys in the comparison model.

Lower-bound proof: if we could build a BST containing n arbitrary distinct keys in o(n log n), an in-order traversal in Θ(n) would return them sorted. That would beat the Ω(n log n) lower bound for comparison sorting, a contradiction. Construction therefore takes Θ(n log n) in the worst case.

If the array is already sorted: direct Θ(n) constructions exist using medians and a consistent level coloring. Making every node black works only if all paths to NIL have the same length; a generic balanced BST is insufficient. Starting from unsorted input, comparison sorting still costs Θ(n log n) in the worst case.

Exercises with solutions

Common mistakes

• Ignoring NIL pointers in the analysis: they are black leaves and count toward black height.
• Assuming red-black means perfectly balanced: the guarantee is h ≤ 2 log₂(n+1), not complete levels.
• Forgetting the mirror cases when the parent is the grandparent’s right child.
• Rotating without updating root and parents, or recoloring before correctly identifying uncle and grandparent.
• Counting every node instead of only black nodes when checking black height.