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

Deleting a node from an RTBST can be done using the same ideas as for other kinds of trees we've seen. However, as it turns out, a variant of this usual technique allows for faster code. In this section, we will implement the usual method, then the improved version. The latter is actually used in libavl.

Here is the outline of the function. Step 2 is the only part that varies between versions: 

382. <RTBST item deletion function 382> =
void *
rtbst_delete (struct rtbst_table *tree, const void *item) 
{
  struct rtbst_node *p;	/* Node to delete. */
  struct rtbst_node *q;	/* Parent of p. */
  int dir;              /* Index into q->rtbst_link[] that leads to p. */

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

  <Step 1: Find RTBST node to delete 383>
  <Step 2: Delete RTBST node, left-looking 390>
  <Step 3: Finish up after deleting RTBST node 384>
}

This code is included in 377.

The first step just finds the node to delete. After it executes, p is the node to delete and q and dir are set such that q->rtbst_link[dir] == p. 

383. <Step 1: Find RTBST node to delete 383> =
if (tree->rtbst_root == NULL)
  return NULL;

p = tree->rtbst_root;
q = (struct rtbst_node *) &tree->rtbst_root;
dir = 0;
if (p == NULL)
  return NULL;

for (;;) 
  {
    int cmp = tree->rtbst_compare (item, p->rtbst_data, tree->rtbst_param);
    if (cmp == 0) 
      break;

    dir = cmp > 0;
    if (dir == 0) 
      {
        if (p->rtbst_link[0] == NULL)
          return NULL;
      } 
    else /* dir == 1 */ 
      {
        if (p->rtbst_rtag == RTBST_THREAD)
          return NULL;
      }

    q = p;
    p = p->rtbst_link[dir];
  }
item = p->rtbst_data;

This code is included in 382.

The final step is also common. We just clean up and return: 

384. <Step 3: Finish up after deleting RTBST node 384> =
tree->rtbst_alloc->libavl_free (tree->rtbst_alloc, p);
tree->rtbst_count--;
return (void *) item;

This code is included in 382.