TAOCP 2.4 Exercise 12

Section 2.4: Multilinked Structures

Exercise 12. [**] [25] (D. M. Dahm.) Consider representing the Data Table in sequential locations with just two links for each item:

PREV  (as in the text);
SCOPE (a link to the last elementary item in this group).

We have SCOPE(P) = P if and only if NODE(P) represents an elementary item. For example, the Data Table of (5) would be replaced by

	`PREV`	`SCOPE`		`PREV`	`SCOPE`		`PREV`	`SCOPE`
`A1:`	`\Lambda`	`G4`	`F3:`	`\Lambda`	`G4`	`B5:`	`B3`	`B5`
`B3:`	`\Lambda`	`D7`	`G4:`	`\Lambda`	`G4`	`C5:`	`C7`	`G9`
`C7:`	`\Lambda`	`C7`	`H1:`	`\Lambda`	`G9`	`E9:`	`E3`	`E9`
`D7:`	`\Lambda`	`D7`	`F5:`	`F3`	`G8`	`D9:`	`D7`	`D9`
`E3:`	`\Lambda`	`E3`	`G8:`	`G4`	`G8`	`G9:`	`G8`	`G9`

(Compare with (5) of Section 2.3.3.) Notice that NODE(P) is part of the tree below NODE(Q) if and only if Q < P <= SCOPE(Q). Design an algorithm that performs the function of Algorithm B when the Data Table has this format.

Verified: yes
Solve time: 1m32s

Let the Data Table entries be stored in preorder, and let the structure stack be represented by the chain of PREV links exactly as in Algorithm B. The essential fact is

$$ \text{NODE}(P)\text{ is below }\text{NODE}(Q) \iff Q<P\le \text{SCOPE}(Q). $$

Hence the test performed in Algorithm B by following descendant links can be replaced by interval tests on the sequential positions.

When a new item $P$ is read, let $T$ be the item currently on the top of the structure stack. While $T\ne\Lambda$ and $P>\text{SCOPE}(T)$, remove $T$ from the stack by setting $T\leftarrow\text{PREV}(T)$. After this process terminates, $T$ is the unique item of greatest depth whose subtree contains $P$, because $P$ lies in the interval $(T,\text{SCOPE}(T)]$ and in no corresponding interval for any deeper item. Therefore $\text{NODE}(P)$ is attached as a son of $\text{NODE}(T)$; if the stack becomes empty, $\text{NODE}(P)$ is a root node. Finally, place $P$ on the top of the stack.

Thus Algorithm B is obtained by replacing its search for the proper ancestor by the repeated test

$$ P>\text{SCOPE}(T), $$

using the PREV chain to move upward. The SCOPE field determines exactly when a subtree has ended, so the resulting tree is identical to the one constructed by Algorithm B.