Chapter 13: Red-Black Trees

Red-black trees are one of many balanced binary search tree schemes that guarantee basic dynamic-set operations take O(lg n) time in the worst case. Standard BST operations (SEARCH, INSERT, DELETE, etc.) run in O(h) time, but h can be as bad as O(n). Red-black trees ensure h = O(lg n).

---

13.1 Properties of Red-Black Trees

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK. By constraining node colors on any simple path from root to leaf, red-black trees ensure that no such path is more than twice as long as any other.

Each node contains the attributes: color, key, left, right, and p (parent).

Red-Black Properties

A red-black tree satisfies the following five properties:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black (no two consecutive red nodes).
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Sentinel

• A single sentinel node T.nil represents all NIL leaves and the root's parent.
• T.nil.color = BLACK; its other attributes can take arbitrary values.
• This avoids wasting space on distinct sentinel nodes for every NIL.

Black-Height

• The black-height of a node x, denoted bh(x), is the number of black nodes on any simple path from x down to a leaf, not including x itself.
• The black-height of the tree is the black-height of its root.

Height Bound (Lemma 13.1)

A red-black tree with n internal nodes has height at most 2 lg(n + 1).

Proof sketch:

• A subtree rooted at any node x contains at least 2^bh(x) − 1 internal nodes (by induction on height).
• By property 4, at least half the nodes on any path from root to leaf (not counting the root) must be black, so bh(root) ≥ h/2.
• Therefore: n ≥ 2^(h/2) − 1, which gives h ≤ 2 lg(n + 1).

Consequence

The operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR all run in O(lg n) time on red-black trees, since each runs in O(h) time and h = O(lg n).

---

13.2 Rotations

Rotations are local operations that change the pointer structure of a BST while preserving the binary-search-tree property. They are used to restore red-black properties after insertions and deletions.

There are two kinds: left rotation and right rotation.

Left Rotation

A left rotation on node x (assuming x.right ≠ T.nil):

• Makes y (x's right child) the new root of the subtree.
• x becomes y's left child.
• y's former left child becomes x's right child.

    x                y
   / \              / \
  α   y    →      x   γ
     / \          / \
    β   γ        α   β

LEFT-ROTATE(T, x)
 1  y = x.right
 2  x.right = y.left
 3  if y.left ≠ T.nil
 4      y.left.p = x
 5  y.p = x.p
 6  if x.p == T.nil
 7      T.root = y
 8  elseif x == x.p.left
 9      x.p.left = y
10  else x.p.right = y
11  y.left = x
12  x.p = y

Right Rotation

RIGHT-ROTATE is symmetric to LEFT-ROTATE (swap "left" and "right").

Key Facts

• Both rotations run in O(1) time.
• Only pointers are changed; all other node attributes remain the same.
• The binary-search-tree property is preserved: keys in α precede x.key, which precedes keys in β, which precede y.key, which precedes keys in γ.

---

13.3 Insertion

Insertion into a red-black tree takes O(lg n) time. The strategy:

1. Insert node z using standard BST insertion.
2. Color z RED.
3. Call RB-INSERT-FIXUP to restore red-black properties.

RB-INSERT

RB-INSERT(T, z)
 1  y = T.nil
 2  x = T.root
 3  while x ≠ T.nil
 4      y = x
 5      if z.key < x.key
 6          x = x.left
 7      else x = x.right
 8  z.p = y
 9  if y == T.nil
10      T.root = z
11  elseif z.key < y.key
12      y.left = z
13  else y.right = z
14  z.left = T.nil
15  z.right = T.nil
16  z.color = RED
17  RB-INSERT-FIXUP(T, z)

Differences from TREE-INSERT:

• All NIL references replaced by T.nil
• z's children set to T.nil (lines 14–15)
• z colored RED (line 16)
• Calls RB-INSERT-FIXUP (line 17)

Which Properties Can Be Violated?

After inserting z (colored red):

• Properties 1, 3, 5 still hold.
• Property 2 violated if z is the root (root must be black).
• Property 4 violated if z's parent is also red (no two consecutive reds).

RB-INSERT-FIXUP

RB-INSERT-FIXUP(T, z)
 1  while z.p.color == RED
 2      if z.p == z.p.p.left
 3          y = z.p.p.right            // y is z's uncle
 4          if y.color == RED
 5              z.p.color = BLACK       // Case 1
 6              y.color = BLACK         // Case 1
 7              z.p.p.color = RED       // Case 1
 8              z = z.p.p              // Case 1
 9          else if z == z.p.right
10              z = z.p                // Case 2
11              LEFT-ROTATE(T, z)      // Case 2
12              z.p.color = BLACK       // Case 3
13              z.p.p.color = RED       // Case 3
14              RIGHT-ROTATE(T, z.p.p) // Case 3
15      else (same as above with "right" and "left" exchanged)
16  T.root.color = BLACK

Loop Invariant

At the start of each iteration:

• (a) Node z is red.
• (b) If z.p is the root, then z.p is black.
• (c) At most one red-black property is violated: either property 2 (z is a red root) or property 4 (z and z.p are both red).

The Three Cases (z.p is a left child)

The symmetric cases apply when z.p is a right child (swap left/right).

Case 1: z's uncle y is RED

• Both z.p and y are red; z.p.p is black.
• Action: Recolor z.p and y to BLACK, z.p.p to RED. Move z up to z.p.p.
• The violation moves up the tree; the loop may repeat.

      B(black)              B(red) ← new z
     / \                   / \
   A(red) D(red)  →    A(black) D(black)
   /                    /
 z(red)               z(red)

Case 2: z's uncle y is BLACK and z is a RIGHT child

• Action: Set z = z.p, then LEFT-ROTATE(T, z).
• Transforms into Case 3. (Case 2 falls through into Case 3.)

Case 3: z's uncle y is BLACK and z is a LEFT child

• Action: Color z.p BLACK, color z.p.p RED, then RIGHT-ROTATE(T, z.p.p).
• The loop terminates (z.p is now black).

Case 2 → Case 3 → Done

      C                C               B
     /                /               / \
    A        →       B        →      A   C
     \              /
      B            A

Analysis

• BST insertion: O(lg n).
• Fixup loop: O(lg n) iterations (only Case 1 repeats, moving z up two levels each time).
• At most 2 rotations total.
• Overall: O(lg n) time.

---

13.4 Deletion

Deletion from a red-black tree takes O(lg n) time. It is more complex than insertion.

RB-TRANSPLANT

A modified TRANSPLANT for red-black trees:

RB-TRANSPLANT(T, u, v)
1  if u.p == T.nil
2      T.root = v
3  elseif u == u.p.left
4      u.p.left = v
5  else u.p.right = v
6  v.p = u.p

Key difference: The assignment v.p = u.p in line 6 is unconditional — it executes even when v is the sentinel T.nil.

RB-DELETE

RB-DELETE(T, z)
 1  y = z
 2  y-original-color = y.color
 3  if z.left == T.nil
 4      x = z.right
 5      RB-TRANSPLANT(T, z, z.right)
 6  elseif z.right == T.nil
 7      x = z.left
 8      RB-TRANSPLANT(T, z, z.left)
 9  else y = TREE-MINIMUM(z.right)
10      y-original-color = y.color
11      x = y.right
12      if y.p == z
13          x.p = y
14      else RB-TRANSPLANT(T, y, y.right)
15          y.right = z.right
16          y.right.p = y
17      RB-TRANSPLANT(T, z, y)
18      y.left = z.left
19      y.left.p = y
20      y.color = z.color
21  if y-original-color == BLACK
22      RB-DELETE-FIXUP(T, x)

Key Tracking Variables

• y: the node removed from or moved within the tree.
  • If z has < 2 children: y = z (removed).
  • If z has 2 children: y = z's successor (moved into z's position, given z's color).
• y-original-color: y's color before any changes. If it was BLACK, fixup is needed.
• x: the node that moves into y's original position. x.p is always set to y's original parent.

When Is Fixup Needed?

If y was red, no properties are violated:

1. No black-heights changed.
2. No adjacent red nodes created.
3. Root remains black.

If y was black, three problems may arise:

1. Property 2: a red child of y may become the new root.
2. Property 4: both x and x.p may be red.
3. Property 5: paths through y's original position now have one fewer black node.

To handle property 5, we conceptually give x an "extra black", making it either doubly black or red-and-black. The fixup procedure resolves this.

RB-DELETE-FIXUP

RB-DELETE-FIXUP(T, x)
 1  while x ≠ T.root and x.color == BLACK
 2      if x == x.p.left
 3          w = x.p.right                  // w is x's sibling
 4          if w.color == RED
 5              w.color = BLACK             // Case 1
 6              x.p.color = RED             // Case 1
 7              LEFT-ROTATE(T, x.p)        // Case 1
 8              w = x.p.right              // Case 1
 9          if w.left.color == BLACK and w.right.color == BLACK
10              w.color = RED               // Case 2
11              x = x.p                    // Case 2
12          else if w.right.color == BLACK
13              w.left.color = BLACK        // Case 3
14              w.color = RED               // Case 3
15              RIGHT-ROTATE(T, w)         // Case 3
16              w = x.p.right              // Case 3
17              w.color = x.p.color         // Case 4
18              x.p.color = BLACK           // Case 4
19              w.right.color = BLACK       // Case 4
20              LEFT-ROTATE(T, x.p)        // Case 4
21              x = T.root                 // Case 4
22      else (same as above with "right" and "left" exchanged)
23  x.color = BLACK

The Goal

The while loop moves the extra black up the tree until:

1. x points to a red-and-black node → color it black (line 23).
2. x points to the root → simply remove the extra black.
3. Suitable rotations and recolorings fix the problem → exit loop.

The Four Cases (x is a left child)

Symmetric cases apply when x is a right child.

Case 1: x's sibling w is RED

• Switch colors of w and x.p, then LEFT-ROTATE on x.p.
• Converts to Case 2, 3, or 4 (new sibling is now black).

Case 2: w is BLACK, both of w's children are BLACK

• Take one black off both x and w (w becomes RED).
• Add an extra black to x.p (x.p becomes the new x).
• The loop repeats with x.p. If entered through Case 1, x.p is red → loop terminates → color x black in line 23.

Case 3: w is BLACK, w's left child is RED, w's right child is BLACK

• Switch colors of w and w.left, then RIGHT-ROTATE on w.
• Transforms into Case 4 (new sibling has a red right child).

Case 4: w is BLACK, w's right child is RED

• Set w's color to x.p's color, x.p to BLACK, w.right to BLACK.
• LEFT-ROTATE on x.p.
• Removes the extra black on x. Set x = T.root to terminate the loop.

Case Flow Summary

Analysis

• Cases 1, 3, and 4 terminate after a constant number of color changes and at most 3 rotations.
• Case 2 is the only case that repeats, moving x up the tree → O(lg n) iterations with no rotations.
• Overall: O(lg n) time, at most 3 rotations.

---

Summary of Complexities