www.delorie.com/gnu/docs/avl/libavl_94.html | search |
Buy GNU books! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
The search step is an extended version of the corresponding code for BST insertion in <@xref{\NODE\, , BST item insertion function.>,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->avl_root; y = tree->avl_root; dir = 0; for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) |
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |