9.4.2 Step 2: Delete

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:

353. <Step 2: Delete item from TRB tree 353> =
if (p->trb_tag[1] == TRB_THREAD) 
  {
    if (p->trb_tag[0] == TRB_CHILD)
      { 
        <Case 1 in TRB deletion 354> 
      }
    else 
      { 
        <Case 2 in TRB deletion 355> 
      }
  } 
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 356> 
      }
    else 
      { 
        <Case 4 in TRB deletion 357> 
      }
  }

This code is included in 351.

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 262>, but we use the stack here instead of a single parent pointer.

354. <Case 1 in TRB deletion 354> =
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 353.

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 263> are again due to the use of a stack.

355. <Case 2 in TRB deletion 355> =
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 353.

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

The code for case 3 merges <Case 3 in TBST deletion 264> with <Case 2 in RB deletion 225>. 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.

356. <Case 3 in TRB deletion 356> =
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 353.

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

Case 4 is a mix of <Case 4 in TBST deletion 265> and <Case 3 in RB deletion 226>. 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.

357. <Case 4 in TRB deletion 357> =
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 353.

Exercises:

1. Rewrite <Case 4 in TAVL deletion 319> 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]