The idea: one node, up to three keys
A 2-3-4 tree is a search tree whose nodes hold 1, 2 or 3 sorted keys. A node with 1 key has 2 children (a 2-node), with 2 keys 3 children (a 3-node), with 3 keys 4 children (a 4-node). Every leaf is on the same level, so the tree is always perfectly balanced: with n keys its height is at most log₂(n + 1).
![Top row: a 2-node [20] with children A and B, a 3-node [10 20] with children A, B, C, and a 4-node [10 20 30] with children A, B, C, D. Bottom row, the same nodes as red-black nodes: black 20; black 20 with a red left child 10; black 20 with red children 10 and 30. The children A to D hang in the same order](Images/twothreefourtree/node-kinds.svg)
The canvas draws the same keys twice: the 2-3-4 tree on top and the red-black tree it is equal to underneath. Each key stays in its own column in both panels. In a 2-3-4 node, the keys written in red are the ones that are red nodes below.
Top-down insert: split on the way down
Insert walks down from the root like a search. Whenever it meets a 4-node, it splits it first: the outer keys become two 2-nodes and the middle key moves up into the parent. The parent cannot be full, because the walk would have split it one level earlier. At the leaf there is always room, so the new key just goes in.
- A split never spreads upward. Each insert does at most one split per level, all on the way down.
- Only a split of the root makes the tree taller, and it adds a level at the top. All leaves move down together, so they stay on one level.
Demo: the first split (10, 20, 30, 40) fills the root to [10 20 30]. Then 40 arrives, the root splits, 20 becomes the new root over [10] and [30], and 40 joins [30]: 1 split, height 2. Demo: one insert, two splits inserts 68 and splits both the root [30 40 50] and the leaf [60 65 70] on the same walk down. Demo: ascending keys 5, 15 … 95 inserts keys in sorted order, which would make a plain binary search tree into a list. Here it ends with height 3 after 5 splits.
The red-black tree in disguise
Turn each 2-3-4 node into one black node and give it its other keys as red children. The result is a red-black tree, and every red-black tree can be read back as a 2-3-4 tree the same way. The red-black rules are the 2-3-4 shape, written for binary nodes:
| red-black rule | what it means in the 2-3-4 tree |
|---|---|
| a red node is a key sharing its black parent's node | a node holds up to 3 keys |
| no red node has a red child | no node holds more than 3 keys |
| every path down has the same number of black nodes | every leaf is on the same level |
| black height | 2-3-4 height |
| the root is black | the root is a whole node, not an extra key |
A 3-node can lean either way: its red key can be the left or the right child. The page keeps the key that arrived last as the red one, which is how a red-black insert leaves it. The checks under the canvas recount both rules after every step.
A split is a colour flip, sometimes with rotations
A 4-node is a black key with two red children. Splitting it is a colour flip: the middle key turns red (it now belongs to its parent's node) and the outer two turn black. If the parent was a 2-node, that is all. If the parent was a 3-node, the middle key can end up as a red child of a red node. The red-black tree then needs rotations to rebuild the 4-node with its black key in the middle:
| the key arrives in | red-black fix |
|---|---|
| a 2-node | none: it becomes a red child |
| a 3-node, on the black key's empty side | none: the black key gets a second red child |
| a 3-node, outside its red key | 1 rotation |
| a 3-node, between its two keys | 2 rotations |
| a new root (root split) | flip, then the root turns black: black height + 1 |
The same table holds for a new key added to a leaf. In Demo: the first split, 30 lands outside the red 20 under black 10, so the red-black tree needs 1 rotation. Demo: split under a 3-node (2 rotations) splits [35 40 45] under the 3-node [30 50], and 40 lands between 30 and 50.
![Left, before: 2-3-4 root [30 50] over [10 20], [35 40 45], [60 70]; the red-black tree has black 50 at the root, red 30 and black 70 below it, black 20 and black 40 under 30, red 10 under 20, red 35 and red 45 under 40, red 60 under 70. Right, after the split: root [30 40 50] over [10 20], [35], [45], [60 70]; the red-black tree has black 40 at the root with red 30 and red 50, black 20, 35, 45, 70 below, red 10 and red 60 at the bottom](Images/twothreefourtree/split-under-3-node.svg)
Height and search cost
A search in the 2-3-4 tree visits one node per level and compares with up to 3 keys in each. The red-black tree visits the same keys as single nodes, so it may visit up to twice as many: each black node on the path can bring one red node. Red-black height is at most 2 × the 2-3-4 height, which is why a red-black tree's height is at most 2 log₂(n + 1). In Demo: search, 2-3-4 path vs red-black path, finding 95 takes 3 2-3-4 nodes but 5 red-black nodes, 2 of them red. Demo: key already in the tree shows that insert stops when it finds the key.
A B-tree is the same idea with bigger nodes. A 2-3-4 tree is a B-tree of order 4, and the split here is the B-tree's "preemptive split". Disks and databases use hundreds of keys per node; see B-tree vs B+ tree. In memory, the red-black form wins because each node is small and binary. AVL vs red-black compares it with the stricter AVL balance.
What the page leaves out
Delete (top-down, it merges or borrows so that the walk never reaches a 2-node), bottom-up insert (split only when a leaf overflows, and pass the split upward), the left-leaning red-black tree, which allows only left-leaning 3-nodes, and duplicates. The page holds at most 16 keys so that each key keeps its own column.
See where this page fits on the Indexing mind map.