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 = (struct avl_node *) &tree->avl_root;
y = tree->avl_root;
dir = 0;
for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) 
  {
    int cmp = 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.