10.5.2 Left-Looking Deletion |

The previous section implemented the “right-looking” form of deletion used elsewhere in libavl. Compared to deletion in a fully threaded binary tree, the benefits to using an RTBST with this kind of deletion are minimal:

- Cases 1 and 2 are similar code in both TBST and RTBST deletion.
- Case 3 in an RTBST avoids one tag copy required in TBST deletion.
- One subcase of case 4 in an RTBST avoids one tag assignment required in the same subcase of TBST deletion.

This is hardly worth it. We saved at most one assignment per call. We need something better if it's ever going to be worthwhile to use right-threaded trees.

Fortunately, there is a way that we can save a little more. This is by changing our right-looking deletion into left-looking deletion, by switching the use of left and right children in the algorithm. In a BST or TBST, this symmetrical change in the algorithm would have no effect, because the BST and TBST node structures are themselves symmetric. But in an asymmetric RTBST even a symmetric change can have a significant effect on an algorithm, as we'll see.

The cases for left-looking deletion are outlined in the same way as for right-looking deletion:

388. <Step 2: Delete RTBST node, left-looking 388> =if(p->rtbst_link[0] ==NULL)

{if(p->rtbst_rtag==RTBST_CHILD) {

<Case 1 in left-looking RTBST deletion 389>

}else

{

<Case 2 in left-looking RTBST deletion 390>

} }else

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

<Case 3 in left-looking RTBST deletion 391>

}else

{

<Case 4 in left-looking RTBST deletion 392>

} }

This code is included in 380.

If the node to delete *p* has a right child but no left child, we can
just replace it by its right child. There is no right thread to update
in *p*'s left subtree because *p* has no left child, and there is no
left thread to update because a right-threaded tree has no left threads.

The deletion looks like this if *p*'s right child is designated *x*:

389. <Case 1 in left-looking RTBST deletion 389> =q->rtbst_link[dir] =p->rtbst_link[1];

This code is included in 388.

This case is analogous to case 2 in right-looking deletion covered earlier. The same discussion applies.

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

This code is included in 388.

If *p* has a left child *r* that itself has a right thread, then we
replace *p* by *r*. Node *r* receives *p*'s former right link, as shown
here:

There is no need to fiddle with threads. If *r* has a right thread
then it gets replaced by *p*'s right child or thread anyhow. Any
right thread within *r*'s left subtree either points within that
subtree or to *r*. Finally, *r*'s right subtree cannot cause
problems.

391. <Case 3 in left-looking RTBST deletion 391> =r->rtbst_link[1] =p->rtbst_link[1];r->rtbst_rtag=p->rtbst_rtag;q->rtbst_link[dir] =r;

This code is included in 388.

The final case handles deletion of a node *p* with a left child *r*
that in turn has a right child. The code here follows the same
pattern as <Case 4 in TBST deletion 263> (see the discussion there for
details). The first step is to find the predecessor *s* of node *p*:

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

{s=r->rtbst_link[1];if(s->rtbst_rtag==RTBST_THREAD)break;r=s; }

This code is included in 388.

Next, we update *r*, handling two subcases depending on whether *s* has
a left child:

393. <Case 4 in left-looking RTBST deletion 392> +=if(s->rtbst_link[0] !=NULL)r->rtbst_link[1] =s->rtbst_link[0];else

{r->rtbst_link[1] =s;r->rtbst_rtag=RTBST_THREAD; }

The final step is to copy *p*'s fields into *s*, then set *q*'s child
pointer to point to *s* instead of *p*. There is no need to chase down
any threads.

394. <Case 4 in left-looking RTBST deletion 392> +=s->rtbst_link[0] =p->rtbst_link[0];s->rtbst_link[1] =p->rtbst_link[1];s->rtbst_rtag=p->rtbst_rtag;q->rtbst_link[dir] =s;

**Exercises:**

**1.** Rewrite <Case 4 in left-looking RTBST deletion 392> to replace the deleted
node's *rtavl_data* by its predecessor, then delete the predecessor,
instead of shuffling pointers. (Refer back to Exercise 4.8-3 for an
explanation of why this approach cannot be used in libavl.)
[answer]