TAOCP 5.4.9 Exercise 5
Let $T$ be a rooted tree representing a merge pattern as in Theorem K, with leaves carrying weights $w_1,\dots,w_n$, and let the external path length be E(T)=\sum_{i=1}^n w_i d_i, where $d_i$ is the l...
Section 5.4.9: Disks and Drums
Exercise 5. [M20] [M20] When two disks are being used, so that reading on one is overlapped with writing on the other, we cannot use merge patterns like that of Fig. 93 since some leaves are at even levels and some are at odd levels. Show how to modify the construction of Theorem K in order to produce trees that are optimal subject to the constraint that all leaves appear on even levels or all on odd levels.
Verified: yes
Solve time: 1m31s
Solution
Let $T$ be a rooted tree representing a merge pattern as in Theorem K, with leaves carrying weights $w_1,\dots,w_n$, and let the external path length be
$$ E(T)=\sum_{i=1}^n w_i d_i, $$
where $d_i$ is the level of the $i$th leaf.
Theorem K constructs a tree minimizing $E(T)$ among all admissible trees with given degree constraints.
We now impose the additional constraint that all leaves must lie either entirely on even levels or entirely on odd levels.
Even-level constraint
Construct from any tree $T$ a transformed tree $T^{(2)}$ by replacing every edge by a path of length $2$ obtained by inserting one new dummy node on each edge. Every original leaf at depth $d_i$ in $T$ becomes a leaf at depth $2d_i$ in $T^{(2)}$. Hence all leaves of $T^{(2)}$ lie on even levels.
The external path length of $T^{(2)}$ is
$$ E(T^{(2)})=\sum_{i=1}^n w_i (2d_i)=2E(T). $$
Conversely, let $S$ be any tree satisfying the constraint that all leaves lie on even levels. Contract every maximal path consisting of alternating internal dummy nodes of degree $2$ (introduced solely by the even-level restriction) into single edges. This produces a tree $S'$ in the original class of admissible trees. Each leaf depth in $S$ equals twice its depth in $S'$, hence
$$ E(S)=2E(S'). $$
Since the factor $2$ is independent of structure, minimizing $E(S)$ over all even-level trees is equivalent to minimizing $E(S')$ over all ordinary trees. By Theorem K, the minimizing tree $T^*$ for the unrestricted problem yields a minimizing even-level tree $T^{(2)}$.
Thus $T^{(2)}$ is optimal among all trees whose leaves lie on even levels.
Odd-level constraint
From $T^{(2)}$, construct $T^{(2)}_+$ by adding a new root above the current root and connecting it by a single edge. Every leaf depth increases by $1$, so each leaf previously at depth $2d_i$ now lies at depth $2d_i+1$, which is odd.
The external path length becomes
$$ E(T^{(2)}+)=\sum{i=1}^n w_i (2d_i+1)=2E(T^*)+\sum_{i=1}^n w_i. $$
The additive term $\sum_{i=1}^n w_i$ depends only on the input weights and not on the structure of the tree, so it does not affect which tree minimizes the quantity.
If $S$ is any tree whose leaves all lie on odd levels, removing the top edge from each root-leaf path (equivalently contracting the root edge) yields a tree $S^\circ$ with all leaves on even levels and
$$ E(S)=E(S^\circ)+\sum_{i=1}^n w_i. $$
Minimizing $E(S)$ over odd-level trees is therefore equivalent to minimizing $E(S^\circ)$ over even-level trees, which is achieved by $T^{(2)}$. Hence $T^{(2)}_+$ is optimal among all trees whose leaves lie on odd levels.
This completes the proof. ∎