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


GNU libavl 2.0.1

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

12.5.2 Step 2: Delete

As demonstrated in the previous chapter, left-looking deletion, where we examine the left subtree of the node to be deleted, is more efficient than right-looking deletion in an RTBST (see section 11.5.2 Left-Looking Deletion). This holds true in an RTAVL tree, too.

 
if (p-&#62;rtavl_link[0] == NULL) 
{ if (p-&#62;rtavl_rtag == RTAVL_CHILD) {
&#60;@xref{\NODE\, , Case 1 in RTAVL deletion.&#62;,432}
} else
{
&#60;@xref{\NODE\, , Case 2 in RTAVL deletion.&#62;,433}
} }
else
{ struct rtavl_node *r = p-&#62;rtavl_link[0]; if (r-&#62;rtavl_rtag == RTAVL_THREAD) {
&#60;@xref{\NODE\, , Case 3 in RTAVL deletion.&#62;,434}
} else
{
&#60;@xref{\NODE\, , Case 4 in RTAVL deletion.&#62;,435}
} } tree-&#62;rtavl_alloc-&#62;libavl_free (tree-&#62;rtavl_alloc, p);
This code is included in @refalso{429

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

If the node to be deleted, p, has a right child but not a left child, then we replace it by its right child.

 
pa[k - 1]-&#62;rtavl_link[da[k - 1]] = p-&#62;rtavl_link[1];
This code is included in @refalso{431

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

If we are deleting a leaf, then we replace it by a null pointer if it's a left child, or by a pointer to its own former right thread if it's a right child. Refer back to the commentary on &#60;@xref{\NODE\, , \TITLE\}.&#62;{Case 2 in right-looking RTBST deletion,385} for further explanation.

 
pa[k - 1]-&#62;rtavl_link[da[k - 1]] = p-&#62;rtavl_link[da[k - 1]];
if (da[k - 1] == 1)
  pa[k - 1]-&#62;rtavl_rtag = RTAVL_THREAD;
This code is included in @refalso{431

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

If p has a left child r, and r has a right thread, then we replace p by r and transfer p's former right link to r. Node r also receives p's balance factor.

 
r-&#62;rtavl_link[1] = p-&#62;rtavl_link[1];
r-&#62;rtavl_rtag = p-&#62;rtavl_rtag;
r-&#62;rtavl_balance = p-&#62;rtavl_balance;
pa[k - 1]-&#62;rtavl_link[da[k - 1]] = r;
da[k] = 0;
pa[k++] = r;
This code is included in @refalso{431

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

The final case, where node p's left child r has a right child, is also the most complicated. We find p's predecessor s first:

 
struct rtavl_node *s;
int j = k++;
for (;;) 
{ da[k] = 1; pa[k++] = r; s = r-&#62;rtavl_link[1]; if (s-&#62;rtavl_rtag == RTAVL_THREAD) break; r = s; }
See also @refalso{436 This code is included in @refalso{431

Then we move s into p's place, not forgetting to update links and tags as necessary:

 
da[j] = 0;
pa[j] = pa[j - 1]-&#62;rtavl_link[da[j - 1]] = s;
if (s-&#62;rtavl_link[0] != NULL)
  r-&#62;rtavl_link[1] = s-&#62;rtavl_link[0];
else 
{ r-&#62;rtavl_rtag = RTAVL_THREAD; r-&#62;rtavl_link[1] = s; }

Finally, we copy p's old information into s, except for the actual data:

 
s-&#62;rtavl_balance = p-&#62;rtavl_balance;
s-&#62;rtavl_link[0] = p-&#62;rtavl_link[0];
s-&#62;rtavl_link[1] = p-&#62;rtavl_link[1];
s-&#62;rtavl_rtag = p-&#62;rtavl_rtag;


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

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