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


GNU libavl 2.0.1

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

11.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 section 8.7 Deletion):

 
if (p-&#62;rtbst_rtag == RTBST_THREAD) 
{ if (p-&#62;rtbst_link[0] != NULL) {
&#60;@xref{\NODE\, , Case 1 in right-looking RTBST deletion.&#62;,384}
} else
{
&#60;@xref{\NODE\, , Case 2 in right-looking RTBST deletion.&#62;,385}
} }
else
{ struct rtbst_node *r = p-&#62;rtbst_link[1]; if (r-&#62;rtbst_link[0] == NULL) {
&#60;@xref{\NODE\, , Case 3 in right-looking RTBST deletion.&#62;,386}
} else
{
&#60;@xref{\NODE\, , Case 4 in right-looking RTBST deletion.&#62;,387}
} }

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

Case 1: p has a right thread and a left child

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 &#60;@xref{\NODE\, , Case 1 in TBST deletion.&#62;,260} is in structure members:

 
struct rtbst_node *t = p-&#62;rtbst_link[0];
while (t-&#62;rtbst_rtag == RTBST_CHILD)
  t = t-&#62;rtbst_link[1];
t-&#62;rtbst_link[1] = p-&#62;rtbst_link[1];
q-&#62;rtbst_link[dir] = p-&#62;rtbst_link[0];
This code is included in @refalso{383

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

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-&#62;rtbst_link[dir]: if dir is 0, we set it to NULL, otherwise dir is 1 and we set it to p-&#62;rtbst_link[1]. However, we know that p-&#62;rtbst_link[0] is NULL, because p is a leaf, so we can instead unconditionally assign p-&#62;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.

 
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{383

Case 3: p's right child has no left child

Code for this case, where p has a right child r that itself has no left child, is almost identical to &#60;@xref{\NODE\, , Case 3 in TBST deletion.&#62;,262}. 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):

 
r-&#62;rtbst_link[0] = p-&#62;rtbst_link[0];
if (r-&#62;rtbst_link[0] != NULL) 
{ struct rtbst_node *t = r-&#62;rtbst_link[0]; while (t-&#62;rtbst_rtag == RTBST_CHILD) t = t-&#62;rtbst_link[1]; t-&#62;rtbst_link[1] = r; } q-&#62;rtbst_link[dir] = r;
This code is included in @refalso{383

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

Code for case 4, the most general case, is very similar to &#60;@xref{\NODE\, , \TITLE\}.&#62;{Case 4 in TBST deletion,263}. 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.

 
struct rtbst_node *s;
for (;;) 
{ s = r-&#62;rtbst_link[0]; if (s-&#62;rtbst_link[0] == NULL) break; r = s; } if (s-&#62;rtbst_rtag == RTBST_CHILD) r-&#62;rtbst_link[0] = s-&#62;rtbst_link[1]; else
r-&#62;rtbst_link[0] = NULL; s-&#62;rtbst_link[0] = p-&#62;rtbst_link[0]; if (p-&#62;rtbst_link[0] != NULL)
{ struct rtbst_node *t = p-&#62;rtbst_link[0]; while (t-&#62;rtbst_rtag == RTBST_CHILD) t = t-&#62;rtbst_link[1]; t-&#62;rtbst_link[1] = s; } s-&#62;rtbst_link[1] = p-&#62;rtbst_link[1]; s-&#62;rtbst_rtag = RTBST_CHILD; q-&#62;rtbst_link[dir] = s;
This code is included in @refalso{383

Exercises:

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


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

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