TAOCP 2.3.1 Exercise 23
A _right-threaded_ binary tree contains ordinary left links and either ordinary right links or right threads.
Section 2.3.1: Traversing Binary Trees
Exercise 23. [22] Design algorithms analogous to Algorithm I for insertion to the right and insertion to the left in a right-threaded binary tree. Assume that the nodes have the fields LLINK, RLINK, and RTAG.
Verified: no
Solve time: 49s
Solution
A right-threaded binary tree contains ordinary left links and either ordinary right links or right threads. Thus each node contains the fields LLINK, RLINK, and RTAG, where
$$ RTAG(P)= \begin{cases} 0, & \text{if } RLINK(P) \text{ points to a right subtree};\ 1, & \text{if } RLINK(P)=P$. \end{cases} $$
Algorithm I for insertion in a threaded tree inserts a node while preserving the threading relation. Since only right threads are present, insertion to the right and insertion to the left must preserve all inorder successor relations represented by RLINK when RTAG=1.
Algorithm RI (Insertion to the right)
Suppose P points to a node of a right-threaded binary tree, and Q is a new node to be inserted as the right son of P. The insertion is possible only if RTAG(P)=1, since otherwise P already has a right subtree.
The inorder successor of P before insertion is P\$ = RLINK(P). After insertion, Q becomes the immediate inorder successor of P, and Q inherits the former successor of P as its own inorder successor.
The algorithm is therefore:
RI1. [Right subtree present?] If RTAG(P)=0, the insertion is impossible.
RI2. [Set successor thread.] Set RLINK(Q)\leftarrow RLINK(P) and RTAG(Q)\leftarrow 1.
RI3. [Initialize left link.] Set LLINK(Q)\leftarrow \Lambda.
RI4. [Insert node.] Set RLINK(P)\leftarrow Q and RTAG(P)\leftarrow 0. The algorithm terminates.
To verify correctness, let S=P\$ before insertion. Since RTAG(P)=1, we have RLINK(P)=S. After step RI2, RLINK(Q)=S, so Q\$=S. After step RI4, P has an ordinary right link to Q, hence P\$=Q. Since Q has no left subtree, inorder traversal visits
$$ P,\ Q,\ S, $$
which is precisely the required order. No other thread relation is changed.
Algorithm LI (Insertion to the left)
Suppose P points to a node of a right-threaded binary tree, and Q is a new node to be inserted as the left son of P. Since left links are not threaded, insertion is possible only if LLINK(P)=\Lambda.
Before insertion, P has some inorder predecessor, say \$P. After insertion, Q becomes the immediate inorder predecessor of P. Since Q has no right subtree, its inorder successor must be P.
The algorithm is therefore:
LI1. [Left subtree present?] If LLINK(P)\ne\Lambda, the insertion is impossible.
LI2. [Set successor thread.] Set RLINK(Q)\leftarrow P and RTAG(Q)\leftarrow 1.
LI3. [Initialize left link.] Set LLINK(Q)\leftarrow \Lambda.
LI4. [Insert node.] Set LLINK(P)\leftarrow Q. The algorithm terminates.
For correctness, after step LI2, Q\$=P. Since Q has no left subtree and no right subtree, inorder traversal of the subtree rooted at P becomes
$$ Q,\ P, $$
instead of simply
$$ P. $$
No right thread elsewhere requires modification. The predecessor of P need not be altered, because predecessor information is not stored in a right-threaded tree.
The required algorithms are therefore:
$$ \boxed{ \begin{array}{l} \text{RI: if }RTAG(P)=1,\ \text{make }Q\text{ the right son of }P\ \qquad RLINK(Q)\leftarrow RLINK(P),\ RTAG(Q)\leftarrow 1,\ \qquad LLINK(Q)\leftarrow \Lambda,\ \qquad RLINK(P)\leftarrow Q,\ RTAG(P)\leftarrow 0.\[6pt] \text{LI: if }LLINK(P)=\Lambda,\ \text{make }Q\text{ the left son of }P\ \qquad RLINK(Q)\leftarrow P,\ RTAG(Q)\leftarrow 1,\ \qquad LLINK(Q)\leftarrow \Lambda,\ \qquad LLINK(P)\leftarrow Q. \end{array} } $$