Understanding Red-Black Tree Insertion Operations

In 2017 the author published a brief comic about red‑black trees; now a more thorough two‑part summary is presented to help readers completely understand this important data structure.

Binary Search Tree (BST) characteristics are reviewed: left subtree values ≤ root, right subtree values ≥ root, and both subtrees are themselves BSTs. An example BST with root 9, left child 8, and right child 12 is shown.

Insertion of nodes 7, 6, 5, 4, 3 into the BST is illustrated, demonstrating how the tree evolves.

Red‑black tree rules are listed: (1) each node is red or black, (2) root is black, (3) all leaves (NIL) are black, (4) red nodes cannot have red children, (5) every path from a node to its descendant leaves contains the same number of black nodes. A typical red‑black tree diagram is provided.

Two insertion examples are examined: inserting 14 (parent 15 is black – no violation) and inserting 21 (parent 22 is red – violates rule 4). The need for adjustments is explained.

Color‑change (recoloring) is described: turning a red node black or vice‑versa to restore properties, noting that a single recolor may affect black‑height and require further fixes.

Left rotation (counter‑clockwise) is defined: the right child replaces its parent, which becomes the left child of the new parent. A diagram illustrates the transformation.

Right rotation (clockwise) is defined: the left child replaces its parent, which becomes the right child of the new parent. Diagrams illustrate the process.

The five insertion cases are detailed:

New node is the root – simply color it black.

Parent is black – no violation.

Parent and uncle are red – recolor parent and uncle black, grandparent red, then possibly recurse.

Parent red, uncle black (or nil), new node is right child of left‑hand parent – perform left rotation on parent, then proceed to case 5.

Parent red, uncle black (or nil), new node is left child of left‑hand parent – perform right rotation on grandparent, then recolor.

Each case is illustrated with images showing the tree before and after rotations and recoloring.

Finally, a concrete example inserting node 21 into a given red‑black tree is walked through, showing how the situation matches case 3, followed by recoloring steps, then case 5 (mirror) with a left rotation around node 13, and final recoloring to restore all red‑black properties.

The article concludes that after these adjustments the red‑black tree again satisfies all balancing rules.