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


GNU libavl 2.0.1

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

13.3.1 Steps 1 and 2: Search and Insert

The process of search and insertion proceeds as usual. Stack pa[], with pa[k - 1] at top of stack, records the parents of the node p currently under consideration, with corresponding stack da[] indicating the direction moved. We use the standard code for insertion into an RTBST. When the loop exits, p is the node under which a new node should be inserted on side dir.

 
da[0] = 0;
pa[0] = (struct rtrb_node *) &tree-&#62;rtrb_root;
k = 1;
if (tree-&#62;rtrb_root != NULL)
  for (p = tree-&#62;rtrb_root; ; p = p-&#62;rtrb_link[dir]) 
{ int cmp = tree-&#62;rtrb_compare (item, p-&#62;rtrb_data, tree-&#62;rtrb_param); if (cmp == 0) return &p-&#62;rtrb_data; pa[k] = p; da[k++] = dir = cmp > 0; if (dir == 0)
{ if (p-&#62;rtrb_link[0] == NULL) break; }
else /* dir == 1 */
{ if (p-&#62;rtrb_rtag == RTRB_THREAD) break; } } else
{ p = (struct rtrb_node *) &tree-&#62;rtrb_root; dir = 0; }
This code is included in @refalso{456

 
n = tree-&#62;rtrb_alloc-&#62;libavl_malloc (tree-&#62;rtrb_alloc, sizeof *n);
if (n == NULL)
  return NULL;
tree-&#62;rtrb_count++;
n-&#62;rtrb_data = item;
n-&#62;rtrb_link[0] = NULL;
if (dir == 0) 
{ if (tree-&#62;rtrb_root != NULL) n-&#62;rtrb_link[1] = p; else
n-&#62;rtrb_link[1] = NULL; }
else /* dir == 1 */
{ p-&#62;rtrb_rtag = RTRB_CHILD; n-&#62;rtrb_link[1] = p-&#62;rtrb_link[1]; } n-&#62;rtrb_rtag = RTRB_THREAD; n-&#62;rtrb_color = RTRB_RED; p-&#62;rtrb_link[dir] = n;
This code is included in @refalso{456


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