www.delorie.com/gnu/docs/avl/libavl_266.html

search

	Buy GNU books!

GNU libavl 2.0.1

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); <@xref{\NODE\, , Step 1: Find PBST node to delete; pbst =>.> prb,494} <@xref{\NODE\, , Step 2: Delete item from PRB tree.>,567} <@xref{\NODE\, , Step 3: Rebalance tree after PRB deletion.>,571} <@xref{\NODE\, , Step 4: Finish up after PRB deletion.>,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