11.5.2 Step 2: Delete |

As demonstrated in the previous chapter, left-looking deletion, where we examine the left subtree of the node to be deleted, is more efficient than right-looking deletion in an RTBST (see Left-Looking Deletion in an RTBST). This holds true in an RTAVL tree, too.

433. <Step 2: Delete RTAVL node 433> =if(p->rtavl_link[0] ==NULL)

{if(p->rtavl_rtag==RTAVL_CHILD) {

<Case 1 in RTAVL deletion 434>

}else

{

<Case 2 in RTAVL deletion 435>

} }else

{structrtavl_node*r=p->rtavl_link[0];if(r->rtavl_rtag==RTAVL_THREAD) {

<Case 3 in RTAVL deletion 436>

}else

{

<Case 4 in RTAVL deletion 437>

} }tree->rtavl_alloc->libavl_free(tree->rtavl_alloc,p);

This code is included in 431.

If the node to be deleted, *p*, has a right child but not a left child,
then we replace it by its right child.

434. <Case 1 in RTAVL deletion 434> =pa[k- 1]->rtavl_link[da[k- 1]] =p->rtavl_link[1];

This code is included in 433 and 472.

If we are deleting a leaf, then we replace it by a null pointer if it's a left child, or by a pointer to its own former right thread if it's a right child. Refer back to the commentary on <Case 2 in right-looking RTBST deletion 387> for further explanation.

435. <Case 2 in RTAVL deletion 435> =pa[k- 1]->rtavl_link[da[k- 1]] =p->rtavl_link[da[k- 1]];if(da[k- 1] == 1)pa[k- 1]->rtavl_rtag=RTAVL_THREAD;

This code is included in 433 and 473.

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.

436. <Case 3 in RTAVL deletion 436> =r->rtavl_link[1] =p->rtavl_link[1];r->rtavl_rtag=p->rtavl_rtag;r->rtavl_balance=p->rtavl_balance;pa[k- 1]->rtavl_link[da[k- 1]] =r;da[k] = 0;pa[k++] =r;

This code is included in 433.

The final case, where node *p*'s left child *r* has a right child, is
also the most complicated. We find *p*'s predecessor *s* first:

437. <Case 4 in RTAVL deletion 437> =structrtavl_node*s;intj=k++;for(;;)

{da[k] = 1;pa[k++] =r;s=r->rtavl_link[1];if(s->rtavl_rtag==RTAVL_THREAD)break;r=s; }

This code is included in 433.

Then we move *s* into *p*'s place, not forgetting to update links and
tags as necessary:

438. <Case 4 in RTAVL deletion 437> +=da[j] = 0;pa[j] =pa[j- 1]->rtavl_link[da[j- 1]] =s;if(s->rtavl_link[0] !=NULL)r->rtavl_link[1] =s->rtavl_link[0];else

{r->rtavl_rtag=RTAVL_THREAD;r->rtavl_link[1] =s; }

Finally, we copy *p*'s old information into *s*, except for the actual
data:

439. <Case 4 in RTAVL deletion 437> +=s->rtavl_balance=p->rtavl_balance;s->rtavl_link[0] =p->rtavl_link[0];s->rtavl_link[1] =p->rtavl_link[1];s->rtavl_rtag=p->rtavl_rtag;