12.4.1 Step 2: Delete

We use left-looking deletion. At this point, p is the node to delete. After the deletion, x is the node that replaced p, or a null pointer if the node was deleted without replacement. The cases are distinguished in the usual way:

471. <Step 2: Delete RTRB node 471> =
if (p->rtrb_link[0] == NULL) 
  {
    if (p->rtrb_rtag == RTRB_CHILD)
      { 
        <Case 1 in RTRB deletion 472> 
      }
    else 
      { 
        <Case 2 in RTRB deletion 473> 
      }
  } 
else 
  {
    enum rtrb_color t;
    struct rtrb_node *r = p->rtrb_link[0];

    if (r->rtrb_rtag == RTRB_THREAD)
      { 
        <Case 3 in RTRB deletion 474> 
      }
    else 
      { 
        <Case 4 in RTRB deletion 475> 
      }
  }

This code is included in 470.

Case 1: p has a right child but no left child

If p, the node to be deleted, has a right child but no left child, then we replace it by its right child. This is the same as <Case 1 in RTAVL deletion 434>.

472. <Case 1 in RTRB deletion 472> =
<Case 1 in RTAVL deletion; rtavl => rtrb 434>

This code is included in 471.

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

Similarly, case 2 is the same as <Case 2 in RTAVL deletion 435>, with the addition of an assignment to x.

473. <Case 2 in RTRB deletion 473> =
<Case 2 in RTAVL deletion; rtavl => rtrb 435>

This code is included in 471.

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

If p has a left child r, and r has a right thread, then we replace p by r and transfer p's former right link to r. Node r also receives p's balance factor.

474. <Case 3 in RTRB deletion 474> =
r->rtrb_link[1] = p->rtrb_link[1];
r->rtrb_rtag = p->rtrb_rtag;
t = r->rtrb_color;
r->rtrb_color = p->rtrb_color;
p->rtrb_color = t;
pa[k - 1]->rtrb_link[da[k - 1]] = r;
da[k] = 0;
pa[k++] = r;

This code is included in 471.

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

The fourth case, where p has a left child that itself has a right child, uses the same algorithm as <Case 4 in RTAVL deletion 437>, except that instead of setting the balance factor of s, we swap the colors of t and s as in <Case 3 in RB deletion 226>.

475. <Case 4 in RTRB deletion 475> =
struct rtrb_node *s;
int j = k++;

for (;;) 
  {
    da[k] = 1;
    pa[k++] = r;
    s = r->rtrb_link[1];
    if (s->rtrb_rtag == RTRB_THREAD)
      break;

    r = s;
  }

da[j] = 0;
pa[j] = pa[j - 1]->rtrb_link[da[j - 1]] = s;

if (s->rtrb_link[0] != NULL)
  r->rtrb_link[1] = s->rtrb_link[0];
else 
  {
    r->rtrb_rtag = RTRB_THREAD;
    r->rtrb_link[1] = s;
  }

s->rtrb_link[0] = p->rtrb_link[0];
s->rtrb_link[1] = p->rtrb_link[1];
s->rtrb_rtag = p->rtrb_rtag;

t = s->rtrb_color;
s->rtrb_color = p->rtrb_color;
p->rtrb_color = t;

This code is included in 471.