TAOCP 5.4.1 Exercise 2

Section 5.4.1: Multiway Merging and Replacement Selection

Exercise 2. [12] [12] What changes would be made to the tree of Fig. 63 if the key 061 were replaced by 612?

Verified: yes
Solve time: 59s

Solution

Figure 63 is a loser tree in which each internal node stores the loser of the comparison, and the root contains the current champion. The key $061$ is the current champion, and it is replaced by $612$. Only the nodes on the search path from the leaf containing $061$ to the root can change, since all other comparisons involve disjoint subtrees.

The original tournament path for $061$ involves exactly three successive comparisons against the keys $512$, $087$, and $154$, in that order along the path to the root. At each internal node on this path, the stored value is the loser of the corresponding match.

After replacement, the leaf containing $061$ is updated to $612$, and the same sequence of opponents is used to reconstruct the tournament along this path.

In the first comparison, $612$ is compared with $512$. Since $512 < 612$, $512$ wins and $612$ becomes the loser stored in the first internal node on the path.

In the second comparison, $512$ is compared with $087$. Since $087 < 512$, $087$ wins and $512$ becomes the loser stored in the second internal node on the path.

In the third comparison, $087$ is compared with $154$. Since $087 < 154$, $087$ wins and $154$ becomes the loser stored in the third internal node on the path, which is the root of the loser tree.

The root now contains $087$, so the champion of the modified tournament is $087$.

All internal nodes off the update path remain unchanged, since no comparisons involving their subtrees are affected by replacing a single external key.

Thus the structural changes are that the three internal nodes on the path previously containing the losers of matches involving $061$ are replaced respectively by $612$, $512$, and $154$, and the root changes from $061$ to $087$.

This completes the update of the loser tree. ∎