TAOCP 6.2.3 Exercise 27
Let a 2-3 tree be defined as in Section 6.
Exercise 27. [M23] [M23] Estimate the maximum number of comparisons needed to search in a 2-3 tree with N internal nodes.
Verified: no
Solve time: 58s
Solution
Let a 2-3 tree be defined as in Section 6.2.3 for generalized balanced search trees in which each internal node has either two or three children, and all external nodes occur at the same level. Let the height be $h$, measured as the number of edges on a path from the root to an external node.
Each search proceeds level by level. At each internal node, the key comparisons determine which of the at most three subtrees is followed. A node with two children contains one key, so exactly one comparison is sufficient to decide the direction. A node with three children contains two keys $K_1 < K_2$, and the search requires first comparing with $K_1$, and then, if necessary, comparing with $K_2$, so at most two comparisons occur at that node.
Let $C$ denote the total number of key comparisons in a worst-case search. Along any root-to-leaf path, each visited internal node contributes at least one comparison and at most two comparisons, hence
$$ h \le C \le 2h. $$
To express $h$ in terms of $N$, consider extremal shapes of 2-3 trees of height $h$.
If every internal node has two children, the tree is a full binary tree, and the number of internal nodes satisfies
$$ N = 2^h - 1. $$
If every internal node has three children, the number of internal nodes satisfies
$$ N = 1 + 3 + 3^2 + \cdots + 3^{h-1} = \frac{3^h - 1}{2}. $$
For an arbitrary 2-3 tree of height $h$, monotonicity in branching degree implies
$$ 2^h - 1 \le N \le \frac{3^h - 1}{2}. $$
From $2^h - 1 \le N$, it follows that
$$ h \le \lg(N+1). $$
From $N \le \frac{3^h - 1}{2}$, it follows that
$$ 3^h \ge 2N + 1, $$
hence
$$ h \ge \log_3(2N+1). $$
Combining these inequalities with $h \le C \le 2h$ yields
$$ \log_3(2N+1) \le C \le 2\lg(N+1). $$
Thus the maximum number of comparisons required for a search in a 2-3 tree with $N$ internal nodes grows on the order of $\Theta(\lg N)$, with worst-case constant factor between $1$ and $2$ relative to the height bound and at most factor $2$ per level due to two-key nodes.
This completes the proof. ∎