TAOCP 6.2.2 Exercise 17

Section 6.2.2: Binary Tree Searching

Exercise 17. [25] [25] Show that if the roles of left and right are completely reversed in Algorithm D, it is easy to extend the algorithm so that it deletes a given node from a right-threaded tree, preserving the necessary threads. (See exercise 2.)

Verified: no
Solve time: 4m47s

A correct solution must start from a precise dual of Algorithm D and then state explicit, local pointer and tag updates that maintain inorder threading in all cases. The previous argument failed because it relied on informal symmetry and incomplete thread maintenance. We now reconstruct the deletion procedure directly in the right-threaded setting and verify each case.

Right-threaded binary search trees

In a right-threaded binary search tree each node $X$ has fields

$\mathrm{LLINK}(X)$: left child pointer (always a real child pointer or null),
$\mathrm{RLINK}(X)$: either right child or inorder successor,
$\mathrm{RTAG}(X)\in{\text{child},\text{thread}}$.

If $\mathrm{RTAG}(X)=\text{thread}$, then $\mathrm{RLINK}(X)=\mathrm{succ}(X)$ in inorder sequence.

A left link is always a child link; threading occurs only on the right.

Basic structural facts

Define

$\mathrm{succ}(X)$: inorder successor of $X$
$\mathrm{pred}(X)$: inorder predecessor of $X$

In a right-threaded tree:

If $\mathrm{RTAG}(X)=\text{thread}$, then $\mathrm{succ}(X)=\mathrm{RLINK}(X)$.
If $X$ has a left child, then $\mathrm{pred}(X)$ is the rightmost node in the left subtree.
Otherwise $\mathrm{pred}(X)$ is found by following parent structure; this is unchanged from ordinary BST logic.

Deletion strategy (mirror of Algorithm D)

We delete a node $T$ while preserving inorder order and all threads.

There are two structural cases.

Case 1: $T$ has at most one real child

Let $C$ be the real child of $T$, or $C=\Lambda$ if none exists.

We first identify the inorder neighbors of $T$:

$P = \mathrm{pred}(T)$
$Q = \mathrm{succ}(T)$

Thread correction (boundary fix)

Only two possible threads may refer to $T$:

the right thread of $P$ if $\mathrm{RTAG}(P)=\text{thread}$,
the left-thread analogue is irrelevant since left links are never threads in a right-threaded tree.

If $\mathrm{RTAG}(P)=\text{thread}$, set

$$ \mathrm{RLINK}(P) \leftarrow Q. $$

This is the only required inorder-thread update in Case 1.

Structural splice

Let $U$ be the parent of $T$.

If $U=\Lambda$, then $C$ becomes the root.
Otherwise replace the appropriate child pointer of $U$ by $C$.

No other structural changes are required.

Why this is sufficient

The inorder sequence loses $T$ and directly connects $P$ to $Q$.
Subtrees of $C$ remain intact.
No internal subtree threads are affected.

Case 2: $T$ has two real children

Let both $\mathrm{LLINK}(T)$ and the right subtree (via child link) be present.

We use the inorder predecessor.

Step 1: choose replacement node

Let

$$ S = \text{rightmost node in the left subtree of } T. $$

This means:

start at $\mathrm{LLINK}(T)$,
follow $\mathrm{RLINK}$ while $\mathrm{RTAG}=\text{child}$,
stop at the last node $S$.

Then:

$\mathrm{RTAG}(S)=\text{thread}$,
$\mathrm{RLINK}(S)=\mathrm{succ}(S)=T$.

Let $P = \mathrm{pred}(S)$. Then $P$ is the parent encountered immediately before $S$ on the right-chain in the left subtree.

Step 2: remove $S$ from its current position

Since $S$ is the rightmost node of the left subtree:

$S$ has no right child (its right link is a thread),
$S$ may have a left child $L_S = \mathrm{LLINK}(S)$.

We splice $S$ out by updating the parent $P$:

If $S$ is the right child of $P$, set

$$ \mathrm{RLINK}(P) \leftarrow \mathrm{LLINK}(S), \quad \mathrm{RTAG}(P) \text{ unchanged}. $$

This preserves inorder structure in the left subtree.

Step 3: move $S$ into position of $T$

We copy structure, not just pointers, carefully preserving thread semantics:

$\mathrm{LLINK}(S) \leftarrow \mathrm{LLINK}(T)$

The left link is always a child link, so no tag adjustment is needed.

$\mathrm{RLINK}(S) \leftarrow \mathrm{RLINK}(T)$
$\mathrm{RTAG}(S) \leftarrow \mathrm{RTAG}(T)$

This transfers the entire right subtree or successor thread structure of $T$ to $S$.

Step 4: fix the critical thread boundary

The only node whose inorder successor changes due to removal of $T$ is $P = \mathrm{pred}(T)$.

Since $S$ replaces $T$, we must ensure:

the inorder predecessor of $S$ is still $P$,
the inorder successor of $S$ is still $\mathrm{succ}(T)$.

Thus we perform:

If $\mathrm{RTAG}(P)=\text{thread}$, then

$$ \mathrm{RLINK}(P) \leftarrow S. $$

This replaces the old successor $T$ by $S$.

No other thread changes are needed because:

all nodes in the left subtree preserve relative inorder structure,
all nodes in the right subtree are unchanged except their predecessor becomes $S$, which is achieved automatically by attaching $S$ in place of $T$.

Correctness verification

1. Inorder sequence preservation

Case 1 removes $T$ and connects $P \to Q$.
Case 2 replaces $T$ by its inorder predecessor $S$, which is the standard BST invariant-preserving replacement.

Thus inorder order is unchanged in both cases.

2. Thread correctness

Only boundary threads can change:

In Case 1: only $\mathrm{RLINK}(P)$ may change, and it is updated to $\mathrm{succ}(T)$.
In Case 2:
$\mathrm{RLINK}(P)$ is updated from $T$ to $S$,
all other threads remain valid because subtree structure is preserved and $S$ inherits $T$'s right structure.

No dangling thread pointers remain.

3. Structural validity

Every node still has at most one right child; threads remain only where $\mathrm{RTAG}=\text{thread}$.
No child pointer is ever mistaken for a thread or vice versa.
All updates are local (constant number of pointer/tag changes per deletion case).

Conclusion

By explicitly mirroring the successor-based deletion of Algorithm D and replacing it with predecessor-based replacement in the two-child case, and by carefully updating only the boundary right-thread pointers, we obtain a correct deletion algorithm for right-threaded binary search trees. All inorder threads remain valid, and the inorder sequence is preserved. ∎