Red-black trees: audit color and black-height invariants

Operational case

A scheduler indexes deadlines 47, 52, and 61. Deadline 52 is the black root; 47 and 61 are red children. Both root-to-null paths contain the same number of black nodes. Adding a red node 19 beneath red node 47 makes two red nodes adjacent and fails the audit even though numeric key order still looks correct. This shows why checking only in-order traversal is insufficient. A production insertion routine must handle red-uncle recoloring, inner and outer rotations, and root recoloring, then preserve the black-height rule across the whole changed path.

Working Python program

class DeadlineNode:
    def __init__(self, deadline, color, left=None, right=None):
        self.deadline = deadline
        self.color = color
        self.left = left
        self.right = right

def black_height(node, lower, upper):
    if node is None:
        return 1
    assert lower < node.deadline < upper
    assert node.color in ("red", "black")
    if node.color == "red":
        assert node.left is None or node.left.color == "black"
        assert node.right is None or node.right.color == "black"
    left_height = black_height(node.left, lower, node.deadline)
    right_height = black_height(node.right, node.deadline, upper)
    assert left_height == right_height
    return left_height + (node.color == "black")

root = DeadlineNode(52, "black", DeadlineNode(47, "red"), DeadlineNode(61, "red"))
assert root.color == "black"
print(black_height(root, float("-inf"), float("inf")))
root.left.left = DeadlineNode(19, "red")
try:
    black_height(root, float("-inf"), float("inf"))
except AssertionError:
    print("invalid")

Output

2
invalid

Time, space, and tradeoff

The audit visits every node and runs in O(n) time, with O(h) recursion stack for tree height h. That is separate from O(log n) search and update bounds for a correctly maintained red-black tree. The sample uses assertions for a compact teaching check; production validation should raise explicit errors even when Python optimization disables assertions. A checker also needs a root-color test at its public boundary. Never infer that a tree is valid just because local parent-child ordering holds or a single sample insertion worked.

Common Mistakes

• Do not equate sorted in-order output with valid color invariants.
• Do not count null leaves inconsistently across paths.
• Do not present an invariant checker as a complete update implementation.

Connected lessons

• Trees and Heaps
• Data Structures
• Binary search trees: preserve order through every branch
• AVL trees: restore height balance after insertion
• Skip lists: randomized levels over an ordered bottom chain
• Projects
• Quizzes

Apply it: Project: own a maintenance index and work queue and Index and queue invariants.