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


GNU libavl 2.0.1

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

14.3 Insertion

The only difference between this code and &#60;@xref{\NODE\, , \TITLE\}.&#62;{BST item insertion function,32} is that we set n's parent pointer after insertion.

 
void **
pbst_probe (struct pbst_table *tree, void *item)
{ struct pbst_node *p, *q; /* Current node in search and its parent. */ int dir; /* Side of q on which p is located. */ struct pbst_node *n; /* Newly inserted node. */ assert (tree != NULL && item != NULL); &#60;@xref{\NODE\, , Step 1: Search PBST tree for insertion point.&#62;,491} &#60;@xref{\NODE\, , Step 2: Insert PBST node.&#62;,492} return &n-&#62;pbst_data; }
This code is included in @refalso{489

 
for (q = NULL, p = tree-&#62;pbst_root; p != NULL; q = p, p = p-&#62;pbst_link[dir]) 
{ int cmp = tree-&#62;pbst_compare (item, p-&#62;pbst_data, tree-&#62;pbst_param); if (cmp == 0) return &p-&#62;pbst_data; dir = cmp > 0; }
This code is included in @refalso{490

 
n = tree-&#62;pbst_alloc-&#62;libavl_malloc (tree-&#62;pbst_alloc, sizeof *p);
if (n == NULL)
  return NULL;
tree-&#62;pbst_count++;
n-&#62;pbst_link[0] = n-&#62;pbst_link[1] = NULL;
n-&#62;pbst_parent = q;
n-&#62;pbst_data = item;
if (q != NULL)
  q-&#62;pbst_link[dir] = n;
else 
tree-&#62;pbst_root = n;
This code is included in @refalso{490

See also: [ Cormen 1990], section 13.3.


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