Lesson 11 · Non-linear structures

Red-Black Trees

Red-Black Trees use node coloring rules to maintain approximate balance, prioritizing faster insertions and deletions over strict height guarantees.

The Coloring Rules

A Red-Black Tree assigns a color (red or black) to every node and enforces four rules: the root is black, all leaves (NIL) are black, red nodes cannot have red children, and every path from a node to its leaves must contain the exact same number of black nodes.

Approximate Balance

Unlike AVL trees that demand strict height differences, the coloring rules of a Red-Black tree only guarantee that the longest path from root to leaf is no more than twice as long as the shortest path. This relaxed balance reduces the frequency of restructuring operations.

Key reference

Terms, operations, and practical uses

Color Properties

Root PropertyThe root node of a Red-Black tree is always colored black.
Red PropertyA red node cannot have a red child (no two consecutive red nodes on any path).
Black Depth PropertyEvery path from a node to any of its descendant NIL leaves contains the exact same number of black nodes.

Modification Rules

Insertion ColorNew nodes are always initially colored red to avoid violating the Black Depth property.
RecoloringIf a red node is inserted under a red parent and the uncle is also red, we recolor the parent, uncle, and grandparent.
RestructuringIf the uncle is black, we perform tree rotations (similar to AVL) to restore the Red Property.

Practical Use

Approximate BalanceThe longest path (alternating red/black) is at most twice the shortest path (all black).
Write EfficiencyBecause it requires fewer rotations than AVL trees on average, it is preferred for write-heavy workloads.
Standard LibrariesThe underlying data structure for C++ std::map, Java TreeMap, and many database indexing systems.

Code example

Repair red-black tree properties after insertion

RED, BLACK = "Red", "Black"

class RBNode:
    def __init__(self, val, color=RED):
        self.val = val
        self.color = color
        self.left = None
        self.right = None

class RedBlackTree:
    def __init__(self):
        self.root = None

    def insert(self, val):
        node = RBNode(val)          # every new node starts Red
        if not self.root:
            self.root = node
        else:
            current = self.root
            while True:
                if val < current.val:
                    if not current.left:
                        current.left = node
                        break
                    current = current.left
                else:
                    if not current.right:
                        current.right = node
                        break
                    current = current.right
        self.root.color = BLACK     # the root is always recoloured Black
        return node

tree = RedBlackTree()
tree.insert(10)
child = tree.insert(20)
print('Root is', tree.root.color)

class RedBlackTree {
public:
    void insert(int val) {
        // Insert Red node, fix violations
    }
};

class RedBlackTree {
    public void insert(int val) {
        // Insert Red node, fix violations
    }
}

Inputinsert a red node beneath a red parent

OutputRoot is Black

Example

Run the example step by step

Output

Restructuring Operations

When an insertion (which defaults to a red node) violates the rule against consecutive red nodes, the tree fixes it. Depending on the color of the node's 'uncle', the tree will either recolor the ancestors or perform a tree rotation, bounding the fix to O(log N) time and at most 3 rotations.

Ubiquity in Standard Libraries

Because Red-Black trees require fewer rotations during modifications while still guaranteeing O(log N) lookups, they are the structure of choice for most built-in language libraries. C++'s std::map, Java's TreeMap, and the Linux kernel's Completely Fair Scheduler all rely on them.