TAOCP 2.3.1 Exercise 32

Section 2.3.1: Traversing Binary Trees

Exercise 32. [21] Suppose that each node of a binary tree has four link fields: LLINK and RLINK, which point to left and right subtrees or \Lambda, as in an unthreaded tree; SUC and PRED, which point to the successor and predecessor of the node in symmetric order. (Thus \operatorname{SUC}(P) = P$ and \operatorname{PRED}(P) = $P. Such a tree contains more information than a threaded tree.) Design an algorithm like Algorithm I for insertion into such a tree.

Verified: yes
Solve time: 57s

Solution

Exercise 31 refers to Algorithm I for insertion into a right-threaded binary tree. In that representation, insertion is performed after locating the parent of the new node and then adjusting a constant number of links and tags. Here each node contains both ordinary tree links and explicit inorder links:

$$ \operatorname{SUC}(P)=P$,\qquad \operatorname{PRED}(P)=$P. $$

Hence insertion into the tree structure and insertion into the inorder doubly linked list can be carried out simultaneously.

Assume that a search has already determined that a new node Q is to be inserted as a child of node P, and that the key in Q is distinct from all keys already present. There are two cases.

If Q is inserted as the left child of P, then in inorder the new node lies immediately before P. Let

$$ R\leftarrow \operatorname{PRED}(P). $$

Before insertion, R and P are consecutive in symmetric order. After insertion the order becomes

$$ R,\ Q,\ P. $$

Therefore

$$ \operatorname{PRED}(Q)=R,\qquad \operatorname{SUC}(Q)=P, $$

and the neighboring nodes must be adjusted to point to Q.

If Q is inserted as the right child of P, then in inorder the new node lies immediately after P. Let

$$ R\leftarrow \operatorname{SUC}(P). $$

Before insertion, P and R are consecutive in symmetric order. After insertion the order becomes

$$ P,\ Q,\ R. $$

Therefore

$$ \operatorname{PRED}(Q)=P,\qquad \operatorname{SUC}(Q)=R, $$

and again the neighboring nodes must be adjusted.

The resulting insertion algorithm is as follows.

Algorithm J (Insertion into a binary tree with SUC and PRED fields).

The search phase is the same as in Algorithm I; upon entry to the insertion phase, P is the parent under which the new node Q is to be attached.

J1. [Left son?] If the new key is less than the key in NODE(P), go to step J2; otherwise go to step J3.

J2. [Insert as left son.]

Set

$$ R\leftarrow \operatorname{PRED}(P). $$

Then perform

$$ \operatorname{LLINK}(P)\leftarrow Q, $$

$$ \operatorname{LLINK}(Q)\leftarrow \Lambda, \qquad \operatorname{RLINK}(Q)\leftarrow \Lambda, $$

$$ \operatorname{PRED}(Q)\leftarrow R, \qquad \operatorname{SUC}(Q)\leftarrow P. $$

Next set

$$ \operatorname{PRED}(P)\leftarrow Q. $$

If $R\neq \Lambda$, set

$$ \operatorname{SUC}(R)\leftarrow Q. $$

Terminate.

J3. [Insert as right son.]

Set

$$ R\leftarrow \operatorname{SUC}(P). $$

Then perform

$$ \operatorname{RLINK}(P)\leftarrow Q, $$

$$ \operatorname{LLINK}(Q)\leftarrow \Lambda, \qquad \operatorname{RLINK}(Q)\leftarrow \Lambda, $$

$$ \operatorname{PRED}(Q)\leftarrow P, \qquad \operatorname{SUC}(Q)\leftarrow R. $$

Next set

$$ \operatorname{SUC}(P)\leftarrow Q. $$

If $R\neq \Lambda$, set

$$ \operatorname{PRED}(R)\leftarrow Q. $$

Terminate.

To prove correctness, consider the left-insertion case. Let $R=\operatorname{PRED}(P)$. Since $R$ is the inorder predecessor of $P$, no node lies between them in symmetric order. The new node is attached as the left child of $P$; therefore, by the definition of inorder traversal, the new node immediately precedes $P$. The assignments

$$ \operatorname{PRED}(Q)=R,\qquad \operatorname{SUC}(Q)=P $$

give Q the correct predecessor and successor. Replacing

$$ \operatorname{SUC}(R)=P $$

$$ \operatorname{SUC}(R)=Q $$

when $R\neq\Lambda$, and replacing

$$ \operatorname{PRED}(P)=R $$

$$ \operatorname{PRED}(P)=Q, $$

preserves the inorder doubly linked list. All other predecessor and successor relations remain unchanged.

The right-insertion case is symmetric. Let $R=\operatorname{SUC}(P)$. Since no node lies between $P$ and $R$ in symmetric order, insertion as the right child of $P$ places the new node immediately after $P$. The assignments

$$ \operatorname{PRED}(Q)=P,\qquad \operatorname{SUC}(Q)=R $$

are therefore correct, and the subsequent updates splice Q between P and R in the inorder list.

Hence after either insertion, the ordinary binary-tree links represent the desired tree, and for every node $X$,

$$ \operatorname{SUC}(X)=X$, \qquad \operatorname{PRED}(X)=$X. $$

This completes the proof.

∎