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


GNU libavl 2.0.1

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

5.6 Search

Searching a binary search tree works just the same way as it did before when we were doing it inside an array. We can implement bst_find() immediately:

 
void *
bst_find (const struct bst_table *tree, const void *item)
{ const struct bst_node *p; assert (tree != NULL && item != NULL); for (p = tree-&#62;bst_root; p != NULL; )
{ int cmp = tree-&#62;bst_compare (item, p-&#62;bst_data, tree-&#62;bst_param); if (cmp < 0)
p = p-&#62;bst_link[0]; else if (cmp > 0)
p = p-&#62;bst_link[1]; else /* cmp == 0 */
return p-&#62;bst_data; } return NULL; }
This code is included in @refalso{29

See also: [ Knuth 1998b], section 6.2.2; [ Cormen 1990], section 13.2; [ Kernighan 1988], section 3.3; [ Bentley 2000], chapters 4 and 5, section 9.3, appendix 1; [ Sedgewick 1998], program 12.7.


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