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 (struct rtbst_traverser *trav) 
{
  assert (trav != NULL);

  if (trav->rtbst_node == NULL)
    return rtbst_t_last (trav, trav->rtbst_table);
  else if (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;
struct rtbst_node *node = trav->rtbst_node;
struct rtbst_node *i;

trav->rtbst_node = NULL;
for (i = trav->rtbst_table->rtbst_root; i != node; ) 
  {
    int dir = cmp (node->rtbst_data, i->rtbst_data, param) > 0;
    if (dir == 1)
      trav->rtbst_node = i;
    i = i->rtbst_link[dir];
  }

return trav->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];
return trav->rtbst_node->rtbst_data;

This code is included in 402.