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


GNU libavl 2.0.1

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

10.4.2 Step 2: Delete

The code for node deletion is a combination of RB deletion (see section 7.5.1 Step 2: Delete) and TBST deletion (see section 8.7 Deletion). The node to delete is p, and after deletion the stack contains all the nodes down to where rebalancing begins. The cases are the same as for TBST deletion:

 
if (p-&#62;trb_tag[1] == TRB_THREAD) 
{ if (p-&#62;trb_tag[0] == TRB_CHILD) {
&#60;@xref{\NODE\, , Case 1 in TRB deletion.&#62;,352}
} else
{
&#60;@xref{\NODE\, , Case 2 in TRB deletion.&#62;,353}
} }
else
{ enum trb_color t; struct trb_node *r = p-&#62;trb_link[1]; if (r-&#62;trb_tag[0] == TRB_THREAD) {
&#60;@xref{\NODE\, , Case 3 in TRB deletion.&#62;,354}
} else
{
&#60;@xref{\NODE\, , Case 4 in TRB deletion.&#62;,355}
} }
This code is included in @refalso{349

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

If the node to delete p has a right thread and a left child, then we replace it by its left child. We also have to chase down the right thread that pointed to p. The code is almost the same as &#60;@xref{\NODE\, , \TITLE\}.&#62;{Case 1 in TBST deletion,260}, but we use the stack here instead of a single parent pointer.

 
struct trb_node *t = p-&#62;trb_link[0];
while (t-&#62;trb_tag[1] == TRB_CHILD)
  t = t-&#62;trb_link[1];
t-&#62;trb_link[1] = p-&#62;trb_link[1];
pa[k - 1]-&#62;trb_link[da[k - 1]] = p-&#62;trb_link[0];
This code is included in @refalso{351

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

Deleting a leaf node is the same process as for a TBST. The changes from &#60;@xref{\NODE\, , Case 2 in TBST deletion.&#62;,261} are again due to the use of a stack.

 
pa[k - 1]-&#62;trb_link[da[k - 1]] = p-&#62;trb_link[da[k - 1]];
if (pa[k - 1] != (struct trb_node *) &tree-&#62;trb_root)
  pa[k - 1]-&#62;trb_tag[da[k - 1]] = TRB_THREAD;
This code is included in @refalso{351

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

The code for case 3 merges &#60;@xref{\NODE\, , Case 3 in TBST deletion.&#62;,262} with &#60;@xref{\NODE\, , \TITLE\}.&#62;{Case 2 in RB deletion,223}. First, the node is deleted in the same way used for a TBST. Then the colors of p and r are swapped, and r is added to the stack, in the same way as for RB deletion.

 
r-&#62;trb_link[0] = p-&#62;trb_link[0];
r-&#62;trb_tag[0] = p-&#62;trb_tag[0];
if (r-&#62;trb_tag[0] == TRB_CHILD) 
{ struct trb_node *t = r-&#62;trb_link[0]; while (t-&#62;trb_tag[1] == TRB_CHILD) t = t-&#62;trb_link[1]; t-&#62;trb_link[1] = r; } pa[k - 1]-&#62;trb_link[da[k - 1]] = r; t = r-&#62;trb_color; r-&#62;trb_color = p-&#62;trb_color; p-&#62;trb_color = t; da[k] = 1; pa[k++] = r;
This code is included in @refalso{351

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

Case 4 is a mix of &#60;@xref{\NODE\, , Case 4 in TBST deletion.&#62;,263} and &#60;@xref{\NODE\, , \TITLE\}.&#62;{Case 3 in RB deletion,224}. It follows the outline of TBST deletion, but updates the stack. After the deletion it also swaps the colors of p and s as in RB deletion.

 
struct trb_node *s;
int j = k++;
for (;;) 
{ da[k] = 0; pa[k++] = r; s = r-&#62;trb_link[0]; if (s-&#62;trb_tag[0] == TRB_THREAD) break; r = s; } da[j] = 1; pa[j] = s; if (s-&#62;trb_tag[1] == TRB_CHILD) r-&#62;trb_link[0] = s-&#62;trb_link[1]; else
{ r-&#62;trb_link[0] = s; r-&#62;trb_tag[0] = TRB_THREAD; } s-&#62;trb_link[0] = p-&#62;trb_link[0]; if (p-&#62;trb_tag[0] == TRB_CHILD)
{ struct trb_node *t = p-&#62;trb_link[0]; while (t-&#62;trb_tag[1] == TRB_CHILD) t = t-&#62;trb_link[1]; t-&#62;trb_link[1] = s; s-&#62;trb_tag[0] = TRB_CHILD; } s-&#62;trb_link[1] = p-&#62;trb_link[1]; s-&#62;trb_tag[1] = TRB_CHILD; t = s-&#62;trb_color; s-&#62;trb_color = p-&#62;trb_color; p-&#62;trb_color = t; pa[j - 1]-&#62;trb_link[da[j - 1]] = s;
This code is included in @refalso{351

Exercises:

1. Rewrite &#60;@xref{\NODE\, , Case 4 in TAVL deletion.&#62;,317} to replace the deleted node's tavl_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