2-3-4 Trees

Definition

A 2-3-4 tree is a B-tree with minimum degree $t = 2$. Every internal node (except possibly the root) has 2, 3, or 4 children, holding 1, 2, or 3 keys respectively. Leaves are keyless and all at the same depth.

The name derives from the number of children: a 2-node has 1 key and 2 children; a 3-node has 2 keys and 3 children; a 4-node has 3 keys and 4 children.

Why Study 2-3-4 Trees?

All B-tree properties hold: $t-1 = 1$ minimum key per non-root node, $2t-1 = 3$ maximum keys per node. The height is $\le \log_2((n+1)/2)$, so all operations are $O(\log n)$.

2-3-4 trees are the conceptual bridge to red-black trees. Every 2-3-4 tree can be mapped to a red-black tree and vice versa (see “Equivalence of Red-Black and 2-3-4 Trees”). Understanding 2-3-4 operations provides intuition for red-black tree rebalancing.

Insertion

Insertion into a 2-3-4 tree follows the B-tree pattern with $t=2$:

1. Walk down from the root to find the appropriate leaf position.
2. If the destination leaf has room (1 or 2 keys), insert directly.
3. If the destination leaf is a 4-node (3 keys, full), split it: the middle key (the median) is promoted to the parent, and the remaining keys form two 2-nodes as children of the promoted key.

Splitting can cascade upward. When the root itself is a 4-node and splits, a new root is created, increasing the tree height by 1 while maintaining perfect balance.

Example: Inserting into a 2-3-4 Tree

Starting with a root containing [D,G] (a 3-node). Insert A:

• A < D, go left. The left child is a leaf. Insert A there: the leaf becomes [A,B] (if B was there) or just [A].

Insert E into a leaf that already has 3 keys [B,D,E] (a 4-node): split by promoting D to the parent and creating left leaf [B] and right leaf [E].

Deletion

Deletion follows the general B-tree delete algorithm with $t=2$:

• If the key is in a leaf with $> 1$ keys: simple removal.
• If in an internal node: swap with predecessor (or successor), then delete from leaf.
• If the target leaf is a 2-node (minimum size, $t-1 = 1$ key):
  • Rotate (redistribute): borrow a key from a sibling that has $> 1$ keys. The sibling’s key moves via the parent; the parent’s separator key moves down.
  • Merge: if both siblings are also 2-nodes, merge this node with a sibling by pulling the parent’s separator key down. The merged node has 3 keys (from $1+1+1$). This may leave the parent too small, cascading upward.

The Red-Black Connection

The 2-3-4 tree maps directly to a red-black tree:

• A 2-node (1 key, 2 children) → a single black node.
• A 3-node (2 keys, 3 children) → a black node with one red child.
• A 4-node (3 keys, 4 children) → a black node with two red children.

This mapping is an isomorphism: operations on one structure correspond exactly to operations on the other. The height of a red-black tree is at most twice the height of its corresponding 2-3-4 tree, hence $O(\log n)$.

Summary

Property	2-3-4 Tree
Type	B-tree with $t=2$
Children per node	2, 3, or 4
Keys per node	1, 2, or 3
Height	$\le \log_2((n+1)/2)$
Insert	Split 4-nodes on overflow
Delete	Rotate or merge 2-nodes
Map to red-black	2-node→black, 3-node→black+red child, 4-node→black+2 red children