TAOCP 6.3 Exercise 37

Let $b_j$ be the number of external nodes at level $j$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.3: Digital Searching

Exercise 37. [M22] [M22] Consider a binary tree with b; external nodes on level J. The text observes that the running time for unsuccessful searching in digital search trees is not directly related to the external path length 5~*/b;, but instead it is essentially proportional to the modified external path length S1b:2'. Prove or disprove: The smallest modified external path length, over all trees with N external nodes, occurs when all of the external nodes appear on at most two adjacent levels. (See exercise 5.3.1, 20.)

Verified: no
Solve time: 5m53s

Let $b_j$ be the number of external nodes at level $j$. A binary prefix tree with $N$ external nodes satisfies the two standard constraints

$$ \sum_j b_j = N, \qquad \sum_j b_j 2^{-j} = 1, \qquad b_j \ge 0, $$

and its modified external path length is

$$ S = \sum_j b_j 2^j. $$

We prove that among all such trees with fixed $N$, the minimum of $S$ is attained when all external nodes lie on at most two adjacent levels.

1. Reformulation

Set

$$ x_j = b_j 2^{-j}. $$

Then $x_j \ge 0$ and the Kraft constraint becomes

$$ \sum_j x_j = 1. $$

We rewrite the remaining quantities:

$$ N = \sum_j b_j = \sum_j x_j 2^j, $$

$$ S = \sum_j b_j 2^j = \sum_j x_j 4^j. $$

Thus we have a linear program in the variables $x_j$:

$$ \sum_j x_j = 1, \qquad \sum_j x_j 2^j = N, \qquad x_j \ge 0, $$

and we minimize the linear objective

$$ S = \sum_j x_j 4^j. $$

This is a finite-dimensional linear program (only finitely many levels $j$ can have $x_j>0$).

2. Extreme-point structure

The feasible region is the intersection of the simplex $\sum x_j = 1$ with one additional linear constraint $\sum x_j 2^j = N$. Hence it is a polytope in which all extreme points have support on at most two indices.

Indeed, if three distinct indices $i<j<k$ had $x_i,x_j,x_k>0$, then the two linear constraints would leave a nontrivial feasible direction in this 3-variable subsystem, contradicting extremality. Hence every extreme point has the form

$$ x_i = \alpha,\quad x_k = 1-\alpha,\quad x_j=0 \ (j\ne i,k). $$

Since the objective is linear, an optimal solution occurs at an extreme point. Therefore, there exists an optimal solution supported on at most two levels $i<k$.

Translating back,

$$ b_i = \alpha 2^i,\qquad b_k = (1-\alpha)2^k, $$

so every optimal tree may be assumed to have external nodes on at most two levels.

It remains to show these two levels must be adjacent.

3. Two-level feasibility conditions

Assume all external nodes lie on levels $i<k$. Let $b_i=a$, $b_k=N-a$. The constraints give

$$ a + (N-a) = N, $$

$$ a2^{-i} + (N-a)2^{-k} = 1. $$

Solving,

$$ a = \frac{1 - N2^{-k}}{2^{-i} - 2^{-k}}. $$

For this to define a valid tree we require $0 \le a \le N$. These inequalities impose:

(i) Lower bound on $N$

$$ a \ge 0 ;\Rightarrow; 1 - N2^{-k} \ge 0 ;\Rightarrow; N \le 2^k. $$

$$ a \le N ;\Rightarrow; 1 \le N2^{-i} ;\Rightarrow; N \ge 2^i. $$

Hence any feasible two-level configuration must satisfy

$$ 2^i \le N \le 2^k. $$

This point is crucial: the bound $N \ge 2^i$ is not true for arbitrary trees, but it is forced here by the requirement that a two-level solution exists.

4. Objective value for two levels

Substituting into $S = a2^i + (N-a)2^k$ yields

$$ S(i,k) = N(2^i + 2^k) - 2^{i+k}. $$

5. Optimal spacing of the two levels

Fix $i$. We compare $k$ and $k-1$, both assumed feasible.

$$ S(i,k) - S(i,k-1) = N(2^k - 2^{k-1}) - (2^{i+k} - 2^{i+k-1}) $$

$$ = N2^{k-1} - 2^{i+k-1} = 2^{k-1}(N - 2^i). $$

From feasibility of the two-level solution we already proved

$$ N \ge 2^i. $$

Hence

$$ S(i,k) - S(i,k-1) \ge 0, $$

with strict inequality unless $N=2^i$.

Therefore, for fixed $i$, decreasing $k$ always decreases (or preserves) the objective, as long as feasibility holds. The smallest possible $k$ is $k=i+1$.

6. Conclusion

We have shown:

  1. An optimal solution exists with support on at most two levels.
  2. Any feasible two-level solution must satisfy $2^i \le N \le 2^k$.
  3. For fixed lower level $i$, the objective is minimized by the smallest feasible upper level $k$.
  4. Hence $k=i+1$.

Therefore, every optimal tree has external nodes on at most two adjacent levels, completing the proof:

$$ \boxed{\text{The minimum modified external path length occurs when leaves lie on at most two adjacent levels.}} $$