Understanding Red‑Black Tree Insertion Cases and Rotations

In 2017 the author published a comic about red‑black trees; this article revisits the topic with a detailed two‑part written tutorial.

It begins by reviewing binary search tree (BST) properties, explaining that all keys in the left subtree are less than or equal to the root and all keys in the right subtree are greater than or equal to the root, and that each subtree is itself a BST. Example searches for the value 10 are illustrated with several diagrams.

The article then introduces the five red‑black tree rules: (1) each node is red or black, (2) the root is black, (3) all NIL leaves are black, (4) red nodes have black children, and (5) every path from a node to its descendant leaves contains the same number of black nodes.

Insertion scenarios are then examined. When a new node is added, the article explains how to detect violations of the rules and how to restore correctness using recoloring and rotations. Five typical cases are described, each with step‑by‑step diagrams.

Case 1: the new node becomes the root; it is recolored black and the tree remains valid.

Case 2: the parent is black, so no adjustment is needed.

Case 3: both the parent and the uncle are red; recoloring the parent to black and the grandparent to red resolves the violation, but may propagate the problem upward.

Case 4: the parent is red, the uncle is black (or absent), and the new node is a right child of a left‑handed parent; a left rotation around the parent is performed.

Case 5: the mirror of case 4 (new node is a left child of a right‑handed parent); a right rotation around the parent restores balance.

The article concludes with a concrete example: inserting the value 21 into a given red‑black tree. The insertion initially creates a red‑red conflict (node 21 under red parent 22). The situation matches case 3, so recoloring and a left rotation around node 13 are applied, followed by final recolorings to obtain a valid red‑black tree.

Through these explanations and illustrations, readers gain a thorough understanding of how red‑black tree insertion works, how to identify rule violations, and how to apply recoloring and rotations to maintain balanced search tree properties.