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


GNU libavl 2.0.1

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

13.4.1 Step 2: Delete

We use left-looking deletion. At this point, p is the node to delete. After the deletion, x is the node that replaced p, or a null pointer if the node was deleted without replacement. The cases are distinguished in the usual way:

 
if (p-&#62;rtrb_link[0] == NULL) 
{ if (p-&#62;rtrb_rtag == RTRB_CHILD) {
&#60;@xref{\NODE\, , Case 1 in RTRB deletion.&#62;,470}
} else
{
&#60;@xref{\NODE\, , Case 2 in RTRB deletion.&#62;,471}
} }
else
{ enum rtrb_color t; struct rtrb_node *r = p-&#62;rtrb_link[0]; if (r-&#62;rtrb_rtag == RTRB_THREAD) {
&#60;@xref{\NODE\, , Case 3 in RTRB deletion.&#62;,472}
} else
{
&#60;@xref{\NODE\, , Case 4 in RTRB deletion.&#62;,473}
} }
This code is included in @refalso{468

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

If p, the node to be deleted, has a right child but no left child, then we replace it by its right child. This is the same as &#60;@xref{\NODE\, , \TITLE\}.&#62;{Case 1 in RTAVL deletion,432}.

 
&#60;@xref{\NODE\, , Case 1 in RTAVL deletion; rtavl =>.&#62; rtrb,432}
This code is included in @refalso{469

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

Similarly, case 2 is the same as &#60;@xref{\NODE\, , Case 2 in RTAVL deletion.&#62;,433}, with the addition of an assignment to x.

 
&#60;@xref{\NODE\, , Case 2 in RTAVL deletion; rtavl =>.&#62; rtrb,433}
This code is included in @refalso{469

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;rtrb_link[1] = p-&#62;rtrb_link[1];
r-&#62;rtrb_rtag = p-&#62;rtrb_rtag;
t = r-&#62;rtrb_color;
r-&#62;rtrb_color = p-&#62;rtrb_color;
p-&#62;rtrb_color = t;
pa[k - 1]-&#62;rtrb_link[da[k - 1]] = r;
da[k] = 0;
pa[k++] = r;
This code is included in @refalso{469

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

The fourth case, where p has a left child that itself has a right child, uses the same algorithm as &#60;@xref{\NODE\, , Case 4 in RTAVL deletion.&#62;,435}, except that instead of setting the balance factor of s, we swap the colors of t and s as in &#60;@xref{\NODE\, , Case 3 in RB deletion.&#62;,224}.

 
struct rtrb_node *s;
int j = k++;
for (;;) 
{ da[k] = 1; pa[k++] = r; s = r-&#62;rtrb_link[1]; if (s-&#62;rtrb_rtag == RTRB_THREAD) break; r = s; } da[j] = 0; pa[j] = pa[j - 1]-&#62;rtrb_link[da[j - 1]] = s; if (s-&#62;rtrb_link[0] != NULL) r-&#62;rtrb_link[1] = s-&#62;rtrb_link[0]; else
{ r-&#62;rtrb_rtag = RTRB_THREAD; r-&#62;rtrb_link[1] = s; } s-&#62;rtrb_link[0] = p-&#62;rtrb_link[0]; s-&#62;rtrb_link[1] = p-&#62;rtrb_link[1]; s-&#62;rtrb_rtag = p-&#62;rtrb_rtag; t = s-&#62;rtrb_color; s-&#62;rtrb_color = p-&#62;rtrb_color; p-&#62;rtrb_color = t;
This code is included in @refalso{469


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

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