Deleting from a PAVL Tree - GNU libavl 2.0.2

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.

534. <PAVL item deletion function 534> =
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 494>
  <Step 2: Delete item from PAVL tree 535>
  <Steps 3 and 4: Update balance factors and rebalance after PAVL deletion 539>
}

This code is included in 522.