5.4.1 Step 1: Search |

The search step is an extended version of the corresponding code for
BST insertion in <BST item insertion function 33>. The earlier code
had only two variables to maintain: the current node the direction to
descend from *p*. The AVL code does this, but it maintains some other
variables, too. During each iteration of the **for** loop, *p* is the
node we are examining, *q* is *p*'s parent, *y* is the most recently
examined node with nonzero balance factor, *z* is *y*'s parent, and
elements 0...*k* - 1 of array *da*[] record each direction
descended, starting from *z*, in order to arrive at *p*. The purposes
for many of these variables are surely uncertain right now, but they
will become clear later.

150. <Step 1: Search AVL tree for insertion point 150> =z= (structavl_node*) &tree->avl_root;y=tree->avl_root;dir= 0;for(q=z,p=y;p!=NULL;q=p,p=p->avl_link[dir])

{intcmp=tree->avl_compare(item,p->avl_data,tree->avl_param);if(cmp== 0)return&p->avl_data;if(p->avl_balance!= 0)z=q,y=p,k= 0;da[k++] =dir=cmp> 0; }

This code is included in 148.