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


GNU libavl 2.0.1

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

10.3 Insertion

The structure of the insertion routine is predictable:

 
void **
trb_probe (struct trb_table *tree, void *item)
{ struct trb_node *pa[TRB_MAX_HEIGHT]; /* Nodes on stack. */ unsigned char da[TRB_MAX_HEIGHT]; /* Directions moved from stack nodes. */ int k; /* Stack height. */ struct trb_node *p; /* Traverses tree looking for insertion point. */ struct trb_node *n; /* Newly inserted node. */ int dir; /* Side of p on which n is inserted. */ assert (tree != NULL && item != NULL); &#60;@xref{\NODE\, , Step 1: Search TRB tree for insertion point.&#62;,338} &#60;@xref{\NODE\, , Step 2: Insert TRB node.&#62;,339} &#60;@xref{\NODE\, , Step 3: Rebalance after TRB insertion.&#62;,340} return &n-&#62;trb_data; }
This code is included in @refalso{336

10.3.1 Steps 1 and 2: Search and Insert  
10.3.2 Step 3: Rebalance  
10.3.3 Symmetric Case  


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