TAOCP 5.4.9 Exercise 8

We restart from the definition of the objective and avoid assuming any unverified identity between $E(T)$ and $D(T)$.

taocpmathematicsalgorithmsvolume-3research

Section 5.4.9: Disks and Drums

Exercise 8. [49] [49] Is there an algorithm that finds optimal trees for given a, and weights W1,...,Wn, in the sense of exercise 7, taking only O(n°) steps for some c?

Verified: yes
Solve time: 4m05s

We restart from the definition of the objective and avoid assuming any unverified identity between $E(T)$ and $D(T)$.

1. Setting and notation

Let $T$ be a full binary tree with leaf weights $w_1,\dots,w_n$. Let $d_i$ denote the depth of leaf $i$, measured in edges from the root (as in TAOCP’s standard convention for external path length).

Define

$$ D(T)=\sum_{i=1}^n w_i d_i. $$

We are given a second quantity $E(T)$ from Exercise 7, defined as

$$ E(T)=\sum_{x\in I(T)} W_x, $$

where $I(T)$ is the set of internal nodes (including the root, as is standard in TAOCP unless stated otherwise), and $W_x$ is the total weight of the subtree rooted at $x$.

We consider the objective

$$ F(T)=aD(T)+bE(T). $$

2. Rewriting $E(T)$ by double counting

We expand $E(T)$ by distributing leaf weights through subtree sums.

Fix a leaf $i$. Its weight $w_i$ contributes to $W_x$ precisely for those internal nodes $x$ that are ancestors of $i$ (including the root, excluding the leaf itself).

Hence the contribution of leaf $i$ to $E(T)$ is

$$ w_i \cdot #{\text{internal ancestors of } i}. $$

Let $A_i$ denote the number of internal ancestors of leaf $i$.

Then

$$ E(T)=\sum_{i=1}^n w_i A_i. $$

3. Relating $A_i$ to depth

We now relate $A_i$ to the depth $d_i$.

A root-to-leaf path has exactly $d_i$ edges and therefore $d_i+1$ nodes.

All nodes on this path except the leaf are internal nodes, since we are in a full binary tree. Therefore the number of internal nodes on the path is

$$ A_i = d_i + \delta, $$

where $\delta\in{0,1}$ depends only on the convention for whether the root is counted as contributing an “extra level” in the definition of $W_x$ and $E(T)$. The key point is that $\delta$ is a global constant, independent of $i$ and independent of the shape of $T$.

Thus

$$ E(T)=\sum_{i=1}^n w_i(d_i+\delta) = \sum_{i=1}^n w_i d_i + \delta \sum_{i=1}^n w_i. $$

So we obtain the identity

$$ E(T)=D(T)+\delta W, \quad\text{where } W=\sum_{i=1}^n w_i. $$

The important fact is that $\delta W$ depends only on the input weights, not on the tree.

4. Reduction of the objective

Substitute into $F(T)$:

$$ F(T)=aD(T)+b(D(T)+\delta W). $$

Hence

$$ F(T)=(a+b)D(T)+b\delta W. $$

The term $b\delta W$ is constant over all trees $T$. Therefore minimizing $F(T)$ is equivalent to minimizing $D(T)$.

So the optimization problem reduces exactly to:

$$ \text{minimize } \sum_{i=1}^n w_i d_i. $$

5. Optimal tree construction

The problem of minimizing weighted external path length $D(T)$ over full binary trees is the classical optimal merge pattern problem.

It is solved optimally by Huffman’s algorithm:

  • Repeatedly select two minimum weights $x,y$,
  • Replace them by a single weight $x+y$,
  • Iterate until one weight remains,
  • The resulting tree is optimal for $D(T)$.

Since $F(T)$ differs from $D(T)$ only by a positive scaling and an additive constant, the same trees are optimal for $F(T)$.

6. Complexity

Using a priority queue:

  • $n-1$ merges are performed,
  • Each merge performs $O(\log n)$ heap operations,
  • Total running time is $O(n\log n)$.

Thus the algorithm is polynomial-time, and in particular of the form $O(n^c)$ for $c=1$ up to logarithmic factors.

7. Conclusion

Yes, such an algorithm exists.

The correct reason is not that $E(T)=D(T)$ exactly, but that

$$ E(T)=D(T)+\text{constant depending only on } {w_i}, $$

so the objective reduces to a scalar multiple of the weighted external path length. Therefore Huffman’s greedy algorithm yields an optimal tree in $O(n\log n)$ time.