TAOCP 6.2.2 Exercise 2
Let each node $P$ contain fields $\operatorname{KEY}(P)$, $\operatorname{LLINK}(P)$, $\operatorname{RLINK}(P)$, and a tag $\operatorname{RTAG}(P)\in{0,1}$.
Section 6.2.2: Binary Tree Searching
Exercise 2. [20] [20] Modify Algorithm T so that it works with right-threaded trees. (See Section 2.3.1; symmetric traversal is easier in such trees.)
Verified: no
Solve time: 1m19s
Solution
Let each node $P$ contain fields $\operatorname{KEY}(P)$, $\operatorname{LLINK}(P)$, $\operatorname{RLINK}(P)$, and a tag $\operatorname{RTAG}(P)\in{0,1}$. The interpretation is that $\operatorname{RTAG}(P)=0$ means $\operatorname{RLINK}(P)$ is a right child, while $\operatorname{RTAG}(P)=1$ means $\operatorname{RLINK}(P)$ is the symmetric successor (a thread). The root pointer is $\operatorname{ROOT}$.
Algorithm T is modified so that all right-null links are replaced by threads to the next node in symmetric order, and search uses these threads to avoid descending into null structure.
Modified Algorithm T (right-threaded tree search and insertion)
$T1$. [Initialize.] Set $P \leftarrow \operatorname{ROOT}$.
$T2$. [Search for position.] If $P = \Lambda$, go to $T4$.
If $K = \operatorname{KEY}(P)$, terminate search.
If $K < \operatorname{KEY}(P)$, go to $T3$.
If $K > \operatorname{KEY}(P)$ and $\operatorname{RTAG}(P) = 0$, set $P \leftarrow \operatorname{RLINK}(P)$ and return to $T2$.
If $K > \operatorname{KEY}(P)$ and $\operatorname{RTAG}(P) = 1$, go to $T4$.
$T3$. [Move left.] If $\operatorname{LLINK}(P) = \Lambda$, go to $T4$. Otherwise set $P \leftarrow \operatorname{LLINK}(P)$ and return to $T2$.
$T4$. [Insert new node $Q$ with key $K$.] Allocate a new node $Q$ and set $\operatorname{KEY}(Q)\leftarrow K$.
If $P = \Lambda$, set $\operatorname{LLINK}(Q)\leftarrow \Lambda$, $\operatorname{RLINK}(Q)\leftarrow \Lambda$, $\operatorname{RTAG}(Q)\leftarrow 1$, and $\operatorname{ROOT}\leftarrow Q$.
If $K < \operatorname{KEY}(P)$, set $\operatorname{LLINK}(Q)\leftarrow \operatorname{LLINK}(P)$, $\operatorname{RLINK}(Q)\leftarrow P$, $\operatorname{RTAG}(Q)\leftarrow 1$, and set $\operatorname{LLINK}(P)\leftarrow Q$.
If $K > \operatorname{KEY}(P)$ and $\operatorname{RTAG}(P)=1$, set $\operatorname{RLINK}(Q)\leftarrow \operatorname{RLINK}(P)$, $\operatorname{RTAG}(Q)\leftarrow 1$, $\operatorname{LLINK}(Q)\leftarrow \Lambda$, set $\operatorname{RLINK}(P)\leftarrow Q$, and set $\operatorname{RTAG}(P)\leftarrow 0$.
If $K > \operatorname{KEY}(P)$ and $\operatorname{RTAG}(P)=0$, set $\operatorname{LLINK}(Q)\leftarrow \Lambda$, $\operatorname{RLINK}(Q)\leftarrow \operatorname{RLINK}(P)$, $\operatorname{RTAG}(Q)\leftarrow 1$, set $\operatorname{RLINK}(P)\leftarrow Q$, and set $\operatorname{RTAG}(P)\leftarrow 0$.
This completes the modification of Algorithm T.
Correctness of threading invariant
After each insertion, every node $P$ with $\operatorname{RTAG}(P)=1$ satisfies that $\operatorname{RLINK}(P)$ is the next node in symmetric order. This property holds initially for the empty structure. When a new node $Q$ is inserted as a right child of $P$ or as a left descendant of a right-threaded chain, the former successor of $P$ becomes the successor of $Q$, and $Q$ becomes the successor of $P$, which preserves the symmetric-order linkage.
Each modification in $T4$ adjusts exactly the two right-thread pointers involved in the local insertion, so no other threads are affected.
Use in traversal
Because $\operatorname{RLINK}(P)$ is either a child or a successor, symmetric traversal reduces to repeated application of: move to leftmost node, output, then follow right threads until $\operatorname{RTAG}=0$, after which a descent into the right subtree resumes. This follows directly from the definition of $\operatorname{RTAG}$ and the construction in $T4$.
This completes the solution. ∎