14.5 Deletion [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

Deletion from a PAVL tree is a natural outgrowth of algorithms we have already implemented. The basic algorithm is the one originally used for plain AVL trees. The search step is taken verbatim from PBST deletion. The deletion step combines PBST and TAVL tree code. Finally, the rebalancing strategy is the same as used in TAVL deletion.

The function outline is below. As noted above, step 1 is borrowed from PBST deletion. The other steps are implemented in the following sections. 

536. <PAVL item deletion function 536> =
void *
pavl_delete (struct pavl_table *tree, const void *item) 
{
  struct pavl_node *p; /* Traverses tree to find node to delete. */
  struct pavl_node *q; /* Parent of p. */
  int dir;             /* Side of q on which p is linked. */

  assert (tree != NULL && item != NULL);

  <Step 1: Find PBST node to delete; pbst => pavl 496>
  <Step 2: Delete item from PAVL tree 537>
  <Steps 3 and 4: Update balance factors and rebalance after PAVL deletion 541>
}

This code is included in 524.