Red-Black Trees: Self-Balancing Binary Search Trees

Introduction

Binary search trees provide O(log n) operations in the average case, but degenerate to O(n) with unbalanced data. Self-balancing trees like red-black trees maintain balance automatically, guaranteeing O(log n) worst-case performance.

Red-black trees are used in many practical implementations: Java’s TreeMap, C++’s std::map, and Linux kernel’s completely fair scheduler.

Properties of Red-Black Trees

A red-black tree is a binary search tree with these properties:

1. Node colors: Each node is either red or black
2. Root is black: The root is always black
3. No red-red: Red nodes cannot have red children (no two consecutive red nodes)
4. Black height: Every path from node to descendant leaves has same number of black nodes
5. Leaves are black: NIL leaves are black

These properties guarantee height ≤ 2log₂(n+1), ensuring O(log n) operations.

Why These Properties Matter

The black-height property ensures balance. Since all paths have equal black nodes, the longest possible path (alternating red-black) is at most twice the shortest (all black). This limits height to approximately 2log₂(n).

Operations

Rotation

Rotations are the fundamental operation for maintaining balance:

# Left rotation around x
def left_rotate(x, parent):
    y = x.right
    x.right = y.left
    if y.left:
        y.left.parent = x
    y.parent = parent
    if not parent:
        return y
    if x == parent.left:
        parent.left = y
    else:
        parent.right = y
    y.left = x
    x.parent = y
    return y

Insertion

Insert new node as red, then fix violations:

def insert_fixup(node):
    while node.parent and node.parent.color == RED:
        if node.parent == node.parent.parent.left:
            uncle = node.parent.parent.right
            if uncle and uncle.color == RED:
                # Case 1: Uncle is red
                node.parent.color = BLACK
                uncle.color = BLACK
                node.parent.parent.color = RED
                node = node.parent.parent
            else:
                if node == node.parent.right:
                    # Case 2: Node is right child
                    node = node.parent
                    left_rotate(node)
                # Case 3: Node is left child
                node.parent.color = BLACK
                node.parent.parent.color = RED
                right_rotate(node.parent.parent)
        else:
            # Symmetric cases
            ...
    root.color = BLACK

Insertion Cases:

1. Uncle is red: Recolor parent, uncle, grandparent
2. Uncle is black, triangle: Rotate to make line case
3. Uncle is black, line: Rotate and recolor

Deletion

Deletion is more complex but follows similar principles. Cases involve fixing double-black (when we remove a black node).

Implementation Considerations

Height: Guaranteed O(log n) for all operations

Memory: Same as regular BST plus color bit

Performance: More rotations than AVL trees during insertions, but fewer during deletions

Compared to AVL: Red-black trees have slightly weaker balance (worst-case height 2log n vs 1.44log n for AVL), but require fewer rotations during insertions.

When to Use Red-Black Trees

• When you need guaranteed O(log n) worst-case operations
• When insertions and deletions are frequent
• When moderate search performance is acceptable
• As underlying structure for maps and sets requiring ordering

Common Uses

• Java: TreeMap, TreeSet
• C++: std::map, std::set
• Linux: CFS scheduler, rbtrees for virtual memory
• Databases: Index structures

External Resources

• GeeksforGeeks - Red Black Tree
• CLRS - Red-Black Trees
• OpenDSA - Red Black Trees

Conclusion

Red-black trees provide practical self-balancing with guaranteed O(log n) operations. Their relatively simple rebalancing logic and good practical performance make them a popular choice for ordered associative containers.