Red-black BST (insert)

Cost and properties

search / insert	≤ 2 lg n — guaranteed
height	≤ 2 lg n
extra state	one bit per node
used by	java.util.TreeMap, C++ std::map

Reference: Sedgewick & Wayne, §3.3; Guibas–Sedgewick 1978.

Red-black BST (insert) in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

RED, BLACK = True, False

class RedBlackBST:
    # A LEFT-LEANING red-black BST is a 2-3 tree drawn as a BST: a red link
    # binds two nodes into one 3-node. Three invariants:
    #   1. red links lean LEFT   2. no node has two red links
    #   3. perfect black balance: every root-to-null path has the same
    #      number of black links

    class _Node:
        def __init__(self, key, val, color):
            self.key, self.val, self.color = key, val, color
            self.left = self.right = None

    def __init__(self):
        self.root = None

    def _is_red(self, x):
        return x is not None and x.color == RED

    def _rotate_left(self, h):            # a right-leaning red link -> left
        x = h.right
        h.right = x.left
        x.left = h
        x.color, h.color = h.color, RED
        return x

    def _rotate_right(self, h):           # two reds in a row -> balanced
        x = h.left
        h.left = x.right
        x.right = h
        x.color, h.color = h.color, RED
        return x

    def _flip_colors(self, h):            # split a temporary 4-node
        h.color = RED
        h.left.color = BLACK
        h.right.color = BLACK

    def put(self, key, val):
        self.root = self._put(self.root, key, val)
        self.root.color = BLACK           # the root is always black

    def _put(self, h, key, val):
        if h is None:
            return RedBlackBST._Node(key, val, RED)   # new links are RED
        if key < h.key:
            h.left = self._put(h.left, key, val)
        elif key > h.key:
            h.right = self._put(h.right, key, val)
        else:
            h.val = val
        # the three fixes, applied on the way back up:
        if self._is_red(h.right) and not self._is_red(h.left):
            h = self._rotate_left(h)
        if self._is_red(h.left) and self._is_red(h.left.left):
            h = self._rotate_right(h)
        if self._is_red(h.left) and self._is_red(h.right):
            self._flip_colors(h)
        return h

Why it works

The 2-3 tree correspondence

Start from a 2-3 tree (nodes hold one or two keys; every path to the bottom has the same length, so it is perfectly balanced) and represent a 3-node as two BST nodes joined by a red link. Every red-black operation is a 2-3 tree operation in disguise, and the perfect balance of the 2-3 tree becomes perfect black balance. That is where the height guarantee comes from — not from measuring or rebalancing.

Three fixes, always in this order

1. Right-leaning red → rotate left. Reds must lean left, by convention, so there is only one shape to handle.
2. Two reds in a row → rotate right. Creates a temporary 4-node with two red children.
3. Two red children → flip colours. Splits the 4-node and passes a red link up to the parent — which is why the fixes must run on the way back up the recursion.

All three are local: they touch a node, its children and one grandchild. Nothing else in the tree is examined, which is what keeps insert logarithmic.

Why insert new nodes red

A new red link adds no black links to any path, so black balance is preserved for free. The colour is a promise that gets repaired upwards rather than a property to be recomputed. Note the root is forced black after every put: a red root would mean a red link with no parent to glue it to.

Cost in practice

Height ≤ 2 lg n, and the average search is ~1.00 lg n — essentially indistinguishable from a perfectly balanced tree, for any insertion order. This is the structure behind java.util.TreeMap, C++ std::map and many filesystem indexes. Sedgewick's left-leaning formulation exists because the classical version needs several times more code to say the same thing.

What to try in the animation

Try sorted insert, the input that ruins a plain BST: here the tree stays short because each new right-leaning red link is immediately rotated.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• course example — insert: S E A R C H X M P L
• sorted insert — insert: A C E H L M P R S X
• reverse sorted — insert: X S R P M L H E C A
• numbers — insert: 10 20 30 40 50 60 70

Open Red-black BST (insert) in the player →