www.delorie.com/gnu/docs/avl/libavl_197.html   search  
Buy GNU books!

GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11.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():

void *
rtbst_t_prev (struct rtbst_traverser *trav)
{ assert (trav != NULL); if (trav-&#62;rtbst_node == NULL) return rtbst_t_last (trav, trav-&#62;rtbst_table); else if (trav-&#62;rtbst_node-&#62;rtbst_link[0] == NULL)
{ &#60;@xref{\NODE\, , Find predecessor of RTBST node with no left child.&#62;,401} }
{ &#60;@xref{\NODE\, , Find predecessor of RTBST node with left child.&#62;,402} } }
This code is included in @refalso{395

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 section 5.9.3 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:

rtbst_comparison_func *cmp = trav-&#62;rtbst_table-&#62;rtbst_compare;
void *param = trav-&#62;rtbst_table-&#62;rtbst_param;
struct rtbst_node *node = trav-&#62;rtbst_node;
struct rtbst_node *i;
trav-&#62;rtbst_node = NULL;
for (i = trav-&#62;rtbst_table-&#62;rtbst_root; i != node; ) 
{ int dir = cmp (node-&#62;rtbst_data, i-&#62;rtbst_data, param) > 0; if (dir == 1) trav-&#62;rtbst_node = i; i = i-&#62;rtbst_link[dir]; } return trav-&#62;rtbst_node != NULL ? trav-&#62;rtbst_node-&#62;rtbst_data : NULL;
This code is included in @refalso{400

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:

trav-&#62;rtbst_node = trav-&#62;rtbst_node-&#62;rtbst_link[0];
while (trav-&#62;rtbst_node-&#62;rtbst_rtag == RTBST_CHILD)
  trav-&#62;rtbst_node = trav-&#62;rtbst_node-&#62;rtbst_link[1];
return trav-&#62;rtbst_node-&#62;rtbst_data;
This code is included in @refalso{400

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003