Red-Black Tree

A balanced search tree that colours nodes red and black to keep its height O(log n); the tree behind TreeMap and std::map.

Worth knowing first

AVL Tree

#How does it work?

A red-black tree is a binary search tree that balances itself by colouring every node red or black. Java's TreeMap, C++'s std::map and the Linux kernel's scheduler use red-black trees.

There are five rules: (1) every node is red or black, (2) the root is black, (3) empty (null) leaves count as black, (4) a red node's children are black, so two reds never follow each other, (5) every path from a node down to its null leaves has the same number of black nodes.

These rules keep the longest path at most twice the shortest, so even though the tree isn't perfectly balanced its height stays O(log n).

A new node is always inserted red. If its parent is red too, rule 4 is broken and we look at the uncle: a red uncle means recolouring, a black uncle means one or two rotations.

#Try it yourself

$ red_black-tree --interactive

Insert a value: a new node starts red. A red node may not have a red child; recolouring and rotations keep that rule.

ValueSpeed

Elements: 6/12VisitingNewRemovingFound / read

#Basic operations

insert(x): Adds a red node like a BST, removes red-red conflicts with recolouring and rotations, and finally colours the root black.
search(x): A plain BST search; colours don't affect it.
delete(x): Deletes like a BST; if a black node goes, it fixes the "double black" with rotations and recolouring based on the sibling. It has more cases than insert.
recolor: With a red uncle, the parent and uncle become black and the grandparent red; the problem moves up.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

from typing import Optional

RED, BLACK = "R", "B"


class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.color = RED  # new nodes start red
        self.left: Optional["Node"] = None
        self.right: Optional["Node"] = None
        self.parent: Optional["Node"] = None


class RedBlackTree:
    def __init__(self) -> None:
        self.root: Optional[Node] = None

    def _rotate_left(self, x: Node) -> None:
        y = x.right
        x.right = y.left
        if y.left:
            y.left.parent = x
        self._replace(x, y)
        y.left = x
        x.parent = y

    def _rotate_right(self, x: Node) -> None:
        y = x.left
        x.left = y.right
        if y.right:
            y.right.parent = x
        self._replace(x, y)
        y.right = x
        x.parent = y

    def _replace(self, old: Node, new: Node) -> None:
        """Puts `new` where `old` hangs from its parent."""
        new.parent = old.parent
        if old.parent is None:
            self.root = new
        elif old is old.parent.left:
            old.parent.left = new
        else:
            old.parent.right = new

    def insert(self, value: int) -> None:
        # 1. Plain BST insert of a red node.
        node, parent, cur = Node(value), None, self.root
        while cur:
            parent = cur
            if value == cur.value:
                return
            cur = cur.left if value < cur.value else cur.right
        node.parent = parent
        if parent is None:
            self.root = node
        elif value < parent.value:
            parent.left = node
        else:
            parent.right = node
        # 2. Fix red-red conflicts.
        while node.parent and node.parent.color == RED:
            parent = node.parent
            grand = parent.parent
            parent_is_left = parent is grand.left
            uncle = grand.right if parent_is_left else grand.left
            if uncle and uncle.color == RED:  # recolour and move up
                parent.color = uncle.color = BLACK
                grand.color = RED
                node = grand
                continue
            if parent_is_left and node is parent.right:  # inner child: make it outer
                self._rotate_left(parent)
                node, parent = parent, node
            elif not parent_is_left and node is parent.left:
                self._rotate_right(parent)
                node, parent = parent, node
            parent.color, grand.color = BLACK, RED  # outer child: rotate grandparent
            if parent_is_left:
                self._rotate_right(grand)
            else:
                self._rotate_left(grand)
        self.root.color = BLACK


def preorder(node: Optional[Node], out: list) -> list:
    if node:
        out.append(f"{node.value}{node.color}")
        preorder(node.left, out)
        preorder(node.right, out)
    return out


tree = RedBlackTree()
for v in [10, 20, 30, 15, 25, 5]:
    tree.insert(v)
print(" ".join(preorder(tree.root, [])))  # value + colour, root first

#Complexity

Operation	Time
search	O(log n)
insert	O(log n), at most 2 rotations
delete	O(log n), at most 3 rotations
Memory	O(n) + 1 colour bit per node

Thanks to the black-height rule the height is at most 2 · log2(n + 1). Inserts and deletes do a constant number of rotations; recolouring may repeat O(log n) times upwards but is cheap. It is more loosely balanced than AVL: lookups can take a little longer, updates need fewer rotations.

#When to use it?

It is the standard choice for ordered structures with frequent inserts and deletes: Java TreeMap/TreeSet, C++ std::map/std::set, the Linux CFS scheduler and many databases' in-memory indexes. For a lookup-heavy workload an AVL tree can be slightly faster.

#Practice

Easy

1/3

What colour does a newly inserted node get in a red-black tree?

1Red
2Black
3Its parent's colour
4Random

1–4 pick · ← → move · enter continue

Medium

1/1

If the new red node's parent and uncle are both red, what happens?

1Parent and uncle become black, the grandparent red
2Rotate around the grandparent
3The new node becomes black
4Nothing; no rule is broken

1–4 pick · ← → move · enter continue

Hard

1/1

Why is a red-black tree usually faster than AVL for inserts and deletes?

1It is more loosely balanced and needs fewer rotations
2Its searches are shorter
3It uses less memory
4It never rotates

1–4 pick · ← → move · enter continue