TAOCP 6.2.2 Exercise 32

Section 6.2.2: Binary Tree Searching

Exercise 32. ▶ [M25] Let $n + 1 = 2^m + k$, where $0 \le k \le 2^m$. There are exactly $\binom{m}{k}$ binary trees in which all external nodes appear on levels $m$ and $m + 1$. Show that, among all equal, the Fibonacci trees turn out to be optimum; see L. E. Stanfel, JACM 17 (1970), 508–517. On machines that cannot make three-way comparisons at once, a program for Algorithm T will have to make two comparisons in step T2, one for equality and one for less-than. B. Sheil and V. R. Pratt have observed that these comparisons need not involve the same key, and it may well be best to have a binary tree whose internal nodes specify either an equality test or a less-than test but not both. (This situation would be interesting to explore as an alternative to the stated problem.)

Verified: no
Solve time: 6m45s

Solution

1. Number of binary trees with all external nodes on levels (m) and (m+1)

An extended binary tree has internal nodes with exactly two children and external nodes (leaves) with no children. If the tree has (n) internal nodes, it has (n+1) external nodes. Suppose every external node lies on level (m) or level (m+1) (the root is at level 0). Then all positions on levels (0,1,\dots,m-1) must be occupied by internal nodes; otherwise an external node would appear on a level (< m). Level (m) contains exactly (2^m) potential positions. Each such position is either

• an internal node (which then has two external children on level (m+1)), or
• an external node (itself on level (m)).

Let (k) be the number of internal nodes on level (m). The number of external nodes on level (m) is (2^m - k), and on level (m+1) it is (2k). The total number of external nodes is therefore [ (2^m - k) + 2k = 2^m + k. ] Since this must equal (n+1), we have the unique representation [ n+1 = 2^m + k,\qquad 0 \le k \le 2^m. ] The tree is completely determined by choosing which (k) of the (2^m) positions on level (m) are internal. Hence the number of such trees is [ \boxed{\binom{2^m}{k}}. ] (Note: The exercise statement writes (\binom{m}{k}); the correct binomial coefficient is (\binom{2^m}{k}).)

2. Optimality of these trees for equal‑probability binary search trees

Consider a binary search tree with (n) distinct keys, each searched with probability (1/n). The average number of comparisons for a successful search is [ C = 1 + \frac{I(T)}{n}, ] where (I(T)) is the internal path length (sum of depths of internal nodes). Minimizing (C) is equivalent to minimizing (I(T)). For any extended binary tree, [ I(T) = E(T) - 2n, ] where (E(T)) is the external path length (sum of depths of external nodes). Thus minimizing (I(T)) is equivalent to minimizing (E(T)) among all extended binary trees with (n) internal nodes (i.e., with (N = n+1) external nodes).

Lemma. Among all extended binary trees with a given number (N) of external nodes, the minimum external path length is attained exactly when all external nodes lie on two adjacent levels.

Proof. Let (T) be a tree with (N) external nodes and minimal (E(T)). Suppose (T) has external nodes at depths differing by at least (2). Let (b) be the minimum depth of an external node and (a \ge b+2) the maximum depth. Let (x) be an external node at depth (b). Because (a \ge b+2), there exists an internal node at depth (a-1) whose two children are external nodes; call them (y) and (z) (both at depth (a)). Perform the following transformation:

• Replace the internal node at depth (a-1) by a single external node (y') (so (y') is at depth (a-1)).
• Replace (x) by an internal node with two external children (x_1, x_2) at depth (b+1).

The new tree has the same number of external nodes (we removed (x,y,z) and added (y',x_1,x_2)). Its external path length changes by [ -\bigl(b + a + a\bigr) + \bigl((a-1) + (b+1) + (b+1)\bigr) = b - a + 1 \le -1. ] This contradicts the minimality of (E(T)). Hence the maximum and minimum depths of external nodes differ by at most (1); i.e., all external nodes lie on two adjacent levels (m) and (m+1). Because the total number of external nodes is (N), the levels must satisfy (2^m \le N < 2^{m+1}). ∎

By the lemma, every optimal tree has all its external nodes on levels (m) and (m+1) with (N = n+1 = 2^m + k) ((0 \le k \le 2^m)). For any such tree, the number of external nodes on level (m) is (2^m - k) and on level (m+1) is (2k), giving an external path length [ E = m(2^m - k) + (m+1)(2k) = m2^m + 2k = 2n + 2 + (m-2)2^m, ] which is independent of (k). Therefore all (\binom{2^m}{k}) trees of this form have the same (minimal) external path length, and consequently the same minimal internal path length. They are precisely the optimal binary search trees for equal probabilities. This result is due to L. E. Stanfel, JACM 17 (1970), 508-517.

3. Remark on the two‑way comparison model

The final paragraph of the exercise refers to machines that cannot perform a three‑way comparison in one instruction. B. Sheil and V. R. Pratt observed that in this situation one may use a binary tree whose internal nodes are labeled either with an equality test or a less‑than test (but not both). For that model the optimal trees for equal probabilities have a different structure, known as Fibonacci trees, where the sizes of the left and right subtrees follow the Fibonacci recurrence. The analysis of that alternative model is a separate problem.

This completes the proof. ∎