Red-Black Trees Explained: Rules, Rotations & Real-World Usage

Red-Black trees are the most widely used self-balancing BSTs in production systems. Java’s TreeMap, C++‘s std::map, and Linux’s Completely Fair Scheduler all use Red-Black trees internally. They are slightly less balanced than AVL trees but have cheaper insertion and deletion, making them the default choice when write operations are frequent.

The 5 Red-Black tree rules

Every Red-Black tree must satisfy all five of these properties simultaneously:

1. Every node is either RED or BLACK
2. The root is always BLACK
3. Every leaf (NIL/null) is BLACK — we treat null pointers as black leaf nodes
4. No two consecutive RED nodes — if a node is red, both its children must be black
5. Black height consistency — every path from a node to any of its descendant NIL leaves passes through the same number of black nodes

Rule 5 is the key insight. It guarantees that no path from root to leaf is more than twice as long as any other, keeping the tree roughly balanced.

Why these rules guarantee O(log n)

The black-height property ensures that the longest path (alternating red-black) is at most twice the shortest path (all black). If the black height is b, then:

• Shortest path: b nodes (all black)
• Longest path: 2b nodes (alternating red-black)

For a tree with n internal nodes, the height h satisfies:

h <= 2 * log2(n + 1)

This means all operations (search, insert, delete) are O(log n) in the worst case.

Node structure

RED = True
BLACK = False

class RBNode:
    def __init__(self, val, color=RED):
        self.val = val
        self.color = color  # new nodes are always RED
        self.left = None
        self.right = None
        self.parent = None

New nodes are always inserted as RED. Why? Inserting a red node never violates the black-height property (Rule 5). It might violate Rule 4 (no double-red), but that is easier to fix.

Red-Black tree skeleton

class RedBlackTree:
    def __init__(self):
        # Sentinel NIL node (black leaf)
        self.NIL = RBNode(val=None, color=BLACK)
        self.root = self.NIL

    def _left_rotate(self, x):
        """Left rotation around node x."""
        y = x.right
        x.right = y.left
        if y.left != self.NIL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def _right_rotate(self, y):
        """Right rotation around node y."""
        x = y.left
        y.left = x.right
        if x.right != self.NIL:
            x.right.parent = y
        x.parent = y.parent
        if y.parent is None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        x.right = y
        y.parent = x

Insertion

Insert follows BST insertion, then fixes violations.

Step 1: BST insert (color new node RED)

def insert(self, val):
    """Insert value into Red-Black Tree."""
    new_node = RBNode(val, color=RED)
    new_node.left = self.NIL
    new_node.right = self.NIL

    # Standard BST insert
    parent = None
    current = self.root
    while current != self.NIL:
        parent = current
        if val < current.val:
            current = current.left
        elif val > current.val:
            current = current.right
        else:
            return  # no duplicates

    new_node.parent = parent
    if parent is None:
        self.root = new_node
    elif val < parent.val:
        parent.left = new_node
    else:
        parent.right = new_node

    # Fix Red-Black violations
    self._fix_insert(new_node)

Step 2: Fix violations

After inserting a red node, we might have a double-red violation (red child of red parent). There are three cases to handle.

def _fix_insert(self, node):
    """Fix Red-Black tree violations after insertion."""
    while node != self.root and node.parent.color == RED:
        if node.parent == node.parent.parent.left:
            uncle = node.parent.parent.right

            # Case 1: Uncle is RED → recolor
            if uncle.color == RED:
                node.parent.color = BLACK
                uncle.color = BLACK
                node.parent.parent.color = RED
                node = node.parent.parent  # move up

            else:
                # Case 2: Node is right child → left rotate to Case 3
                if node == node.parent.right:
                    node = node.parent
                    self._left_rotate(node)

                # Case 3: Node is left child → right rotate + recolor
                node.parent.color = BLACK
                node.parent.parent.color = RED
                self._right_rotate(node.parent.parent)

        else:
            # Mirror: parent is right child of grandparent
            uncle = node.parent.parent.left

            if uncle.color == RED:
                node.parent.color = BLACK
                uncle.color = BLACK
                node.parent.parent.color = RED
                node = node.parent.parent

            else:
                if node == node.parent.left:
                    node = node.parent
                    self._right_rotate(node)

                node.parent.color = BLACK
                node.parent.parent.color = RED
                self._left_rotate(node.parent.parent)

    # Root must always be black
    self.root.color = BLACK

Understanding the three insertion cases

Let us walk through each case with concrete examples.

Case 1: Uncle is RED (color flip)

When both the parent and uncle are red, we can fix the double-red by recoloring:

Before:                After:
      G(B)                G(R) ← check this next
     / \                 / \
   P(R)  U(R)         P(B)  U(B)
   /                   /
  N(R)               N(R)

- Parent and Uncle → BLACK
- Grandparent → RED
- Move up to grandparent and repeat

No rotations needed. But the grandparent turning red might cause a new violation higher up, so we continue the loop.

Case 2: Uncle is BLACK, node is inner child (triangle)

The node forms a “triangle” with its parent and grandparent (e.g., parent is left child, node is right child):

Before:           After rotation (now Case 3):
    G(B)              G(B)
   / \               / \
  P(R) U(B)        N(R) U(B)
   \                /
   N(R)           P(R)

Rotate parent in opposite direction of node.
This converts it to Case 3.

Case 3: Uncle is BLACK, node is outer child (line)

The node forms a straight line with parent and grandparent:

Before:              After:
    G(B)                P(B)
   / \                /   \
  P(R) U(B)        N(R)   G(R)
 /                          \
N(R)                        U(B)

Rotate grandparent + recolor.

Insertion example walkthrough

Insert 10, 20, 30, 15, 25:

# Insert 10: Root → color BLACK
#   10(B)

# Insert 20: Red child of black parent → OK
#   10(B)
#     \
#     20(R)

# Insert 30: Double red! Uncle is NIL (BLACK)
# This is Case 3 (RR line) → left rotate 10
#
# Before:    10(B)          After:    20(B)
#              \                     /    \
#             20(R)               10(R)  30(R)
#               \
#              30(R)

# Insert 15: Red child of red parent!
# Uncle 30 is RED → Case 1 (color flip)
#
# Before:    20(B)          After:    20(B)
#           /    \                   /    \
#        10(R)  30(R)            10(B)  30(B)
#           \                      \
#          15(R)                  15(R)

# Insert 25: Red child of red parent!
# Uncle is NIL (BLACK), inner child → Case 2 then Case 3
#
# Before:    20(B)
#           /    \
#        10(B)  30(B)
#           \    /
#          15(R) 25(R)
#
# Case 2: Right rotate 30 → Case 3: Left rotate 20
# Final:     20(B)
#           /    \
#        10(B)  25(B)
#           \      \
#          15(R)  30(R)

Search and traversal

Search is identical to BST search — the color does not affect the search path:

def search(self, val):
    """Search for value in Red-Black Tree."""
    current = self.root
    while current != self.NIL:
        if val == current.val:
            return True
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    return False

def inorder(self):
    """Return sorted list of all values."""
    result = []
    self._inorder(self.root, result)
    return result

def _inorder(self, node, result):
    if node != self.NIL:
        self._inorder(node.left, result)
        result.append(node.val)
        self._inorder(node.right, result)

Deletion (conceptual overview)

Red-Black deletion is significantly more complex than insertion. It involves:

1. Standard BST deletion to remove the node
2. Fix-up if a black node was removed (which changes black heights)

The fix-up has 4 cases (plus their mirrors), involving the sibling’s color and the sibling’s children’s colors. Here is a simplified conceptual version:

def _fix_delete(self, node):
    """Fix Red-Black violations after deletion."""
    while node != self.root and node.color == BLACK:
        if node == node.parent.left:
            sibling = node.parent.right

            # Case 1: Sibling is RED
            if sibling.color == RED:
                sibling.color = BLACK
                node.parent.color = RED
                self._left_rotate(node.parent)
                sibling = node.parent.right

            # Case 2: Sibling's children are both BLACK
            if (sibling.left.color == BLACK and
                sibling.right.color == BLACK):
                sibling.color = RED
                node = node.parent

            else:
                # Case 3: Sibling's right child is BLACK
                if sibling.right.color == BLACK:
                    sibling.left.color = BLACK
                    sibling.color = RED
                    self._right_rotate(sibling)
                    sibling = node.parent.right

                # Case 4: Sibling's right child is RED
                sibling.color = node.parent.color
                node.parent.color = BLACK
                sibling.right.color = BLACK
                self._left_rotate(node.parent)
                node = self.root  # done

        else:
            # Mirror cases for right child
            sibling = node.parent.left

            if sibling.color == RED:
                sibling.color = BLACK
                node.parent.color = RED
                self._right_rotate(node.parent)
                sibling = node.parent.left

            if (sibling.right.color == BLACK and
                sibling.left.color == BLACK):
                sibling.color = RED
                node = node.parent
            else:
                if sibling.left.color == BLACK:
                    sibling.right.color = BLACK
                    sibling.color = RED
                    self._left_rotate(sibling)
                    sibling = node.parent.left

                sibling.color = node.parent.color
                node.parent.color = BLACK
                sibling.left.color = BLACK
                self._right_rotate(node.parent)
                node = self.root

    node.color = BLACK

Comparison: Red-Black vs AVL

Property	Red-Black	AVL
Height bound	<= 2 log(n+1)	<= 1.44 log(n+2)
Rotations per insert	<= 2	<= 2
Rotations per delete	<= 3	O(log n)
Recoloring per insert	O(log n)	N/A
Lookup speed	Slightly slower	Slightly faster
Insert/Delete speed	Slightly faster	Slightly slower
Implementation	More complex	Simpler

Key insight: Red-Black trees do at most 3 rotations per deletion, while AVL trees might need O(log n) rotations. Since rotations modify the tree structure (and potentially require cache invalidation in concurrent systems), Red-Black trees are preferred for write-heavy workloads.

Real-world usage

Java TreeMap and TreeSet

Java’s TreeMap and TreeSet use Red-Black trees. When you call put() or add(), the Red-Black insertion algorithm runs behind the scenes.

# Python equivalent using sortedcontainers (not RB, but same idea)
from sortedcontainers import SortedDict, SortedSet

sd = SortedDict()
sd[5] = "five"
sd[3] = "three"
sd[8] = "eight"
# Internally maintains sorted order with O(log n) operations

Linux CFS Scheduler

The Linux Completely Fair Scheduler uses a Red-Black tree to track processes by their “virtual runtime”. The leftmost node (smallest vruntime) is always the next process to schedule. This gives O(log n) scheduling decisions.

C++ std::map and std::set

The C++ standard library typically implements std::map, std::set, std::multimap, and std::multiset using Red-Black trees.

Other uses

• NGINX uses RB trees for timer event management
• Epoll (Linux I/O multiplexing) uses RB trees internally
• Memory allocators (jemalloc) use RB trees for free block management

Verifying Red-Black properties

def verify_rb_tree(self):
    """Verify all 5 Red-Black properties."""
    # Rule 2: Root is black
    if self.root.color != BLACK:
        return False, "Root is not black"

    # Check rules 4 and 5 recursively
    valid, black_height = self._verify(self.root)
    if not valid:
        return False, "Violation found"

    return True, f"Valid RB tree, black height = {black_height}"

def _verify(self, node):
    """Return (is_valid, black_height)."""
    if node == self.NIL:
        return True, 1  # NIL nodes are black (Rule 3)

    # Rule 4: No double-red
    if node.color == RED:
        if (node.left.color == RED or node.right.color == RED):
            return False, 0

    left_valid, left_bh = self._verify(node.left)
    right_valid, right_bh = self._verify(node.right)

    if not left_valid or not right_valid:
        return False, 0

    # Rule 5: Equal black heights
    if left_bh != right_bh:
        return False, 0

    # Add 1 if current node is black
    return True, left_bh + (1 if node.color == BLACK else 0)

When to use Red-Black trees

Use Red-Black trees when:

• You need a balanced BST with guaranteed O(log n) operations
• Write operations (insert/delete) are frequent
• You are building a language runtime or OS component
• You need ordered data with range queries

Use something else when:

• Read-heavy workload → AVL tree (stricter balance, faster lookup)
• Only need insert + lookup → Hash table (O(1) average)
• Static data → Sorted array with binary search
• Need persistent/immutable versions → Consider B-trees or treaps

Practice problems

1. Implement Red-Black Insert — Follow the three cases
2. Verify Red-Black Properties — Check all 5 rules recursively
3. Count Red and Black Nodes — Traverse and count by color
4. Find Black Height — Path from root to any NIL
5. Compare RB and AVL Heights — Insert same data, measure heights
6. Implement Ordered Set — Use RB tree for rank, select, range queries

Key takeaways

• Red-Black trees use 5 rules to maintain approximate balance
• New nodes are always RED to avoid black-height violations
• Insertion has 3 cases: uncle red (recolor), uncle black + triangle (rotate to line), uncle black + line (rotate + recolor)
• At most 2 rotations per insert and 3 per delete — better than AVL for writes
• They are the industry standard for self-balancing BSTs in production systems
• Understanding the rules is more important than memorizing the code — most languages provide built-in ordered collections