10.6.5 Backing Up to the Previous Node |

Moving an RTBST traverser backward has the same cases as in the other
ways of finding an inorder predecessor that we've already discussed.
The two main cases are distinguished on whether the current item has a
left child; the third case comes up when there is no current item,
implemented simply by delegation to *rtbst_t_last*():

402. <RTBST traverser back up function 402> =void*rtbst_t_prev(structrtbst_traverser*trav)

{assert(trav!=NULL);if(trav->rtbst_node==NULL)returnrtbst_t_last(trav,trav->rtbst_table);elseif(trav->rtbst_node->rtbst_link[0] ==NULL)

{ <Find predecessor of RTBST node with no left child 403> }

else

{ <Find predecessor of RTBST node with left child 404> } }

This code is included in 397.

The novel case is where the node *p* whose predecessor we want has no
left child. In this case, we use a modified version of the algorithm
originally specified for finding a node's successor in an unthreaded
tree (see Better Iterative Traversal). We take the idea of
moving up until we've moved up to the left, and turn it upside down (to
avoid need for a parent stack) and reverse it (to find the predecessor
instead of the successor).

The idea here is to trace *p*'s entire direct ancestral line. Starting
from the root of the tree, we repeatedly compare each node's data with
*p*'s and use the result to move downward, until we encounter node *p*
itself. Each time we move down from a node *x* to its right child, we
record *x* as the potential predecessor of *p*. When we finally arrive
at *p*, the last node so selected is the actual predecessor, or if none
was selected then *p* is the least node in the tree and we select the
null item as its predecessor.

Consider this algorithm in the context of the tree shown here:

To find the predecessor of node 8, we trace the path from the root down to it: 3-9-5-7-8. The last time we move down to the right is from 7 to 8, so 7 is node 8's predecessor. To find the predecessor of node 6, we trace the path 3-9-5-7-6 and notice that we last move down to the right from 5 to 7, so 5 is node 6's predecessor. Finally, node 0 has the null item as its predecessor because path 3-1-0 does not involve any rightward movement.

Here is the code to implement this case:

403. <Find predecessor of RTBST node with no left child 403> =rtbst_comparison_func*cmp=trav->rtbst_table->rtbst_compare;void*param=trav->rtbst_table->rtbst_param;structrtbst_node*node=trav->rtbst_node;structrtbst_node*i;trav->rtbst_node=NULL;for(i=trav->rtbst_table->rtbst_root;i!=node; )

{intdir=cmp(node->rtbst_data,i->rtbst_data,param) > 0;if(dir== 1)trav->rtbst_node=i;i=i->rtbst_link[dir]; }returntrav->rtbst_node!=NULL?trav->rtbst_node->rtbst_data:NULL;

This code is included in 402.

The other case, where the node whose predecessor we want has a left child, is nothing new. We just find the largest node in the node's left subtree:

404. <Find predecessor of RTBST node with left child 404> =trav->rtbst_node=trav->rtbst_node->rtbst_link[0];while(trav->rtbst_node->rtbst_rtag==RTBST_CHILD)trav->rtbst_node=trav->rtbst_node->rtbst_link[1];returntrav->rtbst_node->rtbst_data;

This code is included in 402.