Understanding Red-Black Trees: Definitions, Construction, and Complexity

1. Definition of Red‑Black Trees

Red‑black trees are self‑balancing binary search trees used in associative arrays and dictionaries; Java's TreeMap and TreeSet are built on them. Their five properties are:

Each node is either red or black.

The root is black.

All leaves (nil nodes) are black.

If a node is red, both its children are black.

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

These rules ensure logarithmic height.

2. Why Balanced Binary Search Trees Matter

Inserting the array [42, 37, 18, 12, 11, 6, 5] as a plain binary search tree (BST) with 42 as the root creates a degenerate linked‑list structure, giving O(n) search time. A balanced BST (e.g., AVL or red‑black) guarantees O(log n) search.

Balanced BSTs were first formalized as AVL trees (Adelson‑Velsky and Landis, 1962).

3. 2‑3 Trees and Their Connection to Red‑Black Trees

2‑3 trees store one or two keys per node and have two or three children. They are height‑balanced, and each 2‑3 tree can be transformed into an equivalent red‑black tree:

2‑node ↔ black node.

3‑node is split into a black parent with a red left child.

The conversion keeps the tree balanced because red nodes always appear as left children.

4. Red‑Black Tree Properties Re‑examined

After conversion, the five red‑black properties hold naturally:

Node colors are defined by the conversion.

The root becomes black because the corresponding 2‑3 root is black.

Leaves are the external nil nodes, which are black.

Red nodes originate from split 3‑nodes, whose children are black 2‑nodes.

Black‑height equality follows from the balanced nature of the original 2‑3 tree.

Search complexity remains O(log n); the worst‑case path length is at most twice that of an AVL tree, but constant factors are ignored in asymptotic analysis.

5. Building a Red‑Black Tree Directly

To insert without first building a 2‑3 tree, we use four operations derived from 2‑3 tree insertion rules:

Keep the root black.

Left rotation.

Right rotation.

Color flip.

Insertion always adds a red node. If the new node violates a property, we apply the appropriate operation:

function leftRotate(node) {
  node.right = target.left;
  target.left = node;
  target.color = node.color;
  node.color = RED;
}

function rightRotate(node) {
  node.left = T1;
  target.right = node;
  target.color = node.color;
  node.color = RED;
}

function flipColors(node) {
  node.color = RED;
  node.left.color = BLACK;
  node.right.color = BLACK;
}

function add(node) {
  if (isRed(node.right) && !isRed(node.left)) node = leftRotate(node);
  if (isRed(node.left) && isRed(node.left.left)) node = rightRotate(node);
  if (isRed(node.left) && isRed(node.right)) flipColors(node);
}

These steps maintain balance and the red‑black invariants during successive insertions.