2-3 trees

What if a node could hold two keys, and split when a third arrives? Watch where the tree grows.

⋯42    if (n->nkeys == 1) {43        if (i == 0) {44            n->keys[1] = n->keys[0];45            n->child[2] = n->child[1];46            n->keys[0] = key;47            n->child[1] = extra;48        } else {49            n->keys[1] = key;50            n->child[2] = extra;51        }52        n->nkeys = 2;53        return false;54    }55    int k3[3];56    struct node23 *c4[4];57    for (int j = 0, a = 0; j < 3; j++)58        k3[j] = j == i ? key : n->keys[a++];59    for (int j = 0, a = 0; j < 4; j++)60        c4[j] = j == i + 1 ? extra : n->child[a++];61    n->nkeys = 1;62    n->keys[0] = k3[0];63    n->child[0] = c4[0];64    n->child[1] = c4[1];65    n->child[2] = NULL;66    *right = make_node(k3[2], c4[2], c4[3]);67    *up = k3[1];68    splits++;69    return true;70}⋯107    struct node23 *root = NULL;108    for (int k = 10; k <= 70; k += 10)109        root = insert(root, k);110    print_inorder(root);

One key or two, and a split

A binary search tree makes one choice at each node: left or right. A 2-3 tree allows a node to hold one key or two:

• a 2-node has one key and two children, smaller keys on the left and larger on the right;
• a 3-node has two keys and three children: smaller than both, between them, and larger than both.

A search compares the key with the one or two keys in a node, picks the child, and goes down, as in Binary search trees.

The difference is in insertion. A new key always goes into the leaf where its search ends. If the leaf has one key, it now has two, and that is all. If it already had two, it would hold three, which is not allowed, so it splits: the smallest key stays, the largest goes to a new node, and the middle key goes up into the parent. The parent may then hold three and split in turn. If the root splits, its middle key becomes a new root.

Follow the clip. 10 and 20 share a leaf. 30 makes it 10 20 30: it splits, and 20 goes up into a new root over 10 and 30. At 70 a split goes up twice: the leaf 50 60 70 splits and sends 60 up, the root becomes 20 40 60 and splits too, and 40 becomes the new root.

Sorted keys made a plain search tree into a chain of height 6. Here they make a tree of height 2.

The code and its cost

The node

The full program, tree23.c, stores a node as:

struct node23 {
    int nkeys;
    int keys[2];
    struct node23 *child[3];
};

nkeys is 1 or 2. A 2-node uses keys[0] and child[0] and child[1]; a 3-node uses both keys and all three children. A leaf’s children are NULL. The struct is 40 bytes: nkeys at offset 0, the two keys at 4 and 8, 4 bytes of padding so that the pointers start at 16, and the three child pointers at 16, 24 and 32.

Inserting: down, then back up

insert_rec(n, key, &up, &right) puts key somewhere below n. It returns false if everything fitted, or true if n itself split, and then it hands back the middle key through up and the new right node through right, because the caller must place them.

It first finds i, the place of the new key among the node’s keys:

int i = 0;
while (i < n->nkeys && key > n->keys[i])
    i++;

If n is not a leaf, it calls itself on child[i]. If that call returns false, there is nothing more to do. If it returns true, the child split, and n must now take the key that came up, with the new node as the child to its right.

Taking a key into a node with room is a few assignments: with i == 0 the old key moves to place 1 and the new one goes in front; otherwise the new key goes in place 1. nkeys becomes 2.

Splitting

A node that already has two keys gathers all three keys in order, and all four children, into small arrays:

int k3[3];
struct node23 *c4[4];
for (int j = 0, a = 0; j < 3; j++)
    k3[j] = j == i ? key : n->keys[a++];
for (int j = 0, a = 0; j < 4; j++)
    c4[j] = j == i + 1 ? extra : n->child[a++];

j == i ? key : n->keys[a++] reads: if this is the new key’s place, use the new key; otherwise take the next of the node’s own keys and move a on. So k3 holds the three keys in order. The children work the same way, with the new node at place i + 1, just right of the new key.

Then the node keeps k3[0] with c4[0] and c4[1], a new node gets k3[2] with c4[2] and c4[3], and k3[1] goes up through *up. If the split reaches the root, insert makes a new root holding that middle key, over the old root and the new node: the tree is one level taller.

What it costs

Every leaf is at the same depth, so the height is set by how many keys fit. A tree of height h has h + 1 levels. With only 2-nodes, it has 2^(h+1) − 1 nodes holding as many keys; with only 3-nodes, 3^(h+1) − 1 keys. So for n keys

A search, or an insertion with all its splits, visits one node per level, with one or two comparisons each: a number of steps proportional to log n, whatever order the keys arrive in.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic tree23.c -o tree23
./tree23

It prints the keys in order, 10 20 30 40 50 60 70, then height 2, 4 splits.

Worked example

Insert 25 into the final tree. The search goes left of 40, right of 20, and ends at the leaf 30, which has one key: it becomes 25 30. No split.

Then insert 27. The search ends at the leaf 25 30, which would hold 25 27 30. It splits: 25 stays, 30 goes to a new leaf, and 27 goes up into 20, which had room and becomes 20 27. One split, and the height is still 2.

The height of 7 keys. At most log₂ 8 − 1 = 2, and at least log₃ 8 − 1 ≈ 0.89, so at least 1. The clip’s tree has height 2, but the same seven keys could also form a tree of height 1: a root 30 60 over the leaves 10 20, 40 50 and 70.

Two checks. How many keys can a 2-3 tree of height 1 hold? (3 to 8: a root with one key over two leaves with one key each, up to a root with two keys over three leaves with two each.) When does the height grow? (Only when the root splits.)

Where it’s used

As a model. 2-3 trees are seldom used as they stand: nodes of two shapes make the code longer than it needs to be. Their idea lives on in two forms that are used everywhere.

Red–black trees. A binary tree that colours some links red to stand for 3-nodes; it is how many libraries store ordered maps (Red–black trees).

B-trees. The same splitting with hundreds of keys per node, sized to a disk block; databases and file systems use them (B-trees).

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.