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


GNU libavl 2.0.1

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

16.3 Insertion

Inserting into a red-black tree is a problem whose form of solution should by now be familiar to the reader. We must now update parent pointers, of course, but the major difference here is that it is fast and easy to find the parent of any given node, eliminating any need for a stack.

Here's the function outline. The code for finding the insertion point is taken directly from the PBST code:

 
void **
prb_probe (struct prb_table *tree, void *item)
{ struct prb_node *p; /* Traverses tree looking for insertion point. */ struct prb_node *q; /* Parent of p; node at which we are rebalancing. */ struct prb_node *n; /* Newly inserted node. */ int dir; /* Side of q on which n is inserted. */ assert (tree != NULL && item != NULL); &#60;@xref{\NODE\, , Step 1: Search PBST tree for insertion point; pbst =>.&#62; prb,491} &#60;@xref{\NODE\, , Step 2: Insert PRB node.&#62;,556} &#60;@xref{\NODE\, , Step 3: Rebalance after PRB insertion.&#62;,557} return &n-&#62;prb_data; }
This code is included in @refalso{554

See also: [ Cormen 1990], section 14.3.

16.3.1 Step 2: Insert  
16.3.2 Step 3: Rebalance  
16.3.3 Symmetric Case  


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