TAOCP 2.3.1 Exercise 34

Let the right-threaded binary trees use the conventions of the section: - `LLINK(P)` is either a left child or `\Lambda`.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.1: Traversing Binary Trees

Exercise 34. [22] Let P point to a node in some binary tree, and let HEAD point to the list head of an empty binary tree. Give an algorithm that (i) removes NODE(P) and all of its subtrees from whatever tree it was in, and then (ii) attaches NODE(P) and its subtrees to NODE(HEAD). Assume that all the binary trees in question are right-threaded, with fields LLINK, RTAG, RLINK in each node.

Verified: no
Solve time: 45s

Solution

Let the right-threaded binary trees use the conventions of the section:

  • LLINK(P) is either a left child or \Lambda.
  • If RTAG(P)=0, RLINK(P) is a right child.
  • If RTAG(P)=1, RLINK(P)=P$.

Let H denote the node pointed to by HEAD. Since HEAD is the list head of an empty binary tree, its left link is empty and its right thread points to itself.

The operation consists of two parts:

  1. Detach the subtree rooted at P from its present tree.
  2. Make P the root of the tree headed by HEAD.

The crucial fact is that, in a right-threaded tree, the inorder predecessor and successor of the entire subtree rooted at P can be found from the threads at the extreme nodes of that subtree.

Let

  • L be the leftmost node of the subtree rooted at P;
  • R be the rightmost node of the subtree rooted at P.

Then:

  • the inorder predecessor of the subtree is the node threaded to by L;
  • the inorder successor of the subtree is the node threaded to by R.

After the subtree is removed, those two nodes must become adjacent in symmetric order; therefore the predecessor's thread must be changed to the successor.

The only remaining task is to determine whether P was a left child or a right child of its parent. Since threads always point upward, the parent is reached by following successor threads from the rightmost node of the subtree until the first node whose left child is P, or by finding a node whose right child is P.

The following algorithm performs the required operation.

D1. [Find extremes of subtree.]
    Set L <- P.
    While LLINK(L) ≠ Λ, set L <- LLINK(L).

    Set R <- P.
    While RTAG(R) = 0, set R <- RLINK(R).

D2. [Find predecessor and successor.]
    Set A <- RLINK(L).
    Set B <- RLINK(R).

D3. [Locate parent of P.]
    Set F <- B.
    While F ≠ LOC(T) and LLINK(F) ≠ P, repeat:
         if RTAG(F) = 0 and RLINK(F) = P, go to D4;
         set F <- RLINK(F).

D4. [Detach subtree.]
    If F = LOC(T), set T <- Λ.
    Else if LLINK(F) = P, set LLINK(F) <- Λ.
    Else begin
         set RTAG(F) <- 1;
         set RLINK(F) <- B;
    end.

    If A ≠ LOC(T) and RTAG(A) = 1 and RLINK(A) = L,
         set RLINK(A) <- B.

D5. [Attach subtree to HEAD.]
    Set LLINK(HEAD) <- P.

    Set RLINK(R) <- HEAD.

    If LLINK(L) = Λ, do nothing.

A more compact description of the final attachment is possible. Since HEAD represents an empty tree, making P its root requires only

LLINK(HEAD) <- P;
RLINK(R) <- HEAD.

where R is the rightmost node of the subtree. All internal threads of the subtree remain correct, and the thread from its rightmost node must now point to the new list head.

To verify correctness, consider the inorder sequence of the original tree. The nodes of the subtree rooted at P form one contiguous block in that sequence. The leftmost node L is the first element of the block and the rightmost node R is the last. Their threads identify the adjacent nodes outside the block, namely the predecessor A and successor B. Replacing the thread from A to L by a thread from A to B removes the entire block from the inorder chain. The modification of the parent link removes the unique structural connection between the subtree and the remainder of the tree. Hence the subtree rooted at P is completely detached.

The tree headed by HEAD is initially empty. Setting LLINK(HEAD) <- P makes P its root. Since R is the rightmost node of that tree, changing its thread to HEAD establishes the standard right-threaded termination condition. No other links or threads inside the subtree require alteration, because the relative inorder positions of all nodes of the subtree are unchanged.

Therefore the algorithm removes NODE(P) together with all its subtrees from its original right-threaded tree and attaches the resulting subtree to NODE(HEAD), preserving the right-threaded representation.

$$ \boxed{\text{The subtree rooted at }P\text{ is detached and becomes the entire tree headed by }HEAD.} $$