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


GNU libavl 2.0.1

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

16.4 Deletion

The RB item deletion algorithm needs the same kind of changes to handle parent pointers that the RB item insertion algorithm did. We can reuse the code from PBST trees for finding the node to delete. The rest of the code will be presented in the following sections.

 
void *
prb_delete (struct prb_table *tree, const void *item)
{ struct prb_node *p; /* Node to delete. */ struct prb_node *q; /* Parent of p. */ struct prb_node *f; /* Node at which we are rebalancing. */ int dir; /* Side of q on which p is a child; side of f from which node was deleted. */ assert (tree != NULL && item != NULL); &#60;@xref{\NODE\, , Step 1: Find PBST node to delete; pbst =>.&#62; prb,494} &#60;@xref{\NODE\, , Step 2: Delete item from PRB tree.&#62;,567} &#60;@xref{\NODE\, , Step 3: Rebalance tree after PRB deletion.&#62;,571} &#60;@xref{\NODE\, , Step 4: Finish up after PRB deletion.&#62;,577} }
This code is included in @refalso{554

See also: [ Cormen 1990], section 14.4.

16.4.1 Step 2: Delete  
16.4.2 Step 3: Rebalance  
16.4.3 Step 4: Finish Up  
16.4.4 Symmetric Case  


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