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


GNU libavl 2.0.1

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

15.4 Insertion

The same basic algorithm has been used for insertion in all of our AVL tree variants so far. (In fact, all three functions share the same set of local variables.) For PAVL trees, we will slightly modify our approach. In particular, until now we have cached comparison results on the way down in order to quickly adjust balance factors after the insertion. Parent pointers let us avoid this caching but still efficiently update balance factors.

Before we look closer, here is the function's outline:

 
void **
pavl_probe (struct pavl_table *tree, void *item)
{ struct pavl_node *y; /* Top node to update balance factor, and parent. */ struct pavl_node *p, *q; /* Iterator, and parent. */ struct pavl_node *n; /* Newly inserted node. */ struct pavl_node *w; /* New root of rebalanced subtree. */ int dir; /* Direction to descend. */ assert (tree != NULL && item != NULL); &#60;@xref{\NODE\, , Step 1: Search PAVL tree for insertion point.&#62;,524} &#60;@xref{\NODE\, , Step 2: Insert PAVL node.&#62;,525} &#60;@xref{\NODE\, , Step 3: Update balance factors after PAVL insertion.&#62;,526} &#60;@xref{\NODE\, , Step 4: Rebalance after PAVL insertion.&#62;,527} }
This code is included in @refalso{522

15.4.1 Steps 1 and 2: Search and Insert  
15.4.2 Step 3: Update Balance Factors  
15.4.3 Step 4: Rebalance  
15.4.4 Symmetric Case  


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