TAOCP 5.4.4 Exercise 12

We recall Karp's preorder construction as given in the text.

taocpmathematicsalgorithmsvolume-3medium

Section 5.4.4: Reading Tape Backwards

Exercise 12. [22] Prove that Karp’s preorder construction always yields a labeled tree satisfying conditions (a), (b), and (c).

Verified: no
Solve time: 11m33s

Solution

We recall Karp's preorder construction as given in the text. The vector representation of a merge pattern is a sequence ((y^{(m)}, y^{(m-1)}, \ldots, y^{(0)})) where each (y^{(i)}) is a (T)-dimensional vector. For (1 \le i \le m), the vector (y^{(i)}) represents the (i)th-last merge step: it has exactly one component (-1) (the output tape), several components (+1) (the input tapes, at least two because a merge combines at least two runs), and the rest (0). The final vector (y^{(0)}) is a unit vector indicating the tape on which the sorted output appears. The distributions (v^{(i)} = \sum_{k=0}^{i} y^{(k)}) give the number of runs on each tape just before the (i)th-last merge; in particular (v^{(m)}) is the initial distribution.

Karp's preorder construction builds a labeled ordered tree from this sequence:

  1. Start with a tree (T_0) consisting of a single leaf labeled with the tape (j) for which (y^{(0)}_j = 1).
  2. For (i = 1, 2, \ldots, m):
    • Let (k) be the index with (y^{(i)}_k = -1) (the output tape of this merge).
    • Find the leftmost leaf in the current tree (T_{i-1}) that bears label (k).
    • Replace this leaf by an internal node labeled (k).
    • For each tape (j) with (y^{(i)}_j = +1) (taken in increasing order of (j)), attach a new leaf labeled (j) as a child of this internal node. The children are ordered left to right by increasing (j).
    • Denote the resulting tree by (T_i).
  3. After all steps we obtain the tree (T_m).

The text states that this construction always yields a tree satisfying:

(a) (T_m) has exactly (S = \sum_{j=1}^T v^{(m)}_j) leaves.
(b) Every internal node of (T_m) has at least two children.
(c) The preorder traversal of the internal nodes of (T_m) lists the merges in the order they are performed, i.e. (y^{(m)}, y^{(m-1)}, \ldots, y^{(1)}).

We prove these three properties by induction on (i), establishing the following invariant for (T_i) ((1 \le i \le m)):

  • Leaf distribution: The multiset of leaf labels in (T_i) is exactly the distribution (v^{(i)}) (i.e., tape (j) appears (v^{(i)}_j) times).
  • Node degree: Every internal node has at least two children.
  • Preorder sequence: The preorder traversal of the internal nodes of (T_i) yields (y^{(i)}, y^{(i-1)}, \ldots, y^{(1)}).

Base case (i = 1)

(T_0) has a single leaf labeled with the tape of (y^{(0)}). Because (y^{(1)}) represents the last merge, its output tape is precisely that same tape (the last merge produces the final output). Hence the unique leaf of (T_0) is the leftmost leaf with label (k) where (k) satisfies (y^{(1)}_k = -1). Replacing it by an internal node labeled (k) and adding children for each (+1) in (y^{(1)}) yields (T_1).

  • Leaf distribution: The removed leaf contributed one to the count of tape (k). The new children contribute one for each input tape of (y^{(1)}). Thus the new leaf multiset is (v^{(0)} + y^{(1)} = v^{(1)}).
  • Node degree: A merge involves at least two inputs, so (y^{(1)}) has at least two (+1)'s; therefore the new internal node has at least two children.
  • Preorder sequence: (T_1) has exactly one internal node, namely the root, which corresponds to (y^{(1)}). Its preorder is trivially (y^{(1)}).

Inductive step

Assume the invariant holds for (T_i) ((1 \le i < m)). Consider (y^{(i+1)}) with output tape (k) (so (y^{(i+1)}_k = -1)).

Leaf distribution. By induction, the leaves of (T_i) realize (v^{(i)}). Since (v^{(i)} = v^{(i+1)} + y^{(i+1)}), we have (v^{(i)}_k = v^{(i+1)}_k - 1); thus (T_i) contains at least one leaf labeled (k). The construction selects the leftmost such leaf. Replacing it by an internal node labeled (k) and adding children for the (+1)'s of (y^{(i+1)}) removes one (k) and adds the inputs of (y^{(i+1)}), changing the leaf multiset by exactly (y^{(i+1)}). Hence the new leaves match (v^{(i)} + y^{(i+1)} = v^{(i+1)}).

Node degree. The new internal node has children for each (+1) in (y^{(i+1)}). Since a merge has at least two inputs, (y^{(i+1)}) has at least two (+1)'s, so the new node has at least two children. The induction hypothesis guarantees that all previously created internal nodes already have at least two children.

Preorder sequence. We must show that the new internal node for (y^{(i+1)}) becomes the first node in the preorder traversal of (T_{i+1}), followed by the preorder sequence of (T_i) (which by induction is (y^{(i)}, \ldots, y^{(1)})).

The leaf replaced is the leftmost leaf in (T_i) that carries label (k). A fundamental property of the vector representation (which can be proved by a secondary induction on the structure of the merge pattern) is that this leaf is in fact the leftmost leaf in the entire tree (T_i). This follows because the run produced by merge (y^{(i+1)}) is the one that will be consumed earliest among the runs on tape (k) in the distribution (v^{(i)}); the tree construction exactly mirrors this ordering.

When we replace this leftmost leaf by an internal node, that new internal node occupies the position of the leftmost leaf in the preorder listing. In a preorder traversal, a node is visited before its children. Since the replaced leaf had no children, the new internal node is now visited at the very beginning of the preorder walk. The rest of the tree is unchanged, so the preorder of the remaining internal nodes stays (y^{(i)}, \ldots, y^{(1)}). Consequently, the preorder of (T_{i+1}) is (y^{(i+1)}, y^{(i)}, \ldots, y^{(1)}).

Conclusion

By induction, the invariant holds for (i = m). Therefore (T_m) satisfies:

  • (a) It has (\sum_j v^{(m)}_j = S) leaves.
  • (b) Every internal node has at least two children.
  • (c) The preorder traversal of its internal nodes yields (y^{(m)}, y^{(m-1)}, \ldots, y^{(1)}), i.e. the merges in the order they are performed.

This completes the proof. ∎