10.5.2 Left-Looking Deletion [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

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:

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:

390. <Step 2: Delete RTBST node, left-looking 390> =
if (p->rtbst_link[0] == NULL) 
  { if (p->rtbst_rtag == RTBST_CHILD) {
        <Case 1 in left-looking RTBST deletion 391>
      } else
      {
        <Case 2 in left-looking RTBST deletion 392>
      } }
else
  { struct rtbst_node *r = p->rtbst_link[0]; if (r->rtbst_rtag == RTBST_THREAD) {
        <Case 3 in left-looking RTBST deletion 393>
      } else
      {
        <Case 4 in left-looking RTBST deletion 394>
      } }

This code is included in 382.

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

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:

[Click here for plain-text rendering]

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

This code is included in 390.

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

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

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

This code is included in 390.

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

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:

[Click here for plain-text rendering]

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.

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

This code is included in 390.

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

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 265> (see the discussion there for details). The first step is to find the predecessor s of node p:

394. <Case 4 in left-looking RTBST deletion 394> =
struct rtbst_node *s;

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

See also 395 and 396.

This code is included in 390.

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

395. <Case 4 in left-looking RTBST deletion 394> +=
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.

396. <Case 4 in left-looking RTBST deletion 394> +=
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 394> 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]