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


GNU libavl 2.0.1

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

11.4 Insertion

Regardless of the kind of binary tree we're dealing with, adding a new node requires setting three pointer fields: the parent pointer and the two child pointers of the new node. On the other hand, we do save a tiny bit on tags: we set either 1 or 2 tags here as opposed to a constant of 3 in &#60;@xref{\NODE\, , TBST item insertion function.&#62;,254}.

Here is the outline:

 
void **
rtbst_probe (struct rtbst_table *tree, void *item)
{ struct rtbst_node *p; /* Current node in search. */ int dir; /* Side of p on which to insert the new node. */ struct rtbst_node *n; /* New node. */ &#60;@xref{\NODE\, , Step 1: Search RTBST for insertion point.&#62;,378} &#60;@xref{\NODE\, , Step 2: Insert new node into RTBST tree.&#62;,379} }
This code is included in @refalso{375

The code to search for the insertion point is not unusual:

 
if (tree-&#62;rtbst_root != NULL)
  for (p = tree-&#62;rtbst_root; ; p = p-&#62;rtbst_link[dir]) 
{ int cmp = tree-&#62;rtbst_compare (item, p-&#62;rtbst_data, tree-&#62;rtbst_param); if (cmp == 0) return &p-&#62;rtbst_data; dir = cmp > 0; if (dir == 0)
{ if (p-&#62;rtbst_link[0] == NULL) break; }
else /* dir == 1 */
{ if (p-&#62;rtbst_rtag == RTBST_THREAD) break; } } else
{ p = (struct rtbst_node *) &tree-&#62;rtbst_root; dir = 0; }
This code is included in @refalso{377

Now for the insertion code. An insertion to the left of a node p in a right-threaded tree replaces the left link by the new node n. The new node in turn has a null left child and a right thread pointing back to p:

rtbstins

An insertion to the right of p replaces the right thread by the new child node n. The new node has a null left child and a right thread that points where p's right thread formerly pointed:

rtbstins2

We can handle both of these cases in one code segment. The difference is in the treatment of n's right child and p's right tag. Insertion into an empty tree is handled as a special case as well:

 
n = tree-&#62;rtbst_alloc-&#62;libavl_malloc (tree-&#62;rtbst_alloc, sizeof *n);
if (n == NULL)
  return NULL;
tree-&#62;rtbst_count++;
n-&#62;rtbst_data = item;
n-&#62;rtbst_link[0] = NULL;
if (dir == 0) 
{ if (tree-&#62;rtbst_root != NULL) n-&#62;rtbst_link[1] = p; else
n-&#62;rtbst_link[1] = NULL; }
else /* dir == 1 */
{ p-&#62;rtbst_rtag = RTBST_CHILD; n-&#62;rtbst_link[1] = p-&#62;rtbst_link[1]; } n-&#62;rtbst_rtag = RTBST_THREAD; p-&#62;rtbst_link[dir] = n; return &n-&#62;rtbst_data;
This code is included in @refalso{377


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

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