Equivalence of Red-Black and 2-3-4 Trees

The Isomorphism

Every 2-3-4 tree can be converted to a red-black tree, and every red-black tree can be converted back to a 2-3-4 tree. The two structures are isomorphic: operations on one translate directly to operations on the other, preserving correctness and asymptotic bounds.

Mapping 2-3-4 Nodes to Red-Black Clusters

Each node type in a 2-3-4 tree maps to a small cluster of red-black nodes:

2-Node (1 key, 2 children) → Single Black Node

A 2-node has one key and two children. Its red-black representation is a single black node. The children of the black node are the representations of the 2-node’s subtrees.

3-Node (2 keys, 3 children) → Black + One Red Child

A 3-node has two keys, $k_1 < k_2$, and three children. There are two possible red-black representations (left- and right-handed isomers):

• Right-handed: black node with key $k_2$, left red child with key $k_1$. Children: leftmost subtree under red node, middle under black node’s left, rightmost under black node’s right.
• Left-handed: black node with key $k_1$, right red child with key $k_2$. Children arranged symmetrically.

4-Node (3 keys, 4 children) → Black + Two Red Children

A 4-node has three keys, $k_1 < k_2 < k_3$, and four children. The red-black representation: black node with key $k_2$, left red child with key $k_1$, right red child with key $k_3$. The four children map to the subtrees of the red and black nodes in order.

Black-Height as 2-3-4 Height

The black-height of a red-black tree equals the height of the corresponding 2-3-4 tree. This follows directly from the mapping: each level in the 2-3-4 tree contributes exactly one black node (the “anchor” of the cluster). Red nodes are “glued” to their black parent and do not increase the 2-3-4 tree height.

This explains why the red-black tree height is at most $2h_{2-3-4} + 1$ (or roughly $2h$): in the worst case, every 2-3-4 node is a 3-node represented as a black node with a red child at the deepest level, doubling the path length compared to black-height.

Translating Operations

Insert

Inserting into a 2-3-4 tree: find leaf, insert key, split 4-nodes that overflow. Translating to red-black:

• Inserting a key into a 2-node (black node) → colour new node red. If parent is black, done. (Case 0)
• Inserting into a 3-node → new red node may create two consecutive reds. Resolving this is a rotation (Case 2 or 3).
• Inserting into a 4-node (black+two red children) → the 4-node is full. Splitting it in 2-3-4 terms corresponds to colour-flipping: the black parent becomes red, and both red children become black. This is exactly Case 1 of the RBT fix-up.

Splitting a 4-Node = Colour Flipping

When a 2-3-4 tree splits a 4-node, the middle key is promoted to the parent, and the node becomes two 2-nodes. In red-black terms:

• Before: black node $k_2$ with red children $k_1$ (left) and $k_3$ (right).
• After: $k_2$ becomes red (promoted into parent’s cluster), $k_1$ and $k_3$ become black (each becomes an independent 2-node).

This colour flip may create a red-red violation at the parent level, which is then resolved by Cases 2/3 or further Case 1 flips.

Merging in Deletion

When a 2-3-4 tree merges nodes during deletion (stealing the separator key from the parent), the corresponding red-black operation involves recolouring and rotations that redistribute “blackness” to fix double-black violations.

Why the Equivalence Matters

1. Correctness: Proving RBT operations correct is done by showing they maintain the mapping to a valid 2-3-4 tree. The 2-3-4 tree’s perfect height balance guarantees the RBT’s logarithmic height.
2. Intuition: The colour rules feel arbitrary until you see they encode 2-3-4 structure. “No two consecutive reds” means “no 2-3-4 node has more than 3 keys.” “Equal black-height” means “all 2-3-4 leaves are at the same depth.”
3. Implementation: An RBT can be debugged by checking whether it maps to a valid 2-3-4 tree. This is a perfectly satisfactory correctness test.

Summary

2-3-4 Node	Red-Black Cluster	Keys
2-node	Single black node	1
3-node	Black + 1 red child	2
4-node	Black + 2 red children	3
2-3-4 height $h$	RBT black-height = $h$
4-node split	Colour flip (Case 1)
Insert into 3-node	Rotation (Cases 2/3)
RBT height bound	$h \le 2\log(n+1)$	From 2-3-4 balance