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

{enumrtrb_colort;structrtrb_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.

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.

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.

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.

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> =structrtrb_node*s;intj=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.