www.delorie.com/gnu/docs/avl/libavl_42.html

search

	Buy GNU books!

GNU libavl 2.0.1

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.