Red-Black Tree — Talent Factory

Insert or delete keys and follow every sub-step of the repair one by one: recoloring, rotations, cases A–C for insertion and cases 1–4 for deletion. The Sedgewick view draws red edges horizontally and makes the link to the 2-3-4 tree visible.

The principle

A red-black tree is a binary search tree with five rules:

Every node is red or black.
The root is black.
The NIL leaves (empty children) are black.
A red node has only black children.
Every path from a node down to its NIL leaves contains the same number of black nodes.

As a result, the longest path is at most twice as long as the shortest. The tree is balanced less strictly than an AVL tree, but needs fewer rotations per change (upper bound).

Insertion

The new node N is red and violates at most rule 4 (red under red). What matters is the uncle O, the sibling of the parent V:

Case	Uncle O	Action
A	red	V and O black, G red. The problem moves up to the grandparent G.
B	black, N and V form a line	V black, G red, one rotation at G. Done.
C	black, N and V form a kink	Rotation at V turns the kink into a line, then case B.

Cases B and C each exist in a mirrored version. Deletion adds four more cases (sibling red, sibling black with black children, kink, line). The simulation shows them step by step.

Python code (insertion)

RED, BLACK = True, False


class Node:
    def __init__(self, key, parent=None):
        self.key, self.color = key, RED      # a new node is always red
        self.left = self.right = None        # None = black NIL leaf
        self.parent = parent


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


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

    def _replace(self, old, new):
        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 _rotate_left(self, x):
        y = x.right
        x.right = y.left
        if y.left:
            y.left.parent = x
        self._replace(x, y)
        y.left, x.parent = x, y

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

    def insert(self, key):
        parent, cur = None, self.root
        while cur:                           # as in an ordinary BST
            if key == cur.key:
                return
            parent, cur = cur, (cur.left if key < cur.key else cur.right)
        n = Node(key, parent)
        if parent is None:
            self.root = n
        elif key < parent.key:
            parent.left = n
        else:
            parent.right = n
        self._fix_insert(n)

    def _fix_insert(self, n):
        while is_red(n.parent):              # rule 4 violated: red under red
            p = n.parent
            g = p.parent                     # grandparent (the root is black)
            p_is_left = p is g.left
            uncle = g.right if p_is_left else g.left
            if is_red(uncle):                # case A: recolor, problem moves up
                p.color = uncle.color = BLACK
                g.color = RED
                n = g
                continue
            if n is (p.right if p_is_left else p.left):   # case C: kink -> line
                (self._rotate_left if p_is_left else self._rotate_right)(p)
                n, p = p, n
            p.color, g.color = BLACK, RED    # case B: one rotation at G
            (self._rotate_right if p_is_left else self._rotate_left)(g)
        self.root.color = BLACK              # rule 2

Usage: tree = RedBlackTree(), then tree.insert(10) for each key.