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


GNU libavl 2.0.1

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

6.4.1 Step 1: Search

The search step is an extended version of the corresponding code for BST insertion in &#60;@xref{\NODE\, , BST item insertion function.&#62;,32}. 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.

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


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