TAOCP 6.2.2 Exercise 43

Exercise 43. [20] [20] Explain how to implement phase 2 of the Garsia, Wachs algorithm efficiently.

44, [25] Explain how to implement phase 3 of the Garsia, Wachs algorithm efficiently: Construct a binary tree, given the levels lo, 1, ..., In of its leaves in symmetric order.

Verified: yes
Solve time: 1m36s

Solution

Phase 2 constructs the binary tree from the sequence produced by phase 1, which is a linear list of leaves (or partial trees) in symmetric order. Each element has an associated weight, and only adjacent elements in this list are ever eligible to be combined.

Let the current sequence be maintained as a doubly linked list of nodes. Each node $x$ stores its weight $w(x)$ and pointers $L(x)$ and $R(x)$ to its current predecessor and successor in the sequence. The goal is to repeatedly combine two adjacent nodes into a single node until only one node remains.

To obtain an efficient implementation, associate with each pair of adjacent nodes $(x, R(x))$ a record representing the pair weight

$$ p(x) = w(x) + w(R(x)). $$

All such pairs are stored in a priority queue keyed by $p(x)$.

Each entry in the priority queue also stores a pointer to $x$. Because adjacency changes during the process, a queue entry is valid only if $R(x)$ still exists and satisfies $L(R(x)) = x$. Any entry failing this condition is ignored when extracted.

The phase proceeds by repeated extraction of a minimum pair.

When a pair pointer $x$ is extracted from the priority queue, the condition $L(R(x)) = x$ is tested. If it fails, the pair is obsolete and is discarded, and the next minimum is extracted.

When the pair is valid, the algorithm combines $x$ and $R(x)$ into a new node $z$. The node $z$ becomes the replacement for $x$ and $R(x)$ in the sequence. Its weight is defined by

$$ w(z) = w(x) + w(R(x)). $$

Its left and right links are set so that $x$ and $R(x)$ become its children in the binary tree being constructed, preserving the ordering of leaves required by symmetric traversal.

In the doubly linked list, $z$ is inserted in place of the consecutive pair $(x, R(x))$. If $L(x)$ exists, then its right pointer is changed from $x$ to $z$. If $R(R(x))$ exists, its left pointer is changed from $R(x)$ to $z$. The node $z$ is then linked between these neighbors.

After this replacement, new adjacent pairs are created only locally: $(L(z), z)$ and $(z, R(z))$, whenever the corresponding neighbors exist. For each such pair, a priority queue entry with key equal to the sum of their weights is inserted.

This locality holds because all unaffected pairs retain their adjacency relations and therefore their previously stored keys remain valid for correctness checking at extraction time.

The process terminates when the list contains a single node. This node is the root of the binary tree.

Correctness follows because every operation combines two adjacent elements, preserving the in-order sequence of leaves, and because every pair ever combined is selected in nondecreasing order of weight sum among all currently adjacent pairs, matching the greedy structure required by the optimal alphabetic tree construction described in the Garsia–Wachs method.

The efficiency of the method comes from the fact that each node is created exactly once and each adjacency is inserted into the priority queue a constant number of times, while each queue operation costs logarithmic time in the number of active pairs. The list operations are constant-time pointer updates.

This completes the description of an efficient implementation of phase 2. ∎