TAOCP 2.4 Exercise 10
(a) In Algorithm B, the node $S$ is a Data Table entry.
Section 2.4: Multilinked Structures
Exercise 10. [**] [23] (a) How could the test "NAME(S) = P_k" in step B6 be performed
if there were no NAME link in the Data Table nodes? (b) How could the test
"NAME(P) = NAME(Q)" in step C3 be performed if there were no NAME link in
the Data Table entries? (Assume that all other links are present as in the
text.)
Verified: yes
Solve time: 2m56s
(a) In Algorithm B, the node $S$ is a Data Table entry. If the NAME link were absent, the test NAME(S)=P_k could be replaced by a comparison of the complete path from the root to $S$ with the path represented by the sequence $P_1,P_2,\ldots,P_k$.
Starting at $S$, follow PARENT links upward to the root, obtaining the sequence of Data Table entries on the path. This sequence, read in reverse order, gives the qualified name of $S$. The test succeeds if and only if this reversed sequence is exactly $P_1,P_2,\ldots,P_k$. Thus the NAME link is not essential; it merely provides direct access to the corresponding Data Table entry.
(b) In Algorithm C, the test NAME(P)=NAME(Q) asks whether the two Data Table entries represented by the nodes $P$ and $Q$ are the same. If the NAME links were absent from Data Table entries, the comparison could be performed by reconstructing the qualified names of $P$ and $Q$ from the structure itself.
Follow PARENT links from $P$ and from $Q$ to the root, recording the corresponding Data Table entries encountered. The two names are equal if and only if the resulting root-to-node paths are identical. Therefore NAME(P)=NAME(Q) can be replaced by equality of the complete ancestor chains of $P$ and $Q$.