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


GNU libavl 2.0.1

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

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-&#62;rtavl_root;
p = tree-&#62;rtavl_root;
if (p == NULL)
  return NULL;
for (;;) 
{ int cmp, dir; cmp = tree-&#62;rtavl_compare (item, p-&#62;rtavl_data, tree-&#62;rtavl_param); if (cmp == 0) break; dir = cmp > 0; if (dir == 0)
{ if (p-&#62;rtavl_link[0] == NULL) return NULL; }
else /* dir == 1 */
{ if (p-&#62;rtavl_rtag == RTAVL_THREAD) return NULL; } pa[k] = p; da[k++] = dir; p = p-&#62;rtavl_link[dir]; } tree-&#62;rtavl_count--; item = p-&#62;rtavl_data;
This code is included in @refalso{429


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