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


GNU libavl 2.0.1

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

13.4.2 Step 3: Rebalance

The rebalancing step's outline is much like that for deletion in a symmetrically threaded tree, except that we must check for a null child pointer on the left side of x versus a thread on the right side:

 
if (p-&#62;rtrb_color == RTRB_BLACK) 
{ for (; k > 1; k--)
{ struct rtrb_node *x; if (da[k - 1] == 0 || pa[k - 1]-&#62;rtrb_rtag == RTRB_CHILD) x = pa[k - 1]-&#62;rtrb_link[da[k - 1]]; else
x = NULL; if (x != NULL && x-&#62;rtrb_color == RTRB_RED)
{ x-&#62;rtrb_color = RTRB_BLACK; break; } if (da[k - 1] == 0) {
&#60;@xref{\NODE\, , Left-side rebalancing after RTRB deletion.&#62;,475}
} else
{
&#60;@xref{\NODE\, , Right-side rebalancing after RTRB deletion.&#62;,476}
} } if (tree-&#62;rtrb_root != NULL)
tree-&#62;rtrb_root-&#62;rtrb_color = RTRB_BLACK; }
This code is included in @refalso{468

As for RTRB insertion, rebalancing on either side of the root is not symmetric because the tree structure itself is not symmetric, but again the rebalancing steps are very similar. The outlines of the left-side and right-side rebalancing code are below. The code for ensuring that w is black and for case 1 on each side are the same as the corresponding unthreaded RB code, because none of that code needs to check for empty trees:

 
struct rtrb_node *w = pa[k - 1]-&#62;rtrb_link[1];
if (w-&#62;rtrb_color == RTRB_RED) 
  { 
&#60;@xref{\NODE\, , Ensure w.&#62; is black in left-side RB deletion rebalancing; rb => rtrb,228}
} if ((w-&#62;rtrb_link[0] == NULL
|| w-&#62;rtrb_link[0]-&#62;rtrb_color == RTRB_BLACK) && (w-&#62;rtrb_rtag == RTRB_THREAD
|| w-&#62;rtrb_link[1]-&#62;rtrb_color == RTRB_BLACK)) {
&#60;@xref{\NODE\, , Case 1 in left-side RB deletion rebalancing; rb =>.&#62; rtrb,229}
} else
{ if (w-&#62;rtrb_rtag == RTRB_THREAD
|| w-&#62;rtrb_link[1]-&#62;rtrb_color == RTRB_BLACK) {
&#60;@xref{\NODE\, , Transform left-side RTRB deletion rebalancing case 3 into case 2.&#62;,479}
} &#60;@xref{\NODE\, , Case 2 in left-side RTRB deletion rebalancing.&#62;,477} break; }
This code is included in @refalso{474

 
struct rtrb_node *w = pa[k - 1]-&#62;rtrb_link[0];
if (w-&#62;rtrb_color == RTRB_RED) 
  { 
&#60;@xref{\NODE\, , Ensure w.&#62; is black in right-side RB deletion rebalancing; rb => rtrb,234}
} if ((w-&#62;rtrb_link[0] == NULL
|| w-&#62;rtrb_link[0]-&#62;rtrb_color == RTRB_BLACK) && (w-&#62;rtrb_rtag == RTRB_THREAD
|| w-&#62;rtrb_link[1]-&#62;rtrb_color == RTRB_BLACK)) {
&#60;@xref{\NODE\, , Case 1 in right-side RB deletion rebalancing; rb =>.&#62; rtrb,235}
} else
{ if (w-&#62;rtrb_link[0] == NULL
|| w-&#62;rtrb_link[0]-&#62;rtrb_color == RTRB_BLACK) {
&#60;@xref{\NODE\, , Transform right-side RTRB deletion rebalancing case 3 into case 2.&#62;,480}
} &#60;@xref{\NODE\, , Case 2 in right-side RTRB deletion rebalancing.&#62;,478} break; }
This code is included in @refalso{474

Case 2: w's child opposite the deletion is red

If the deletion was on the left side of w and w's right child is red, we rotate left at pa[k - 1] and perform some recolorings, as we did for unthreaded RB trees (@pageref{rbdelcase2}). There is a special case when w has no left child. This must be transformed into a thread from leading to w following the rotation:

rtrbdel1

 
&#60;@xref{\NODE\, , Case 2 in left-side RB deletion rebalancing; rb =>.&#62; rtrb,230}
if (w-&#62;rtrb_link[0]-&#62;rtrb_link[1] == NULL) 
{ w-&#62;rtrb_link[0]-&#62;rtrb_rtag = RTRB_THREAD; w-&#62;rtrb_link[0]-&#62;rtrb_link[1] = w; }
This code is included in @refalso{475

Alternately, if the deletion was on the right side of w and w's left child is right, we rotate right at pa[k - 1] and recolor. There is an analogous special case:

rtrbdel2

 
&#60;@xref{\NODE\, , Case 2 in right-side RB deletion rebalancing; rb =>.&#62; rtrb,237}
if (w-&#62;rtrb_rtag == RTRB_THREAD) 
{ w-&#62;rtrb_rtag = RTRB_CHILD; pa[k - 1]-&#62;rtrb_link[0] = NULL; }
This code is included in @refalso{476

Case 3: w's child on the side of the deletion is red

If the deletion was on the left side of w and w's left child is red, then we rotate right at w and recolor, as in case 3 for unthreaded RB trees (@pageref{rbdelcase3}). There is a special case when w's left child has a right thread. This must be transformed into a null left child of w's right child following the rotation:

rtrbdel3

 
&#60;@xref{\NODE\, , Transform left-side RB deletion rebalancing case 3 into case 2; rb =>.&#62; rtrb,231}
if (w-&#62;rtrb_rtag == RTRB_THREAD) 
{ w-&#62;rtrb_rtag = RTRB_CHILD; w-&#62;rtrb_link[1]-&#62;rtrb_link[0] = NULL; }
This code is included in @refalso{475

Alternately, if the deletion was on the right side of w and w's right child is red, we rotate left at w and recolor. There is an analogous special case:

rtrbdel4

 
&#60;@xref{\NODE\, , Transform right-side RB deletion rebalancing case 3 into case 2; rb =>.&#62; rtrb,236}
if (w-&#62;rtrb_link[0]-&#62;rtrb_link[1] == NULL) 
{ w-&#62;rtrb_link[0]-&#62;rtrb_rtag = RTRB_THREAD; w-&#62;rtrb_link[0]-&#62;rtrb_link[1] = w; }
This code is included in @refalso{476


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

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