Red-Black Tree

The idea

A plain binary search tree can degrade into a long chain, for example when keys arrive in sorted order, and then every operation becomes O(n). Self-balancing trees prevent that. An AVL tree tracks heights exactly. A red-black tree uses a cheaper trick: one extra bit per node, its colour, and a few rules that keep the tree roughly balanced.

The five rules

1. Every node is red or black.
2. The root is black.
3. Every empty child (NIL leaf) counts as black.
4. A red node never has a red child (no two reds in a row).
5. From any node, every path down to its NIL leaves passes the same number of black nodes (its black-height).

Rules 4 and 5 together guarantee that the longest path (alternating red and black) is at most twice the shortest (all black). So the height is at most 2 · log₂(n + 1).

Inserting

1. Insert the key like a normal BST and colour it red. A red node doesn’t change any black count, so rule 5 still holds.
2. If its parent is black, you are done.
3. If its parent is red, rule 4 is broken. Look at the uncle (the parent’s sibling):

Finally, colour the root black.

Case 1 only recolours, though it can repeat up the tree. Cases 2 and 3 end the fix-up with at most two rotations in total.

Example

Start with 20 (black), whose children 10 and 30 are black, and 10 has red children 5 and 15.

• Insert 12: it goes under 15 as a red child. Its parent 15 is red and its uncle 5 is red, so this is case 1: 15 and 5 turn black and 10 turns red. 10’s parent (20) is black, so we stop.
• Insert 13: it goes under 12 as a right child. Parent 12 is red and the uncle (15’s right side) is NIL, so black. 13 is an inner child, so case 2 rotates left at 12. That gives a straight line, and case 3 colours 13 black and 15 red, then rotates right at 15. Now 13 has children 12 and 15, both red.

Code (insertion fix-up)

RED, BLACK = True, False

class Node:
    def __init__(self, key):
        self.key, self.color = key, RED
        self.left = self.right = self.parent = None

def is_red(n):
    return n is not None and n.color == RED

def fix_insert(tree, z):
    while is_red(z.parent):
        p, g = z.parent, z.parent.parent
        if p is g.left:
            uncle = g.right
            if is_red(uncle):                       # case 1: recolour
                p.color = uncle.color = BLACK
                g.color = RED
                z = g
                continue
            if z is p.right:                        # case 2: inner child
                z = p
                tree.rotate_left(z)
                p = z.parent
            p.color, g.color = BLACK, RED           # case 3: outer child
            tree.rotate_right(g)
        else:                                       # mirror image
            uncle = g.left
            if is_red(uncle):
                p.color = uncle.color = BLACK
                g.color = RED
                z = g
                continue
            if z is p.left:
                z = p
                tree.rotate_right(z)
                p = z.parent
            p.color, g.color = BLACK, RED
            tree.rotate_left(g)
    tree.root.color = BLACK

rotate_left and rotate_right are the same rotations used by AVL trees. They move nodes but keep the BST order.

Red-black tree vs AVL tree

Where is it used?

Red-black trees are everywhere: Java’s TreeMap and TreeSet, C++’s std::map and std::set, the Linux kernel (its CPU scheduler, CFS, keeps runnable tasks in a red-black tree) and many database and file-system indexes.

Common mistakes

• Inserting the new node as black. That breaks rule 5 everywhere along its path.
• Forgetting that a missing child (NIL) is black. A missing uncle means case 2 or 3, not case 1.
• Applying case 3 to a zig-zag shape. Do the case 2 rotation first.
• Forgetting the last step: colour the root black.