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

search

	Buy GNU books!

GNU libavl 2.0.1

12.5.1 Step 1: Search

There's nothing new in searching an RTAVL tree for a node to delete. We use p to search the tree, and push its chain of parent nodes onto stack pa[] along with the directions da[] moved down from them, including the pseudo-root node at the top.

k = 1; da[0] = 0; pa[0] = (struct rtavl_node *) &tree->rtavl_root; p = tree->rtavl_root; if (p == NULL) return NULL; for (;;) { int cmp, dir; cmp = tree->rtavl_compare (item, p->rtavl_data, tree->rtavl_param); if (cmp == 0) break; dir = cmp > 0; if (dir == 0) { if (p->rtavl_link[0] == NULL) return NULL; } else /* dir == 1 */ { if (p->rtavl_rtag == RTAVL_THREAD) return NULL; } pa[k] = p; da[k++] = dir; p = p->rtavl_link[dir]; } tree->rtavl_count--; item = p->rtavl_data;

This code is included in @refalso{429