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


GNU libavl 2.0.1

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

13.3.2 Step 3: Rebalance

The rebalancing outline follows &#60;@xref{\NODE\, , \TITLE\}.&#62;{Step 3: Rebalance after RB insertion,201}.

 
while (k >= 3 && pa[k - 1]-&#62;rtrb_color == RTRB_RED) 
{ if (da[k - 2] == 0) {
&#60;@xref{\NODE\, , Left-side rebalancing after RTRB insertion.&#62;,460}
} else
{
&#60;@xref{\NODE\, , Right-side rebalancing after RTRB insertion.&#62;,461}
} } tree-&#62;rtrb_root-&#62;rtrb_color = RTRB_BLACK;
This code is included in @refalso{456

The choice of case for insertion on the left side is made in the same way as in &#60;@xref{\NODE\, , Left-side rebalancing after RB insertion.&#62;,202}, except that of course right-side tests for non-empty subtrees are made using rtrb_rtag instead of rtrb_link[1], and similarly for insertion on the right side. In short, we take q (which is not a real variable) as the new node n if this is the first time through the loop, or a node whose color has just been changed to red otherwise. We know that both q and its parent pa[k - 1] are red, violating rule 1 for red-black trees, and that q's grandparent pa[k - 2] is black. Here is the code to distinguish cases:

 
struct rtrb_node *y = pa[k - 2]-&#62;rtrb_link[1];
if (pa[k - 2]-&#62;rtrb_rtag == RTRB_CHILD && y-&#62;rtrb_color == RTRB_RED)
  { 
&#60;@xref{\NODE\, , Case 1 in left-side RTRB insertion rebalancing.&#62;,462}
} else
{ struct rtrb_node *x; if (da[k - 1] == 0) y = pa[k - 1]; else
{
&#60;@xref{\NODE\, , Case 3 in left-side RTRB insertion rebalancing.&#62;,466}
} &#60;@xref{\NODE\, , Case 2 in left-side RTRB insertion rebalancing.&#62;,464} break; }
This code is included in @refalso{459

 
struct rtrb_node *y = pa[k - 2]-&#62;rtrb_link[0];
if (pa[k - 2]-&#62;rtrb_link[0] != NULL && y-&#62;rtrb_color == RTRB_RED)
  { 
&#60;@xref{\NODE\, , Case 1 in right-side RTRB insertion rebalancing.&#62;,463}
} else
{ struct rtrb_node *x; if (da[k - 1] == 1) y = pa[k - 1]; else
{
&#60;@xref{\NODE\, , Case 3 in right-side RTRB insertion rebalancing.&#62;,467}
} &#60;@xref{\NODE\, , Case 2 in right-side RTRB insertion rebalancing.&#62;,465} break; }
This code is included in @refalso{459

Case 1: q's uncle is red

If node q's uncle is red, then no links need be changed. Instead, we will just recolor nodes. We reuse the code for RB insertion (@pageref{rbinscase1}):

 
&#60;@xref{\NODE\, , Case 1 in left-side RB insertion rebalancing; rb =>.&#62; rtrb,203}
This code is included in @refalso{460

 
&#60;@xref{\NODE\, , Case 1 in right-side RB insertion rebalancing; rb =>.&#62; rtrb,207}
This code is included in @refalso{461

Case 2: q is on same side of parent as parent is of grandparent

If q is a left child of its parent y and y is a left child of its own parent x, or if both q and y are right children, then we rotate at x away from y. This is the same that we would do in an unthreaded RB tree (@pageref{rbinscase2}).

However, as usual, we must make sure that threads are fixed up properly in the rotation. In particular, for case 2 in left-side rebalancing, we must convert a right thread of y, after rotation, into a null left child pointer of x, like this:

rtrbins

 
&#60;@xref{\NODE\, , Case 2 in left-side RB insertion rebalancing; rb =>.&#62; rtrb,204}
if (y-&#62;rtrb_rtag == RTRB_THREAD) 
{ y-&#62;rtrb_rtag = RTRB_CHILD; x-&#62;rtrb_link[0] = NULL; }
This code is included in @refalso{460

For the right-side rebalancing case, we must convert a null left child of y, after rotation, into a right thread of x:

rtrbins2

 
&#60;@xref{\NODE\, , Case 2 in right-side RB insertion rebalancing; rb =>.&#62; rtrb,208}
if (x-&#62;rtrb_link[1] == NULL) 
{ x-&#62;rtrb_rtag = RTRB_THREAD; x-&#62;rtrb_link[1] = y; }
This code is included in @refalso{461

Case 3: q is on opposite side of parent as parent is of grandparent

If q is a left child and its parent is a right child, or vice versa, then we have an instance of case 3, and we rotate at q's parent in the direction from q to its parent. We handle this case as seen before for unthreaded RB trees (@pageref{rbinscase3}), with the addition of fix-ups for threads during rotation.

The left-side fix-up and the code to do it look like this:

rtrbins3

 
&#60;@xref{\NODE\, , Case 3 in left-side RB insertion rebalancing; rb =>.&#62; rtrb,205}
if (x-&#62;rtrb_link[1] == NULL) 
{ x-&#62;rtrb_rtag = RTRB_THREAD; x-&#62;rtrb_link[1] = y; }
This code is included in @refalso{460

Here's the right-side fix-up and code:

rtrbins4

 
&#60;@xref{\NODE\, , Case 3 in right-side RB insertion rebalancing; rb =>.&#62; rtrb,209}
if (y-&#62;rtrb_rtag == RTRB_THREAD) 
{ y-&#62;rtrb_rtag = RTRB_CHILD; x-&#62;rtrb_link[0] = NULL; }
This code is included in @refalso{461


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

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