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

Deletion in an RTAVL tree takes the usual pattern. 

429. <RTAVL item deletion function 429> =
void *
rtavl_delete (struct rtavl_table *tree, const void *item) 
{
  /* Stack of nodes. */
  struct rtavl_node *pa[RTAVL_MAX_HEIGHT]; /* Nodes. */
  unsigned char da[RTAVL_MAX_HEIGHT];     /* rtavl_link[] indexes. */
  int k;                                  /* Stack pointer. */

  struct rtavl_node *p; /* Traverses tree to find node to delete. */

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

  <Step 1: Search RTAVL tree for item to delete 430>
  <Step 2: Delete RTAVL node 431>
  <Steps 3 and 4: Update balance factors and rebalance after RTAVL deletion 438>

  return (void *) item;
}

This code is included in 418.