9.4.2 Step 2: Delete [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

The code for node deletion is a combination of RB deletion (see Deleting an RB Node Step 2 - Delete) and TBST deletion (see Deleting from a TBST). The node to delete is p, and after deletion the stack contains all the nodes down to where rebalancing begins. The cases are the same as for TBST deletion:

351. <Step 2: Delete item from TRB tree 351> =
if (p->trb_tag[1] == TRB_THREAD) 
  { if (p->trb_tag[0] == TRB_CHILD) {
        <Case 1 in TRB deletion 352>
      } else
      {
        <Case 2 in TRB deletion 353>
      } }
else
  { enum trb_color t; struct trb_node *r = p->trb_link[1]; if (r->trb_tag[0] == TRB_THREAD) {
        <Case 3 in TRB deletion 354>
      } else
      {
        <Case 4 in TRB deletion 355>
      } }

This code is included in 349.

Case 1: p has a right thread and a left child

If the node to delete p has a right thread and a left child, then we replace it by its left child. We also have to chase down the right thread that pointed to p. The code is almost the same as <Case 1 in TBST deletion 260>, but we use the stack here instead of a single parent pointer.

352. <Case 1 in TRB deletion 352> =
struct trb_node *t = p->trb_link[0];
while (t->trb_tag[1] == TRB_CHILD)
  t = t->trb_link[1];
t->trb_link[1] = p->trb_link[1];
pa[k - 1]->trb_link[da[k - 1]] = p->trb_link[0];

This code is included in 351.

Case 2: p has a right thread and a left thread

Deleting a leaf node is the same process as for a TBST. The changes from <Case 2 in TBST deletion 261> are again due to the use of a stack.

353. <Case 2 in TRB deletion 353> =
pa[k - 1]->trb_link[da[k - 1]] = p->trb_link[da[k - 1]];
if (pa[k - 1] != (struct trb_node *) &tree->trb_root)
  pa[k - 1]->trb_tag[da[k - 1]] = TRB_THREAD;

This code is included in 351.

Case 3: p's right child has a left thread

The code for case 3 merges <Case 3 in TBST deletion 262> with <Case 2 in RB deletion 223>. First, the node is deleted in the same way used for a TBST. Then the colors of p and r are swapped, and r is added to the stack, in the same way as for RB deletion.

354. <Case 3 in TRB deletion 354> =
r->trb_link[0] = p->trb_link[0];
r->trb_tag[0] = p->trb_tag[0];
if (r->trb_tag[0] == TRB_CHILD) 
  { struct trb_node *t = r->trb_link[0]; while (t->trb_tag[1] == TRB_CHILD) t = t->trb_link[1]; t->trb_link[1] = r; } pa[k - 1]->trb_link[da[k - 1]] = r; t = r->trb_color; r->trb_color = p->trb_color; p->trb_color = t; da[k] = 1; pa[k++] = r;

This code is included in 351.

Case 4: p's right child has a left child

Case 4 is a mix of <Case 4 in TBST deletion 263> and <Case 3 in RB deletion 224>. It follows the outline of TBST deletion, but updates the stack. After the deletion it also swaps the colors of p and s as in RB deletion.

355. <Case 4 in TRB deletion 355> =
struct trb_node *s;
int j = k++;

for (;;) 
  { da[k] = 0; pa[k++] = r; s = r->trb_link[0]; if (s->trb_tag[0] == TRB_THREAD) break; r = s; } da[j] = 1; pa[j] = s; if (s->trb_tag[1] == TRB_CHILD) r->trb_link[0] = s->trb_link[1]; else
  { r->trb_link[0] = s; r->trb_tag[0] = TRB_THREAD; } s->trb_link[0] = p->trb_link[0]; if (p->trb_tag[0] == TRB_CHILD)
  { struct trb_node *t = p->trb_link[0]; while (t->trb_tag[1] == TRB_CHILD) t = t->trb_link[1]; t->trb_link[1] = s; s->trb_tag[0] = TRB_CHILD; } s->trb_link[1] = p->trb_link[1]; s->trb_tag[1] = TRB_CHILD; t = s->trb_color; s->trb_color = p->trb_color; p->trb_color = t; pa[j - 1]->trb_link[da[j - 1]] = s;

This code is included in 351.

Exercises:

1. Rewrite <Case 4 in TAVL deletion 317> to replace the deleted node's tavl_data by its successor, then delete the successor, instead of shuffling pointers. (Refer back to Exercise 4.8-3 for an explanation of why this approach cannot be used in libavl.) [answer]