Master Red-Black Trees: Visual Guide to Balancing Binary Search Trees

Binary Search Tree

Binary Search Tree (BST) is a tree where each node's left subtree contains only values smaller than the node and the right subtree contains only values larger than the node, and both subtrees are themselves BSTs.

All values in the left subtree are less than the node.

All values in the right subtree are greater than the node.

Both left and right subtrees must also be BSTs.

These properties are easily understood with the following diagram:

Another example that still satisfies the three constraints is shown below:

From a programming perspective, an unbalanced tree can lead to a search time of O(h), where h may grow arbitrarily.

Red-Black Tree

Red-Black Tree (RBT) is a self‑balancing binary search tree that follows four rules:

Each node is either red or black.

The root is always black.

No two consecutive red nodes are allowed (a red node cannot have a red parent or red child).

Every path from a node (including the root) to its descendant NULL leaves contains the same number of black nodes.

Understanding these rules is similar to learning a Rubik's Cube: practice the steps repeatedly.

The two fundamental operations for maintaining balance are recolor and rotation .

When inserting a new node X, the algorithm proceeds as follows:

1. Color the new node red.

2. If X is the root, recolor it black.

3. If X’s parent is red, handle two cases based on the color of X’s uncle:

Left‑Left (LL) Case

Imagine pulling the parent node up like a rope and recoloring.

Left‑Right (LR) Case

Perform a left rotation to transform the situation into an LL case.

Right‑Right (RR) Case

Similar to LL, visualize it as pulling a rope.

Right‑Left (RL) Case

Perform a right rotation to convert the situation into an RR case.

Insert 10, 20, 30, 15 into an empty tree:

Insert 10 as the root and color it black.

Insert 20 as the right child of 10 and color it red.

Insert 30 as the right child of 20 (both 20 and 30 are red), triggering the RR case; rotate left at 20, making 20 the new root and recolor it black.

Insert 15 as the left child of 20, color it red. Its uncle (30) is red, so recolor 10 and 30 black, recolor 15 and its grandparent 20 red, then recolor the root 20 black.

Each subsequent insertion repeats these steps, and practicing with the animated illustrations solidifies understanding of red‑black tree transformations.