www.delorie.com/gnu/docs/avl/libavl_197.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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():
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->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; ) |
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->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; |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |