www.delorie.com/gnu/docs/avl/libavl_190.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

11.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:

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:

 
if (p-&#62;rtbst_link[0] == NULL) 
{ if (p-&#62;rtbst_rtag == RTBST_CHILD) {
&#60;@xref{\NODE\, , Case 1 in left-looking RTBST deletion.&#62;,389}
} else
{
&#60;@xref{\NODE\, , Case 2 in left-looking RTBST deletion.&#62;,390}
} }
else
{ struct rtbst_node *r = p-&#62;rtbst_link[0]; if (r-&#62;rtbst_rtag == RTBST_THREAD) {
&#60;@xref{\NODE\, , Case 3 in left-looking RTBST deletion.&#62;,391}
} else
{
&#60;@xref{\NODE\, , Case 4 in left-looking RTBST deletion.&#62;,392}
} }
This code is included in @refalso{380

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:

rtbstdel

 
q-&#62;rtbst_link[dir] = p-&#62;rtbst_link[1];
This code is included in @refalso{388

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.

 
q-&#62;rtbst_link[dir] = p-&#62;rtbst_link[dir];
if (dir == 1)
  q-&#62;rtbst_rtag = RTBST_THREAD;
This code is included in @refalso{388

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:

rtbstdel2

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.

 
r-&#62;rtbst_link[1] = p-&#62;rtbst_link[1];
r-&#62;rtbst_rtag = p-&#62;rtbst_rtag;
q-&#62;rtbst_link[dir] = r;
This code is included in @refalso{388

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 &#60;@xref{\NODE\, , Case 4 in TBST deletion.&#62;,263} (see the discussion there for details). The first step is to find the predecessor s of node p:

 
struct rtbst_node *s;
for (;;) 
{ s = r-&#62;rtbst_link[1]; if (s-&#62;rtbst_rtag == RTBST_THREAD) break; r = s; }
See also @refalso{393 This code is included in @refalso{388

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

 
if (s-&#62;rtbst_link[0] != NULL)
  r-&#62;rtbst_link[1] = s-&#62;rtbst_link[0];
else 
{ r-&#62;rtbst_link[1] = s; r-&#62;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.

 
s-&#62;rtbst_link[0] = p-&#62;rtbst_link[0];
s-&#62;rtbst_link[1] = p-&#62;rtbst_link[1];
s-&#62;rtbst_rtag = p-&#62;rtbst_rtag;
q-&#62;rtbst_link[dir] = s;    

Exercises:

1. Rewrite &#60;@xref{\NODE\, , Case 4 in left-looking RTBST deletion.&#62;,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]


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003