10.5.1 Right-Looking Deletion |

Our usual algorithm for deletion looks at the right subtree of the node to be deleted, so we call it “right-looking.” The outline for this kind of deletion is the same as in TBST deletion (see Deleting from a TBST):

385. <Step 2: Delete RTBST node, right-looking 385> =if(p->rtbst_rtag==RTBST_THREAD)

{if(p->rtbst_link[0] !=NULL) {

<Case 1 in right-looking RTBST deletion 386>

}else

{

<Case 2 in right-looking RTBST deletion 387>

} }else

{structrtbst_node*r=p->rtbst_link[1];if(r->rtbst_link[0] ==NULL) {

<Case 3 in right-looking RTBST deletion 388>

}else

{

<Case 4 in right-looking RTBST deletion 389>

} }

Each of the four cases, presented below, is closely analogous to the same case in TBST deletion.

In this case, node *p* has a right thread and a left child. As in a
TBST, this means that after deleting *p* we must update the right thread
in *p*'s former left subtree to point to *p*'s replacement. The only
difference from <Case 1 in TBST deletion 262> is in structure members:

386. <Case 1 in right-looking RTBST deletion 386> =structrtbst_node*t=p->rtbst_link[0];while(t->rtbst_rtag==RTBST_CHILD)t=t->rtbst_link[1];t->rtbst_link[1] =p->rtbst_link[1];q->rtbst_link[dir] =p->rtbst_link[0];

This code is included in 385.

If node *p* is a leaf, then there are two subcases, according to whether
*p* is a left child or a right child of its parent *q*. If *dir* is 0,
then *p* is a left child and the pointer from its parent must be set to
`NULL`. If *dir* is 1, then *p* is a right child and the link from its
parent must be changed to a thread to its successor.

In either of these cases we must set *q*->*rtbst_link*[*dir*]: if *dir* is
0, we set it to `NULL`, otherwise *dir* is 1 and we set it to
*p*->*rtbst_link*[1]. However, we know that *p*->*rtbst_link*[0] is `NULL`,
because *p* is a leaf, so we can instead unconditionally assign
*p*->*rtbst_link*[*dir*]. In addition, if *dir* is 1, then we must tag
*q*'s right link as a thread.

If *q* is the pseudo-root, then *dir* is 0 and everything works out fine
with no need for a special case.

387. <Case 2 in right-looking RTBST deletion 387> =q->rtbst_link[dir] =p->rtbst_link[dir];if(dir== 1)q->rtbst_rtag=RTBST_THREAD;

This code is included in 385.

Code for this case, where *p* has a right child *r* that itself has no
left child, is almost identical to <Case 3 in TBST deletion 264>. There
is no left tag to copy, but it is still necessary to chase down the
right thread in *r*'s new left subtree (the same as *p*'s former left
subtree):

388. <Case 3 in right-looking RTBST deletion 388> =r->rtbst_link[0] =p->rtbst_link[0];if(r->rtbst_link[0] !=NULL)

{structrtbst_node*t=r->rtbst_link[0];while(t->rtbst_rtag==RTBST_CHILD)t=t->rtbst_link[1];t->rtbst_link[1] =r; }q->rtbst_link[dir] =r;

This code is included in 385.

Code for case 4, the most general case, is very similar to <Case 4 in TBST deletion 265>. The only notable difference is in the subcase where
*s* has a right thread: in that case we just set *r*'s left link to
`NULL` instead of having to set it up as a thread.

389. <Case 4 in right-looking RTBST deletion 389> =structrtbst_node*s;for(;;)

{s=r->rtbst_link[0];if(s->rtbst_link[0] ==NULL)break;r=s; }if(s->rtbst_rtag==RTBST_CHILD)r->rtbst_link[0] =s->rtbst_link[1];else

r->rtbst_link[0] =NULL;s->rtbst_link[0] =p->rtbst_link[0];if(p->rtbst_link[0] !=NULL)

{structrtbst_node*t=p->rtbst_link[0];while(t->rtbst_rtag==RTBST_CHILD)t=t->rtbst_link[1];t->rtbst_link[1] =s; }s->rtbst_link[1] =p->rtbst_link[1];s->rtbst_rtag=RTBST_CHILD;q->rtbst_link[dir] =s;

This code is included in 385.

**Exercises:**

**1.** Rewrite <Case 4 in right-looking RTBST deletion 389> to replace the
deleted node's *rtavl_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]