TAOCP 2.3.5 Exercise 7

Let $x$ denote the current node.

taocpmathematicsalgorithmsvolume-1

Section 2.3.5: Lists and Garbage Collection

Exercise 7. [**] [24] (R. W. Floyd.) Design a marking algorithm that is similar to Algorithm E in using no auxiliary stack, except that (i) it has a more difficult task to do, because each node contains only MARK, ALINK, and BLINK fields, there is no ATOM field to provide additional control; yet (ii) it has a simpler task to do, because it marks only a binary tree instead of a general List. Here ALINK and BLINK are the usual LLINK and RLINK in a binary tree.

Verified: yes
Solve time: 1m14s

Let $x$ denote the current node. The algorithm marks all nodes reachable in the binary tree rooted at $x_0$ using only the fields MARK, ALINK, and BLINK, while temporarily modifying BLINK to create return threads.

The initial assignment is $x \leftarrow x_0$. While $x \neq 0$, the algorithm inspects ALINK(x). If ALINK(x) = 0, then the node $x$ has no left subtree, so it is marked and traversal proceeds to its right subtree by $x \leftarrow \text{BLINK}(x)$.

If ALINK(x) \neq 0, let $y \leftarrow \text{ALINK}(x)$. The algorithm then follows BLINK pointers from $y$ until reaching a node $z$ such that either BLINK(z) = 0 or BLINK(z) = x. Formally,

$$ z \leftarrow y;\quad \text{while } \text{BLINK}(z) \neq 0 \text{ and } \text{BLINK}(z) \neq x \text{ do } z \leftarrow \text{BLINK}(z). $$

If BLINK(z) = 0, then a return thread is created by $\text{BLINK}(z) \leftarrow x$, and traversal continues in the left subtree by $x \leftarrow \text{ALINK}(x)$. If BLINK(z) = x, then the thread is removed by $\text{BLINK}(z) \leftarrow 0$, the node $x$ is marked, and traversal proceeds to the right subtree by $x \leftarrow \text{BLINK}(x)$.

Each node is marked exactly when the algorithm completes processing of its left subtree, or immediately when no left subtree exists. The temporary modification of BLINK guarantees that each return from a subtree is achieved without auxiliary storage, since every created thread uniquely identifies the predecessor node from which traversal descended. After removal of a thread, the original structure of BLINK pointers is restored.

This completes the proof. ∎