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

GNU libavl 2.0.1

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

13.3 Insertion

Insertion is, as usual, one of the operations that must be newly implemented for our new type of tree. There is nothing surprising in the function's outline:

 
void **
rtrb_probe (struct rtrb_table *tree, void *item) 
{
  struct rtrb_node *pa[RTRB_MAX_HEIGHT]; /* Nodes on stack. */
  unsigned char da[RTRB_MAX_HEIGHT];   /* Directions moved from stack nodes. */
  int k;                               /* Stack height. */
  struct rtrb_node *p; /* Current node in search. */
  struct rtrb_node *n; /* New node. */
  int dir;             /* Side of p on which p is located. */
  assert (tree != NULL && item != NULL);
  &#60;@xref{\NODE\, , Step 1: Search RTRB tree for insertion point.&#62;,457}
  &#60;@xref{\NODE\, , Step 2: Insert RTRB node.&#62;,458}
  &#60;@xref{\NODE\, , Step 3: Rebalance after RTRB insertion.&#62;,459}
  return &n-&#62;rtrb_data;
}
This code is included in @refalso{455

13.3.1 Steps 1 and 2: Search and Insert  
13.3.2 Step 3: Rebalance  


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