8.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:

311. <TAVL item deletion function 311> =
<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);

  <Step 1: Search TAVL tree for item to delete 312>
  <Step 2: Delete item from TAVL tree 313>
  <Steps 3 and 4: Update balance factors and rebalance after TAVL deletion 318>
}

This code is included in 300.

• Deleting a TAVL Node Step 1 - Search
• Deleting a TAVL Node Step 2 - Delete
• Deleting a TAVL Node Step 3 - Update
• Deleting a TAVL Node Step 4 - Rebalance
• TAVL Deletion Symmetric Case
• Finding the Parent of a TBST Node