TAOCP 6.3 Exercise 39

We construct a fully rigorous solution by cleanly separating the structural lemma from the contraction argument, avoiding informal swapping arguments.

taocpmathematicsalgorithmsvolume-3math-project

Section 6.3: Digital Searching

Exercise 39. [M43] [M43] Develop an algorithm to find optimum digital search trees, analogous to the optimum binary search trees considered in Section 6.2.2.

Verified: yes
Solve time: 4m28s

We construct a fully rigorous solution by cleanly separating the structural lemma from the contraction argument, avoiding informal swapping arguments.

Problem restatement

We are given keys $K_1,\dots,K_n$ with probabilities $p_1,\dots,p_n>0$, $\sum_{i=1}^n p_i=1$. A digital search tree for successful search corresponds to a full binary tree whose leaves are labeled by the keys, and the cost of searching $K_i$ is its leaf depth $d_i$.

We wish to minimize

$$ W(T)=\sum_{i=1}^n p_i d_i, $$

over all full binary trees with $n$ labeled leaves.

This is the problem of minimizing weighted external path length.

Step 1: structural lemma (deepest sibling pair)

Lemma 1

In any full binary tree, there exist two leaves of maximum depth that are siblings.

Proof

Let $T$ be a full binary tree and let $d_{\max}$ be the maximum leaf depth.

Take any node $v$ at depth $d_{\max}-1$. Such a node must exist because a leaf at depth $d_{\max}$ has a parent at depth $d_{\max}-1$.

In a full binary tree every internal node has exactly two children. Therefore $v$ has exactly two children, say $v_L$ and $v_R$.

Neither $v_L$ nor $v_R$ can be internal nodes, because that would imply a leaf at depth greater than $d_{\max}$, contradicting maximality of $d_{\max}$.

Hence both $v_L$ and $v_R$ are leaves at depth $d_{\max}$, and they are siblings.

∎

Step 2: exchange lemma (two smallest weights can be placed deepest)

Lemma 2

There exists an optimal tree in which the two smallest probabilities are assigned to sibling leaves at maximum depth.

Proof

Let $T$ be an optimal tree. Let $x,y$ be any sibling pair of leaves at maximum depth $d_{\max}$, whose probabilities are $p_x,p_y$.

Let $a,b$ be the two smallest probabilities among all $p_i$, so $p_a \le p_b \le p_i$ for all $i$.

We show that there exists an optimal tree in which $a$ and $b$ are placed at $x$ and $y$.

Step 2.1: placing a smallest weight at maximum depth

Assume $p_a > p_x$. Let $a$ be at depth $d(a)\le d_{\max}$.

If $d(a) < d_{\max}$, swap labels $a$ and $x$. The change in cost is

$$ \Delta = p_a d_{\max} + p_x d(a) - (p_x d_{\max} + p_a d(a)) = (p_a - p_x)(d_{\max} - d(a)) > 0 $$

since $p_a > p_x$ and $d_{\max} > d(a)$.

Thus swapping decreases cost, contradicting optimality of $T$. Therefore no such $a$ exists, and we must have $p_x \le p_a$.

Since $a$ is the smallest probability, this forces $p_x = p_a$.

Hence some optimal tree has $a$ at a deepest leaf.

Step 2.2: placing the second smallest weight

Remove $a$ from consideration and apply the same argument to the remaining tree.

Among the remaining leaves, let $b$ be the smallest probability. By the same exchange argument, any optimal tree can be modified (without increasing cost) so that $b$ occupies a deepest remaining leaf.

Because deepest leaves occur in sibling pairs (Lemma 1), we can ensure $a$ and $b$ occupy the two sibling leaves at depth $d_{\max}$.

Thus there exists an optimal tree in which the two smallest probabilities are siblings at maximum depth.

∎

Step 3: reduction (contraction step)

Lemma 3

Let $x,y$ be sibling leaves in a tree $T$ at depth $d_{\max}$, and let $p_z=p_x+p_y$. Let $T'$ be the tree obtained by replacing $x,y$ with a single leaf $z$ at depth $d_{\max}-1$. Then

$$ W(T)=W(T')+(p_x+p_y). $$

Proof

Only the contributions of $x$ and $y$ change.

In $T$:

$$ p_x d_{\max} + p_y d_{\max}. $$

In $T'$:

$$ (p_x+p_y)(d_{\max}-1). $$

Subtracting gives

$$ p_x d_{\max} + p_y d_{\max} - (p_x+p_y)(d_{\max}-1) = p_x + p_y. $$

All other leaves remain unchanged in depth, so the identity holds.

∎

Step 4: optimality theorem

Theorem

An optimal digital search tree is obtained by repeatedly merging the two smallest probabilities, i.e. by the Huffman algorithm.

Proof

We proceed by induction on $n$.

Base cases

For $n=1$, the cost is $0$.

For $n=2$, the only tree has both leaves at depth $1$, which is trivially optimal.

Inductive step

Assume correctness for all instances of size $<n$.

Let $a,b$ be the two smallest probabilities. By Lemma 2, there exists an optimal tree $T$ in which $a$ and $b$ are sibling leaves at maximum depth.

Form a reduced instance by replacing $a,b$ with a single leaf $z$ of weight

$$ p_z = p_a + p_b. $$

By Lemma 3, every tree $T'$ for the reduced instance corresponds to a tree $T$ for the original instance with

$$ W(T)=W(T')+p_a+p_b, $$

and this additive term is independent of structure.

Thus minimizing $W(T)$ over the original instance is equivalent to minimizing $W(T')$ over the reduced instance.

By the induction hypothesis, the reduced instance is optimally solved by repeatedly applying the same rule.

Therefore the original instance is solved by repeatedly merging the two smallest weights.

Algorithm

Use a min-priority queue:

  1. Insert all weights $p_1,\dots,p_n$.
  2. While more than one weight remains:
  • extract two minimum elements $a,b$,
  • replace them with $a+b$,
  • insert $a+b$.
  1. The induced binary tree is the optimal digital search tree.

Conclusion

The corrected proof isolates the key structural fact: a full binary tree always contains a deepest sibling pair, and an exchange argument shows that the two smallest probabilities can be placed at such a pair in some optimal tree. The contraction lemma then yields a clean induction identical to Huffman coding, establishing optimal digital search trees.