Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Red-black insertion: rotate and recolor an ordered index

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A left-leaning red-black search tree represents a balanced ordered index with colored parent links. A newly inserted key starts red. During the return from recursion, a right-leaning red link rotates left, a pair of left red links rotates right, and two red children trigger a color split. The root becomes black before the update finishes. These transformations preserve binary-search order and equal black height, so insertion and search remain O(log n) in the worst case when the invariant is maintained. The program handles unique integer keys and ignores a duplicate; it does not implement deletion or concurrent access.

Operational case

A scheduler inserts deadlines 47, 52, 61, 19, 26, 58, and 83. Sorted traversal must report every deadline once, regardless of the root chosen by rotations. The audit also rejects a right-leaning red link, adjacent red links, unequal black height, and an out-of-order descendant. Keeping a separate audit in the teaching program makes the invariant observable; application code would normally run such checks in tests rather than after every live insertion. A deadline's payload or tie policy would need its own key convention before this becomes a scheduler index.

Working Python program

python
class DeadlineNode:
    def __init__(self, deadline):
        self.deadline = deadline
        self.left = None
        self.right = None
        self.red = True


def is_red(node):
    return node is not None and node.red


def rotate_left(parent):
    promoted = parent.right
    parent.right = promoted.left
    promoted.left = parent
    promoted.red, parent.red = parent.red, True
    return promoted


def rotate_right(parent):
    promoted = parent.left
    parent.left = promoted.right
    promoted.right = parent
    promoted.red, parent.red = parent.red, True
    return promoted


def split_four_node(parent):
    parent.red = not parent.red
    parent.left.red = not parent.left.red
    parent.right.red = not parent.right.red


def insert_at(parent, deadline):
    if parent is None:
        return DeadlineNode(deadline)
    if deadline < parent.deadline:
        parent.left = insert_at(parent.left, deadline)
    elif deadline > parent.deadline:
        parent.right = insert_at(parent.right, deadline)
    else:
        return parent
    if is_red(parent.right) and not is_red(parent.left):
        parent = rotate_left(parent)
    if is_red(parent.left) and is_red(parent.left.left):
        parent = rotate_right(parent)
    if is_red(parent.left) and is_red(parent.right):
        split_four_node(parent)
    return parent


def insert(root, deadline):
    root = insert_at(root, deadline)
    root.red = False
    return root


def ordered(parent):
    if parent is None:
        return []
    return ordered(parent.left) + [parent.deadline] + ordered(parent.right)


def audit(parent, lower, upper):
    if parent is None:
        return 1
    assert lower < parent.deadline < upper
    assert not is_red(parent.right)
    if parent.red:
        assert not is_red(parent.left)
    left_black = audit(parent.left, lower, parent.deadline)
    right_black = audit(parent.right, parent.deadline, upper)
    assert left_black == right_black
    return left_black + (not parent.red)


deadline_root = None
for deadline in (47, 52, 61, 19, 26, 58, 83):
    deadline_root = insert(deadline_root, deadline)
assert not deadline_root.red
print(ordered(deadline_root))
print(audit(deadline_root, float("-inf"), float("inf")) > 0)

Output

Output
[19, 26, 47, 52, 58, 61, 83]
True

Time, space, and tradeoff

One insertion follows a logarithmic-height path and performs only bounded local rotations or color changes per visited node, giving O(log n) time and O(log n) recursive stack space. The index stores O(n) nodes. The final in-order list and full audit each take O(n) time and are demonstration checks, not part of ordinary insertion. Python assertions can be disabled, so production invariant testing should use explicit errors. The implementation does not erase deadlines; deletion requires additional move-red and fix-up cases and must be tested separately.

Common Mistakes

  • Do not mark the new root red after a completed insertion.
  • Do not rotate pointers without moving the corresponding color relationship.
  • Do not claim this insertion-only program handles deletion or cross-thread mutation.

Connected lessons

Apply this mutation in the index mutation project, then check the mutation quiz.

Red-black deletion: move color before removing a key extends this operation.

data structures
range-query-structures
Storage details