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

search

	Buy GNU books!

GNU libavl 2.0.1

9.5 Deletion

Deletion from a TAVL tree can be accomplished by combining our knowledge about AVL trees and threaded trees. From one perspective, we add rebalancing to TBST deletion. From the other perspective, we add thread handling to AVL tree deletion.

The function outline is about the same as usual. We do add a helper function for finding the parent of a TAVL node:

<@xref{\NODE\, , Find parent of a TBST node; tbst =>.> tavl,327} void * tavl_delete (struct tavl_table *tree, const void *item) { struct tavl_node *p; /* Traverses tree to find node to delete. */ struct tavl_node *q; /* Parent of p. */ int dir; /* Index into q->tavl_link[] to get p. */ int cmp; /* Result of comparison between item and p. */ assert (tree != NULL && item != NULL); <@xref{\NODE\, , Step 1: Search TAVL tree for item to delete.>,312} <@xref{\NODE\, , Step 2: Delete item from TAVL tree.>,313} <@xref{\NODE\, , Steps 3 and 4: Update balance factors and rebalance after TAVL deletion.>,318} }

This code is included in @refalso{300

9.5.1 Step 1: Search
9.5.2 Step 2: Delete
9.5.3 Step 3: Update Balance Factors
9.5.4 Step 4: Rebalance
9.5.5 Symmetric Case
9.5.6 Finding the Parent of a Node