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


GNU libavl 2.0.1

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

10.4.3 Step 3: Rebalance

The outline for rebalancing after threaded RB deletion is the same as for the unthreaded case (see section 7.5.2 Step 3: Rebalance):

 
if (p-&#62;trb_color == TRB_BLACK) 
{ for (; k > 1; k--)
{ if (pa[k - 1]-&#62;trb_tag[da[k - 1]] == TRB_CHILD)
{ struct trb_node *x = pa[k - 1]-&#62;trb_link[da[k - 1]]; if (x-&#62;trb_color == TRB_RED)
{ x-&#62;trb_color = TRB_BLACK; break; } } if (da[k - 1] == 0) {
&#60;@xref{\NODE\, , Left-side rebalancing after TRB deletion.&#62;,357}
} else
{
&#60;@xref{\NODE\, , Right-side rebalancing after TRB deletion.&#62;,363}
} } if (tree-&#62;trb_root != NULL) tree-&#62;trb_root-&#62;trb_color = TRB_BLACK; }
This code is included in @refalso{349

The rebalancing cases are the same, too. We need to check for thread tags, not for null pointers, though, in some places:

 
struct trb_node *w = pa[k - 1]-&#62;trb_link[1];
if (w-&#62;trb_color == TRB_RED) 
  { 
&#60;@xref{\NODE\, , Ensure w.&#62; is black in left-side TRB deletion rebalancing,358}
} if ((w-&#62;trb_tag[0] == TRB_THREAD
|| w-&#62;trb_link[0]-&#62;trb_color == TRB_BLACK) && (w-&#62;trb_tag[1] == TRB_THREAD
|| w-&#62;trb_link[1]-&#62;trb_color == TRB_BLACK)) {
&#60;@xref{\NODE\, , Case 1 in left-side TRB deletion rebalancing.&#62;,359}
} else
{ if (w-&#62;trb_tag[1] == TRB_THREAD
|| w-&#62;trb_link[1]-&#62;trb_color == TRB_BLACK) {
&#60;@xref{\NODE\, , Transform left-side TRB deletion rebalancing case 3 into case 2.&#62;,361}
} &#60;@xref{\NODE\, , Case 2 in left-side TRB deletion rebalancing.&#62;,360} break; }
This code is included in @refalso{356

Case Reduction: Ensure w is black

This transformation does not move around any subtrees that might be threads, so there is no need for it to change.

 
&#60;@xref{\NODE\, , Ensure w.&#62; is black in left-side RB deletion rebalancing; rb => trb,228}
This code is included in @refalso{357

Case 1: w has no red children

This transformation just recolors nodes, so it also does not need any changes.

 
&#60;@xref{\NODE\, , Case 1 in left-side RB deletion rebalancing; rb =>.&#62; trb,229}
This code is included in @refalso{357

Case 2: w's right child is red

If w has a red right child and a left thread, then it is necessary to adjust tags and links after the left rotation at w and recoloring, as shown in this diagram:

trbdel

 
&#60;@xref{\NODE\, , Case 2 in left-side RB deletion rebalancing; rb =>.&#62; trb,230}
if (w-&#62;trb_tag[0] == TRB_THREAD) 
{ w-&#62;trb_tag[0] = TRB_CHILD; pa[k - 1]-&#62;trb_tag[1] = TRB_THREAD; pa[k - 1]-&#62;trb_link[1] = w; }
This code is included in @refalso{357

Case 3: w's left child is red

If w has a red left child, which has a right thread, then we again need to adjust tags and links after right rotation at w and recoloring, as shown here:

trbdel2

 
&#60;@xref{\NODE\, , Transform left-side RB deletion rebalancing case 3 into case 2; rb =>.&#62; trb,231}
if (w-&#62;trb_tag[1] == TRB_THREAD) 
{ w-&#62;trb_tag[1] = TRB_CHILD; w-&#62;trb_link[1]-&#62;trb_tag[0] = TRB_THREAD; w-&#62;trb_link[1]-&#62;trb_link[0] = w; }
This code is included in @refalso{357


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

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