Master Red-Black Trees with Illustrated Comics: From Basics to Insertion & Deletion

Red‑Black Tree Overview

A red‑black tree is a self‑balancing binary search tree that guarantees O(log n) time for search, insertion, and deletion. Its balancing is enforced by five invariants:

Each node is either red or black .

The root is black.

All leaves (nil children) are black.

Red nodes cannot have red children (no two consecutive reds).

Every simple path from a node to its descendant leaves contains the same number of black nodes.

These properties make red‑black trees suitable for high‑performance system components such as the Linux kernel’s memory and process management, Java’s TreeMap / TreeSet, and C++’s std::map / std::set.

Implementation Highlights

Core Operations

Both insertion and deletion may violate the red‑black properties, so each operation is followed by a fix‑up phase that restores balance. The fix‑up logic consists of a finite set of case analyses based on the colors of the current node, its parent, uncle, and sibling.

Insertion

The algorithm inserts the new node as in a regular binary search tree, colors it red, and then applies the following cases until the tree satisfies all invariants:

If the new node is the root, recolor it black.

If the parent is black, the tree is already valid.

If the parent and uncle are red, recolor parent and uncle black, grandparent red, and continue fixing from the grandparent.

If the parent is red but the uncle is black, perform appropriate rotations (left‑rotate or right‑rotate) and recolor to eliminate the red‑red conflict.

Deletion

Deletion removes a node similarly to a standard BST, then handles the “double‑black” situation that may arise when a black node is removed. The fix‑up proceeds through these cases:

If the removed node’s replacement is red, recolor it black.

If the sibling is red, rotate to make the sibling black and the parent red, then continue.

If the sibling and its children are black, recolor the sibling red and move the double‑black up to the parent.

If the sibling is black and at least one of its children is red, perform rotations and recolorings that transfer the extra blackness to the sibling’s red child, restoring all invariants.

Testing and Validation

The accompanying PDF provides complete source code for a binary search tree and a red‑black tree, each with an extensive test suite. The tests perform hundreds of thousands of random insertions and deletions, verifying after each operation that:

In‑order traversal yields a sorted sequence.

All red‑black properties hold.

Tree height remains bounded by 2 · log₂(n + 1).

These stress tests confirm the correctness and performance characteristics of the implementation.

Practical Usage

Developers can copy the provided code into their own IDEs, compile, and run the test harness to experiment with the data structure. The step‑by‑step case illustrations (presented as comic panels in the original material) serve as a visual aid for understanding the rotation and recoloring decisions required during insertion and deletion.