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

GNU libavl 2.0.1

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

15.5 Deletion

Deletion from a PAVL tree is a natural outgrowth of algorithms we have already implemented. The basic algorithm is the one originally used for plain AVL trees. The search step is taken verbatim from PBST deletion. The deletion step combines PBST and TAVL tree code. Finally, the rebalancing strategy is the same as used in TAVL deletion.

The function outline is below. As noted above, step 1 is borrowed from PBST deletion. The other steps are implemented in the following sections.

 
void *
pavl_delete (struct pavl_table *tree, const void *item) 
{
  struct pavl_node *p; /* Traverses tree to find node to delete. */
  struct pavl_node *q; /* Parent of p. */
  int dir;             /* Side of q on which p is linked. */
  assert (tree != NULL && item != NULL);
  &#60;@xref{\NODE\, , Step 1: Find PBST node to delete; pbst =>.&#62; pavl,494}
  &#60;@xref{\NODE\, , Step 2: Delete item from PAVL tree.&#62;,535}
  &#60;@xref{\NODE\, , Steps 3 and 4: Update balance factors and rebalance after PAVL deletion.&#62;,539}
}
This code is included in @refalso{522

15.5.1 Step 2: Delete  
15.5.2 Step 3: Update Balance Factors  
15.5.3 Step 4: Rebalance  
15.5.4 Symmetric Case  


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