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


GNU libavl 2.0.1

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

7.4.1 Step 1: Search

The first thing to do is to search for the point to insert the new node. In a manner similar to AVL deletion, we keep a stack of nodes tracking the path followed to arrive at the insertion point, so that later we can move up the tree in rebalancing.

 
pa[0] = (struct rb_node *) &tree-&#62;rb_root;
da[0] = 0;
k = 1;
for (p = tree-&#62;rb_root; p != NULL; p = p-&#62;rb_link[da[k - 1]]) 
{ int cmp = tree-&#62;rb_compare (item, p-&#62;rb_data, tree-&#62;rb_param); if (cmp == 0) return &p-&#62;rb_data; pa[k] = p; da[k++] = cmp > 0; }
This code is included in @refalso{197


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