7.2 Red-Black Trees: Properties and Operations

Red-Black Tree Properties

Red-Black trees are self-balancing binary search trees that attach a color (red or black) to every node. This coloring scheme enforces a set of invariants that keep the tree roughly balanced, guaranteeing $O(\log n)$ time for search, insertion, and deletion. They're used heavily in practice: the C++ std::map, Java's TreeMap, and the Linux kernel's scheduler all rely on Red-Black trees under the hood.

Compared to AVL trees, Red-Black trees allow slightly less strict balancing, which means they can be faster for workloads with many insertions and deletions (fewer rotations on average). The tradeoff is that lookups can be marginally slower because the tree can be a bit taller.

The Five Properties

Every valid Red-Black tree satisfies all five of these properties simultaneously:

1. Node coloring: Every node is colored either red or black.
2. Root property: The root is always black.
3. Leaf property: All leaf nodes (NIL/null pointers) are considered black. These aren't "real" nodes with data; they're sentinel placeholders that simplify the logic.
4. Red property: A red node cannot have a red child. Put another way, no two red nodes can appear consecutively on any path. This is sometimes called the no double-red rule.
5. Black-height property: Every path from a given node down to any of its descendant NIL leaves passes through the same number of black nodes. This count is called the node's black-height.

Property 5 is the one that actually enforces balance. Combined with property 4, it guarantees that the longest root-to-leaf path is at most twice the length of the shortest. Here's why: the shortest possible path is all black nodes, and the longest path alternates red and black. Since both paths have the same number of black nodes, the longest path can only squeeze in one red node between each pair of black nodes, making it at most $2 \times$ the shortest.

This means a Red-Black tree with $n$ nodes has a height of at most $2 \log_2(n+1)$, keeping all operations logarithmic.

Red-Black Tree Operations

Insertion

New nodes are always inserted as red. Why red? Inserting a black node would immediately violate the black-height property (property 5) on every path through that node. A red insertion only risks violating the red property (property 4), and only if the parent is also red.

Step-by-step insertion process:

1. Perform a standard BST insertion. Color the new node red.
2. If the new node is the root, recolor it black. Done.
3. If the parent is black, no property is violated. Done.
4. If the parent is red, you have a double-red violation. Now check the uncle (the parent's sibling):

Case A: Uncle is red (recoloring case)

1. Recolor the parent and uncle to black.
2. Recolor the grandparent to red.
3. Move your focus up to the grandparent and repeat from step 2 (the grandparent might now cause a new double-red violation with its parent).

Case B: Uncle is black or NIL (rotation case)

The specific rotation depends on the shape of the path from grandparent to parent to new node:

Deletion

Deletion is the trickiest operation. The high-level idea: remove the node using standard BST deletion, then fix any property violations that result.

Step-by-step deletion process:

1. Find the node to delete. If it has two children, replace its value with its in-order successor (smallest node in the right subtree) or in-order predecessor (largest in the left subtree), then delete that successor/predecessor node instead. This reduces the problem to deleting a node with at most one child.
2. Let the node actually being removed be $v$, and its child (which replaces it) be $u$.

Simple cases:

• If $v$ is red, just remove it. No properties are violated since removing a red node doesn't change any path's black-height.
• If $v$ is black but $u$ is red, replace $v$ with $u$ and recolor $u$ black. This preserves the black-height.

Hard case: both $v$ and $u$ are black (or $u$ is NIL)

This creates a double-black at $u$'s position, meaning that path is now one black node short. Fixing this requires examining the sibling of the double-black node and its children. The cases involve combinations of:

• Sibling is red: rotate to convert into a case where the sibling is black.
• Sibling is black with at least one red child: perform a rotation and recoloring to push an extra black node into the deficient path.
• Sibling is black with two black children: recolor the sibling red, pushing the double-black problem up to the parent. If the parent is red, recolor it black and you're done. If the parent is black, it becomes the new double-black and you repeat.

The exact rotation direction depends on whether the sibling is a left or right child, mirroring the insertion cases. In the worst case, the fix propagates up to the root, but it still takes at most $O(\log n)$ steps.

Time Complexity