5.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.

167. <Step 1: Search AVL tree for item to delete 167> =
k = 0;
p = (struct avl_node *) &tree->avl_root;
for (cmp = -1; cmp != 0; 
     cmp = tree->avl_compare (item, p->avl_data, tree->avl_param)) 
  {
    int dir = cmp > 0;

    pa[k] = p;
    da[k++] = dir;

    p = p->avl_link[dir];
    if (p == NULL)
      return NULL;
  }
item = p->avl_data;

This code is included in 166 and 222.