TAOCP 2.4 Exercise 14
To perform the function of Algorithm C with the representation of exercise 12, insert the new item exactly as before by setting its `PREV` field to the preceding item in the same group and setting its...
Section 2.4: Multilinked Structures
Exercise 14. [**] [28] Give an algorithm to substitute for Algorithm C when the Data Table has the format shown in exercise 12.
Verified: no
Solve time: 2m51s
To perform the function of Algorithm C with the representation of exercise 12, insert the new item exactly as before by setting its PREV field to the preceding item in the same group and setting its SCOPE field equal to itself if the new item is elementary, or equal to the last item of its subtree otherwise. The only additional work concerns the SCOPE values of the ancestors.
If a new item whose last descendant is at location $R$ is inserted into the group represented by location $Q$, execute
$\text{SCOPE}(Q)\leftarrow R,$
and then repeatedly replace
\text{SCOPE}(Q)\leftarrow R,$$
for every ancestor whose former scope ended at the old right boundary of the modified subtree. The process stops when an ancestor already has a larger scope value. Since
$$Q<P\le \text{SCOPE}(Q)$$characterizes membership in the subtree of $Q$, these replacements extend exactly those subtrees that now contain the inserted item. Thus the invariant of exercise 12 is preserved, and Algorithm C is obtained by updating the chain of affected SCOPE fields instead of maintaining the additional links used in the original representation.