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


GNU libavl 2.0.1

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

16.3.2 Step 3: Rebalance

When we rebalanced ordinary RB trees, we used the expressions pa[k - 1] and pa[k - 2] to refer to the parent and grandparent, respectively, of the node at which we were rebalancing, and we called that node q, though that wasn't a variable name (see section 7.4.3 Step 3: Rebalance). Now that we have parent pointers, we use a real variable q to refer to the node where we're rebalancing.

This means that we could refer to its parent and grandparent as q-&#62;prb_parent and q-&#62;prb_parent-&#62;prb_parent, respectively, but there's a small problem with that. During rebalancing, we will need to move nodes around and modify parent pointers. That means that q-&#62;prb_parent and q-&#62;prb_parent-&#62;prb_parent will be changing under us as we work. This makes writing correct code hard, and reading it even harder. It is much easier to use a pair of new variables to hold q's parent and grandparent.

That's exactly the role that f and g, respectively, play in the code below. If you compare this code to &#60;@xref{\NODE\, , \TITLE\}.&#62;{Step 3: Rebalance after RB insertion,201}, you'll also notice the way that checking that f and g are non-null corresponds to checking that the stack height is at least 3 (see Exercise 6.4.3-1 for an explanation of the reason this is a valid test).

 
q = n;
for (;;) 
{ struct prb_node *f; /* Parent of q. */ struct prb_node *g; /* Grandparent of q. */ f = q-&#62;prb_parent; if (f == NULL || f-&#62;prb_color == PRB_BLACK) break; g = f-&#62;prb_parent; if (g == NULL) break; if (g-&#62;prb_link[0] == f) {
&#60;@xref{\NODE\, , Left-side rebalancing after PRB insertion.&#62;,558}
} else
{
&#60;@xref{\NODE\, , Right-side rebalancing after PRB insertion.&#62;,562}
}
} tree-&#62;prb_root-&#62;prb_color = PRB_BLACK;
This code is included in @refalso{555

After replacing pa[k - 1] by f and pa[k - 2] by g, the cases for PRB rebalancing are distinguished on the same basis as those for RB rebalancing (see &#60;@xref{\NODE\, , Left-side rebalancing after RB insertion.&#62;,202}). One addition: cases 2 and 3 need to work with q's great-grandparent, so they stash it into a new variable h.

 
struct prb_node *y = g-&#62;prb_link[1];
if (y != NULL && y-&#62;prb_color == PRB_RED) 
  { 
&#60;@xref{\NODE\, , Case 1 in left-side PRB insertion rebalancing.&#62;,559}
} else
{ struct prb_node *h; /* Great-grandparent of q. */ h = g-&#62;prb_parent; if (h == NULL) h = (struct prb_node *) &tree-&#62;prb_root; if (f-&#62;prb_link[1] == q) {
&#60;@xref{\NODE\, , Case 3 in left-side PRB insertion rebalancing.&#62;,561}
} &#60;@xref{\NODE\, , Case 2 in left-side PRB insertion rebalancing.&#62;,560} break; }
This code is included in @refalso{557

Case 1: q's uncle is red

In this case, as before, we need only rearrange colors (@pageref{rbinscase1}). Instead of popping the top two items off the stack, we directly set up q, the next node at which to rebalance, to be the (former) grandparent of the original q.

prbins1

 
f-&#62;prb_color = y-&#62;prb_color = PRB_BLACK;
g-&#62;prb_color = PRB_RED;
q = g;
This code is included in @refalso{558

Case 2: q is the left child of its parent

If q is the left child of its parent, we rotate right at g:

prbins2

The result satisfies both RB balancing rules. Refer back to the discussion of the same case in ordinary RB trees for more details (@pageref{rbinscase2}).

 
g-&#62;prb_color = PRB_RED;
f-&#62;prb_color = PRB_BLACK;
g-&#62;prb_link[0] = f-&#62;prb_link[1];
f-&#62;prb_link[1] = g;
h-&#62;prb_link[h-&#62;prb_link[0] != g] = f;
f-&#62;prb_parent = g-&#62;prb_parent;
g-&#62;prb_parent = f;
if (g-&#62;prb_link[0] != NULL)
  g-&#62;prb_link[0]-&#62;prb_parent = g;
This code is included in @refalso{558

Case 3: q is the right child of its parent

If q is a right child, then we transform it into case 2 by rotating left at f:

prbins3

Afterward we relabel q as f and treat the result as case 2. There is no need to properly set q itself because case 2 never uses variable q. For more details, refer back to case 3 in ordinary RB trees (@pageref{rbinscase3}).

 
f-&#62;prb_link[1] = q-&#62;prb_link[0];
q-&#62;prb_link[0] = f;
g-&#62;prb_link[0] = q;
f-&#62;prb_parent = q;
if (f-&#62;prb_link[1] != NULL)
  f-&#62;prb_link[1]-&#62;prb_parent = f;
f = q;
This code is included in @refalso{558


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

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