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

search

	Buy GNU books!

GNU libavl 2.0.1

8.5 Search

In searching a TBST we just have to be careful to distinguish threads from child pointers. If we hit a thread link, then we've run off the bottom of the tree and the search is unsuccessful. Other that that, a search in a TBST works the same as in any other binary search tree.

void * tbst_find (const struct tbst_table *tree, const void *item) { const struct tbst_node *p; assert (tree != NULL && item != NULL); p = tree->tbst_root; if (p == NULL) return NULL; for (;;) { int cmp, dir; cmp = tree->tbst_compare (item, p->tbst_data, tree->tbst_param); if (cmp == 0) return p->tbst_data; dir = cmp > 0; if (p->tbst_tag[dir] == TBST_CHILD) p = p->tbst_link[dir]; else return NULL; } }

This code is included in @refalso{251