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


GNU libavl 2.0.1

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

5.9.3.8 Backing Up to the Previous Node

Moving to the previous node is analogous to moving to the next node. The only difference, in fact, is that directions are reversed from left to right.

 
void *
bst_t_prev (struct bst_traverser *trav)
{ struct bst_node *x; assert (trav != NULL); if (trav-&#62;bst_generation != trav-&#62;bst_table-&#62;bst_generation) trav_refresh (trav); x = trav-&#62;bst_node; if (x == NULL)
{ return bst_t_last (trav, trav-&#62;bst_table); }
else if (x-&#62;bst_link[0] != NULL)
{ if (trav-&#62;bst_height >= BST_MAX_HEIGHT)
{ bst_balance (trav-&#62;bst_table); return bst_t_prev (trav); } trav-&#62;bst_stack[trav-&#62;bst_height++] = x; x = x-&#62;bst_link[0]; while (x-&#62;bst_link[1] != NULL)
{ if (trav-&#62;bst_height >= BST_MAX_HEIGHT)
{ bst_balance (trav-&#62;bst_table); return bst_t_prev (trav); } trav-&#62;bst_stack[trav-&#62;bst_height++] = x; x = x-&#62;bst_link[1]; } }
else
{ struct bst_node *y; do
{ if (trav-&#62;bst_height == 0)
{ trav-&#62;bst_node = NULL; return NULL; } y = x; x = trav-&#62;bst_stack[--trav-&#62;bst_height]; }
while (y == x-&#62;bst_link[0]); } trav-&#62;bst_node = x; return x-&#62;bst_data; }
This code is included in @refalso{63


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