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

GNU libavl 2.0.1

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

6.5.1 Step 1: Search

The only difference between this search and an ordinary search in a BST is that we have to keep track of the nodes above the one we're deleting. We do this by pushing them onto the stack defined above. Each iteration through the loop compares item to p's data, pushes the node onto the stack, moves down in the proper direction. The first trip through the loop is something of an exception: we hard-code the comparison result to -1 so that the pseudo-root node is always the topmost node on the stack. When we find a match, we set item to the actual data item found, so that we can return it later.

k = 0;
p = (struct avl_node *) &tree-&#62;avl_root;
for (cmp = -1; cmp != 0; 
cmp = tree-&#62;avl_compare (item, p-&#62;avl_data, tree-&#62;avl_param))
{ int dir = cmp > 0; pa[k] = p; da[k++] = dir; p = p-&#62;avl_link[dir]; if (p == NULL) return NULL; } item = p-&#62;avl_data;
This code is included in @refalso{164

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