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


GNU libavl 2.0.1

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

11.3 Search

A right-threaded tree is inherently asymmetric, so many of the algorithms on it will necessarily be asymmetric as well. The search function is the simplest demonstration of this. For descent to the left, we test for a null left child with rtbst_link[0]; for descent to the right, we test for a right thread with rtbst_rtag. Otherwise, the code is familiar:

 
void *
rtbst_find (const struct rtbst_table *tree, const void *item)
{ const struct rtbst_node *p; int dir; assert (tree != NULL && item != NULL); if (tree-&#62;rtbst_root == NULL) return NULL; for (p = tree-&#62;rtbst_root; ; p = p-&#62;rtbst_link[dir])
{ int cmp = tree-&#62;rtbst_compare (item, p-&#62;rtbst_data, tree-&#62;rtbst_param); if (cmp == 0) return p-&#62;rtbst_data; dir = cmp > 0; if (dir == 0)
{ if (p-&#62;rtbst_link[0] == NULL) return NULL; }
else /* dir == 1 */
{ if (p-&#62;rtbst_rtag == RTBST_THREAD) return NULL; } } }
This code is included in @refalso{375


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