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


GNU libavl 2.0.1

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

9.4.1 Steps 1 and 2: Search and Insert

The first step is a lot like the unthreaded AVL version in &#60;@xref{\NODE\, , \TITLE\}.&#62;{Step 1: Search AVL tree for insertion point,148}. There is an unfortunate special case for an empty tree, because a null pointer for tavl_root indicates an empty tree but in a nonempty tree we must seek a thread link. After we're done, p, not q as before, is the node below which a new node should be inserted, because the test for stepping outside the binary tree now comes before advancing p.

 
z = (struct tavl_node *) &tree-&#62;tavl_root;
y = tree-&#62;tavl_root;
if (y != NULL) 
{ for (q = z, p = y; ; q = p, p = p-&#62;tavl_link[dir])
{ int cmp = tree-&#62;tavl_compare (item, p-&#62;tavl_data, tree-&#62;tavl_param); if (cmp == 0) return &p-&#62;tavl_data; if (p-&#62;tavl_balance != 0) z = q, y = p, k = 0; da[k++] = dir = cmp > 0; if (p-&#62;tavl_tag[dir] == TAVL_THREAD) break; } }
else
{ p = z; dir = 0; }
This code is included in @refalso{301

The insertion adds to the TBST code by setting the balance factor of the new node and handling the first insertion into an empty tree as a special case:

 
&#60;@xref{\NODE\, , Step 2: Insert TBST node; tbst =>.&#62; tavl,256}
n-&#62;tavl_balance = 0;
if (tree-&#62;tavl_root == n)
  return &n-&#62;tavl_data;
This code is included in @refalso{301


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