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

search

	Buy GNU books!

GNU libavl 2.0.1

7.5 Deletion

The process of deletion from an RB tree is very much in line with the other algorithms for balanced trees that we've looked at already. This time, the steps are:

1. Search for the item to delete.

2. Delete the item.

3. Rebalance the tree as necessary.

4. Finish up and return.

Here's an outline of the code. Step 1 is already done for us, because we can reuse the search code from AVL deletion.

void * rb_delete (struct rb_table *tree, const void *item) { struct rb_node *pa[RB_MAX_HEIGHT]; /* Nodes on stack. */ unsigned char da[RB_MAX_HEIGHT]; /* Directions moved from stack nodes. */ int k; /* Stack height. */ struct rb_node *p; /* The node to delete, or a node part way to it. */ int cmp; /* Result of comparison between item and p. */ assert (tree != NULL && item != NULL); <@xref{\NODE\, , Step 1: Search AVL tree for item to delete; avl =>.> rb,165} <@xref{\NODE\, , Step 2: Delete item from RB tree.>,221} <@xref{\NODE\, , Step 3: Rebalance tree after RB deletion.>,225} <@xref{\NODE\, , Step 4: Finish up after RB deletion.>,232} }

This code is included in @refalso{196

See also: [ Cormen 1990], section 14.4.

7.5.1 Step 2: Delete
7.5.2 Step 3: Rebalance
7.5.3 Step 4: Finish Up
7.5.4 Symmetric Case