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

search

	Buy GNU books!

GNU libavl 2.0.1

6.5 Deletion

Deletion in an AVL tree is remarkably similar to insertion. The steps that we go through are analogous:

1. Search for the item to delete.

2. Delete the item.

3. Update balance factors.

4. Rebalance the tree, if necessary.

5. Finish up and return.

The main difference is that, after a deletion, we may have to rebalance at more than one level of a tree, starting from the bottom up. This is a bit painful, because it means that we have to keep track of all the nodes that we visit as we search for the node to delete, so that we can then move back up the tree. The actual updating of balance factors and rebalancing steps are similar to those used for insertion.

The following sections cover deletion from an AVL tree in detail. Before we get started, here's an outline of the function.

void * avl_delete (struct avl_table *tree, const void *item) { /* Stack of nodes. */ struct avl_node *pa[AVL_MAX_HEIGHT]; /* Nodes. */ unsigned char da[AVL_MAX_HEIGHT]; /* avl_link[] indexes. */ int k; /* Stack pointer. */ struct avl_node *p; /* Traverses tree to find node to delete. */ 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.>,165} <@xref{\NODE\, , Step 2: Delete item from AVL tree.>,166} <@xref{\NODE\, , Steps 3--4: Update balance factors and rebalance after AVL deletion.>,171} <@xref{\NODE\, , Step 5: Finish up and return after AVL deletion.>,176} }

This code is included in @refalso{145

See also: [ Knuth 1998b], pages 473--474; [ Pfaff 1998].

6.5.1 Step 1: Search
6.5.2 Step 2: Delete
6.5.3 Step 3: Update Balance Factors
6.5.4 Step 4: Rebalance
6.5.5 Step 5: Finish Up
6.5.6 Symmetric Case