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:

313. <TAVL item deletion function 313> =
<Find parent of a TBST node; tbst => tavl 329>

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 314>
  <Step 2: Delete item from TAVL tree 315>
  <Steps 3 and 4: Update balance factors and rebalance after TAVL deletion 320>
}

This code is included in 302.

• 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