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


GNU libavl 2.0.1

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

12.4.1 Steps 1--2: Search and Insert

The basic insertion step itself follows the same steps as &#60;@xref{\NODE\, , \TITLE\}.&#62;{RTBST item insertion function,377} does for a plain RTBST. We do keep track of the directions moved on stack da[] and the last-seen node with nonzero balance factor, in the same way as &#60;@xref{\NODE\, , \TITLE\}.&#62;{Step 1: Search AVL tree for insertion point,148} for unthreaded AVL trees.

 
z = (struct rtavl_node *) &tree-&#62;rtavl_root;
y = tree-&#62;rtavl_root;
if (tree-&#62;rtavl_root != NULL)
  for (q = z, p = y; ; q = p, p = p-&#62;rtavl_link[dir]) 
{ int cmp = tree-&#62;rtavl_compare (item, p-&#62;rtavl_data, tree-&#62;rtavl_param); if (cmp == 0) return &p-&#62;rtavl_data; if (p-&#62;rtavl_balance != 0) z = q, y = p, k = 0; da[k++] = dir = cmp > 0; if (dir == 0)
{ if (p-&#62;rtavl_link[0] == NULL) break; }
else /* dir == 1 */
{ if (p-&#62;rtavl_rtag == RTAVL_THREAD) break; } } else
{ p = (struct rtavl_node *) &tree-&#62;rtavl_root; dir = 0; }
This code is included in @refalso{419

 
n = tree-&#62;rtavl_alloc-&#62;libavl_malloc (tree-&#62;rtavl_alloc, sizeof *n);
if (n == NULL)
  return NULL;
tree-&#62;rtavl_count++;
n-&#62;rtavl_data = item;
n-&#62;rtavl_link[0] = NULL;
if (dir == 0)
  n-&#62;rtavl_link[1] = p;
else /* dir == 1 */ 
{ p-&#62;rtavl_rtag = RTAVL_CHILD; n-&#62;rtavl_link[1] = p-&#62;rtavl_link[1]; } n-&#62;rtavl_rtag = RTAVL_THREAD; n-&#62;rtavl_balance = 0; p-&#62;rtavl_link[dir] = n; if (y == NULL)
{ n-&#62;rtavl_link[1] = NULL; return &n-&#62;rtavl_data; }
This code is included in @refalso{419


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