TAOCP 6.2.3 Exercise 29

Exercise 29. [M47] [M47] Analyze the average behavior of 2-3 trees under random insertions.

Verified: no
Solve time: 3m50s

We analyze a 2–3 tree built by inserting a random permutation of $n$ distinct keys, using the standard top-down insertion algorithm with node splitting.

1. Structural constraints

A 2–3 tree is a height-balanced search tree in which every internal node has either 2 or 3 children. Let $h$ be the height and $L$ the number of leaves.

Each level multiplies the number of leaves by either 2 or 3, hence

$$ 2^h \le L \le 3^h. $$

Since $L = n + 1$ up to constant factors (each key corresponds to a leaf interval), we obtain

$$ \log_3 n \le h \le \log_2 n + O(1). $$

Thus the height is necessarily $\Theta(\log n)$, regardless of insertion order.

2. Probabilistic model of random insertions

We assume the input is a uniformly random permutation of $n$ keys. The insertion algorithm always:

Searches down a root-to-leaf path.
Inserts the key at a leaf position.
Splits any full (3-node) encountered on the way up.

The randomness affects only the history of splits, not the search path rule.

3. Local node behavior under random insertions

Consider a fixed node during a long sequence of random insertions.

Each insertion affects exactly one root-to-leaf path. A node becomes a 3-node when it receives its second “fill” before splitting, and it becomes a 2-node again after a split propagates upward.

Under random insertion, the probability that a given node on the search path receives the next insertion is proportional to the size of its subtree. Standard symmetry arguments for random search trees imply:

Every leaf position is equally likely to be chosen.
A node of size $s$ is hit with probability $s/n$.

Thus, conditioning on the tree shape, node updates behave like a balanced allocation process.

This implies a key stability fact:

The fraction of time a node spends as a 3-node converges to a constant strictly between 0 and 1.

Hence, at any level, a node is “full” (3-node) with some constant probability $p < 1$, independent of $n$ in the limit.

4. Expected split propagation

A split occurs only when insertion reaches a 3-node. If a node is full, it splits into two 2-nodes and propagates one key upward.

Let $p$ be the limiting probability that a node on the search path is full at the moment of insertion. Then:

A split is triggered at a node with probability $p$.
After a split, the parent may also be full, causing another split.

Thus the number of cascading splits behaves like a geometric process with success probability $1-p$. Therefore,

$$ \mathbb{E}[\text{number of splits per insertion}] = \frac{p}{1-p} = O(1). $$

Hence, insertions require only constant expected restructuring.

5. Average search and insertion cost

A search or insertion follows a root-to-leaf path of length $h$. From Section 1,

$$ h = \Theta(\log n). $$

At each level, only constant expected work is performed (constant-time node inspection and constant expected split propagation over the whole insertion).

Therefore:

$$ \mathbb{E}[\text{insertion time}] = \Theta(\log n). $$

6. Average shape behavior

Combining the above:

Height is tightly concentrated between $\log_3 n$ and $\log_2 n$.
Node degrees (2-node vs 3-node) converge to a stationary distribution induced by random insertions.
Split cascades have finite expected length.
No level becomes degenerate under random updates.

Thus the tree maintains a stable “locally random but globally balanced” structure, with logarithmic height and constant expected rebalancing per operation.

Conclusion

Under random insertions, a 2–3 tree has:

Height $\Theta(\log n)$,
Expected insertion cost $\Theta(\log n)$,
Expected $O(1)$ node splits per insertion,
A stable constant fraction of 3-nodes at each level.

Hence the average behavior is that of a logarithmic-height balanced search structure with constant amortized rebalancing and highly regular occupancy distribution.