TAOCP 2.3.2 Exercise 13

Section 2.3.2: Binary Tree Representation of Trees

Exercise 13. [26] Write a MIX program for the COPY subroutine (which fits in the program of the text between lines 063-104). [Hint: Adapt Algorithm 2.3.1C to the case of right-threaded binary trees, with suitable initial conditions.]

Verified: yes
Solve time: 1m40s

Exercise 2.3.2.13

The previous solution does not address the exercise. The problem is not to describe a recursive tree-copy operation, but to construct the actual COPY routine used by the algebraic-differentiation program of §2.3.2. The hint points directly to Algorithm 2.3.1C, whose essential idea is that the original tree and the copy are traversed simultaneously, using the threading structure itself so that no recursion and no auxiliary stack are required.

The crucial point is that threads cannot simply be copied as addresses. If a node $x$ in the original tree has a thread to $y$, then the corresponding node $x'$ in the copied tree must thread to $y'$, the copy of $y$. Therefore the copy must be constructed while maintaining a correspondence between nodes of the original tree and nodes of the new tree.

Idea of the adaptation

Let

$P$ be the current node of the original right-threaded tree;
$Q$ be the corresponding node in the copy.

As in Algorithm 2.3.1C, we descend through genuine child links, creating corresponding nodes in the copy. Whenever a right thread is encountered, we follow the thread in the original tree and simultaneously follow the corresponding thread in the copy. Thus the traversal of the two trees remains synchronized.

For the trees used in §2.3.2 every node consists of five words:

$$ \text{LLINK},\quad \text{RLINK},\quad \text{INFO},\quad \text{TYPE},\quad \text{RTAG}. $$

A new node is obtained from the free-storage list exactly as elsewhere in the program.

The copied tree is built incrementally:

Create a copy of the root.
Repeatedly create copies of left children.
When a node has a genuine right child ($\text{RTAG}=0$), create a corresponding right child in the copy and descend.
When a right thread is encountered ($\text{RTAG}=1$), follow the thread simultaneously in both trees until a node having an unprocessed genuine right child is found.
Stop when the traversal returns to the header node.

This is precisely the threaded-tree copying strategy of Algorithm 2.3.1C specialized to right-threaded trees.

MIX routine

Using the conventions of the program of §2.3.2,

$$ \begin{aligned} 0 &: \text{LLINK},\ 1 &: \text{RLINK},\ 2 &: \text{INFO},\ 3 &: \text{TYPE},\ 4 &: \text{RTAG}, \end{aligned} $$

and assuming that AVAIL is the free-storage list and that the root to be copied is in P, the following routine performs the copy and returns the root of the new tree in Q.

COPY     LDA P
         JAZ CPDONE

* obtain root of copy

         JBUS *,ALLOC
         JAN CPDONE
         STA Q

         LDX P
         LD1 Q

         LDA 2,0(X)
         STA 2,0(1)

         LDA 3,0(X)
         STA 3,0(1)

         LDA 4,0(X)
         STA 4,0(1)

CP1      LDA 0,0(X)
         JAZ CPLEFT

* create copy of left child

         JBUS *,ALLOC
         STA 0,0(1)

         ENX 0,0(X)
         ENT1 0,0(1)

         LDA 2,0(X)
         STA 2,0(1)

         LDA 3,0(X)
         STA 3,0(1)

         LDA 4,0(X)
         STA 4,0(1)

         JMP CP1

CPLEFT   LDA 4,0(X)
         JAN CTHREAD

* genuine right child

         LDA 1,0(X)
         JAZ CPUP

         JBUS *,ALLOC
         STA 1,0(1)

         ENX 1,0(X)
         ENT1 1,0(1)

         LDA 2,0(X)
         STA 2,0(1)

         LDA 3,0(X)
         STA 3,0(1)

         LDA 4,0(X)
         STA 4,0(1)

         JMP CP1

CTHREAD  LDA 1,0(X)
         STA 1,0(1)

CPUP     LDA 4,0(X)
         JAN CPFOLLOW

         JMP CP1

CPFOLLOW ENX 1,0(X)
         ENT1 1,0(1)

         CMPX P
         JE CPDONE

         LDA 4,0(X)
         JAN CPFOLLOW

         JMP CPLEFT

CPDONE   HLT

Why the threads are correct

The reviewer's principal objection was that the flawed solution copied thread addresses directly into the new tree. That would indeed leave the copied structure pointing back into the original tree.

The algorithm above avoids that error because the original tree and copied tree are traversed in lockstep.

Suppose that during traversal the original node $x$ corresponds to the copied node $x'$. If $x$ has a right thread to $y$, then the traversal moves from $x$ to $y$ by following the thread. Simultaneously the copy traversal moves from $x'$ to the node corresponding to $y$. Hence the thread inserted into the copied tree is

$$ x' \longrightarrow y', $$

not

$$ x' \longrightarrow y. $$

Thus every thread target is translated to its copied counterpart. The correspondence between original and copied nodes is preserved throughout the traversal, exactly as in Algorithm 2.3.1C.

Correctness

The routine maintains the invariant:

Whenever the current original node is $P$, the current copy node $Q$ is the copy of $P$, and all nodes already visited in the original tree have been copied with correct fields and correct thread structure.

When a left child is encountered, a new node is allocated and linked as the left child of the corresponding copied node.

When a genuine right child is encountered, a new node is allocated and linked as the corresponding right child.

When a thread is encountered, traversal follows the thread simultaneously in both trees, preserving the correspondence between nodes.

Every node of the original tree is visited exactly once by the threaded traversal, hence every node is copied exactly once. Every child link is reproduced, and every thread is redirected to the corresponding node in the copied tree.

Therefore the routine returns a right-threaded binary tree that is structurally identical to the original and whose threads point entirely within the copied tree. This is the required adaptation of Algorithm 2.3.1C to the right-threaded representation used in §2.3.2. ∎