2-3 and 2-3-4 Trees

The previous lesson repaired balance with rotations: the tree breaks, then is fixed. This lesson’s approach is different — the tree never breaks, because the way it grows preserves balance by definition.

The idea is to give up the binary constraint: a node can carry more than one key.

Two Node Types

A 2-3 tree has two kinds of nodes:

• 2-node: One key, two children. The left subtree carries smaller values, the right carries larger ones — an ordinary search tree node.
• 3-node: Two keys, three children. The left subtree carries values smaller than the first key, the middle subtree carries values between the two keys, and the right subtree carries values larger than the second key.

        [7 | 12]            ← 3-node: two keys, three children
       /    |    \
    [3]   [10]  [25 | 30]

The structure’s defining rule is this: all leaves are at the same depth. This is not a property arranged afterward; it is a direct consequence of the insertion method.

Search

Search resembles that of a binary tree; the only difference is comparing against more than one key within a node. If the key is found in the node, search ends; if not, it descends into the corresponding child based on which range the value falls into.

The number of comparisons within a node is at most two, that is, constant. The cost is again proportional to height.

Insertion: Growth from the Bottom Up

Insertion always happens at a leaf. There are three cases:

If the leaf is a 2-node, the key is added and the node becomes a 3-node. The tree’s shape does not change.

If the leaf is a 3-node, a node with three keys is temporarily formed. This node is split: the middle key is promoted to the node above, and the remaining two keys become two separate 2-nodes.

If the promoted key overflows the node above it as well, the same split repeats one level up. Splitting can continue all the way to the root; if the root splits, a new root is formed and the tree’s height increases by one.

This last point is the source of the structure’s balance guarantee. The tree grows from the root, not from the leaves; all leaves descend one level at the same time, so a depth difference never arises.

class Node23:
    """2-3 tree node: one or two keys; zero, two, or three children."""

    def __init__(self, keys: list[int], children: list | None = None) -> None:
        self.keys = keys
        self.children = children or []

    def is_leaf(self) -> bool:
        return not self.children


def _insert(node: Node23, value: int):
    """Returns (node, promoted); promoted = (key, left, right) or None."""
    if node.is_leaf():
        keys = sorted(node.keys + [value])
        if len(keys) <= 2:
            return Node23(keys), None            # 2-node → 3-node
        middle = keys[1]                            # overflowed: promote the middle
        return None, (middle, Node23([keys[0]]), Node23([keys[2]]))

    i = 0
    while i < len(node.keys) and value > node.keys[i]:
        i += 1
    child, promoted = _insert(node.children[i], value)
    if promoted is None:
        node.children[i] = child
        return node, None

    key, left, right = promoted                           # a key came up from below
    keys = node.keys[:i] + [key] + node.keys[i:]
    children = node.children[:i] + [left, right] + node.children[i + 1:]
    if len(keys) <= 2:
        return Node23(keys, children), None
    middle = keys[1]                                # this node overflowed too
    return None, (middle,
                  Node23([keys[0]], children[:2]),
                  Node23([keys[2]], children[2:]))


def insert(root: Node23 | None, value: int) -> Node23:
    if root is None:
        return Node23([value])
    node, promoted = _insert(root, value)
    if promoted is None:
        return node
    key, left, right = promoted
    return Node23([key], [left, right])               # root split: height increased


def levels(root: Node23) -> list[list[list[int]]]:
    """Shows the tree level by level, as lists of node key lists."""
    result, row = [], [root]
    while row:
        result.append([d.keys for d in row])
        next_row = []
        for d in row:
            next_row.extend(d.children)
        row = next_row
    return result


root = None
for value in (3, 7, 10, 12, 25, 30):          # sorted insertion
    root = insert(root, value)
    print(value, "->", levels(root))

# 3  -> [[[3]]]
# 7  -> [[[3, 7]]]
# 10 -> [[[7]], [[3], [10]]]
# 12 -> [[[7]], [[3], [10, 12]]]
# 25 -> [[[7, 12]], [[3], [10], [25]]]
# 30 -> [[[7, 12]], [[3], [10], [25, 30]]]

The output shows step by step how the growth proceeds. On the third insertion the root overflows, splits, and the tree rises to two levels. On the fifth insertion a leaf overflows; the middle key is promoted to the root, and the root becomes a 3-node.

What stands out is that the input is sorted. The same order produced a chain of height five in a plain binary search tree; here the height is one.

2-3-4 Trees

Extending the same idea one step further gives a 2-3-4 tree: nodes can carry one, two, or three keys. The split threshold rises to four keys; the rule is the same.

The added flexibility makes splits rarer. In exchange, the number of comparisons within a node increases and the node structure grows.

Correspondence with Red–Black Trees

There is a one-to-one correspondence between 2-3-4 trees and the red–black trees from the previous lesson: a 2-3-4 tree can be converted into a red–black tree by expanding its nodes into a binary structure.

The correspondence is built as follows: a 2-node is a black node; a 3-node is a black node with a red child attached to it; a 4-node is a black node with two red children. Red links mean “actually part of the same node.”

This correspondence explains the origin of the red–black rules. Forbidding two consecutive red nodes is the same as a node not carrying more than three keys. The equal black count on every path is the same as all leaves being at the same depth.

In other words, the two structures are two representations of the same idea: one holds multiple keys per node, the other encodes the same information with colors in a binary tree. The binary representation is preferred in implementation because it keeps the node structure fixed.

Height Bound

Since all leaves are at the same depth, height is computed directly. Given that every node carries at least two and at most three children:

$$\log_3 n \leq h \leq \log_2 n$$

It is logarithmic at both ends; search, insertion, and deletion are $O(\log n)$. Deletion is the mirror image of insertion: if a node is left with no keys, it borrows from a sibling; if the sibling cannot give one either, the two nodes are merged and the deficit is carried up a level.

The point to note in deletion is that the deficit, too, can propagate toward the root: if the chain of merges reaches the root, the root is replaced by its single child and the tree’s height decreases by one. Just like growth, shrinkage happens only at the root; for this reason balance is never broken.

Summary

• In a 2-3 tree, nodes carry one or two keys; a 2-node has two children, a 3-node has three.
• All leaves are at the same depth, and this is a direct consequence of the insertion method.
• An overflowing node is split and the middle key is promoted to the node above; when the root splits, the height increases by one.
• Because the tree grows from the root rather than the leaves, imbalance never arises; even sorted input does not produce a degenerate tree.
• A 2-3-4 tree is the same idea extended to three keys, and it maps one-to-one onto a red–black tree.
• Height lies between $\log_3 n$ and $\log_2 n$; all operations are logarithmic.

Next Step

Raising the number of keys per node from two to three made the tree shallower. What happens if that number is raised into the hundreds? This question becomes critical when data resides on disk rather than in memory. The next lesson takes up B-trees, designed around block-based storage.