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


GNU libavl 2.0.1

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

16.4.2 Step 3: Rebalance

The rebalancing code is easily related to the analogous code for ordinary RB trees in &#60;@xref{\NODE\, , Rebalance after RB deletion.&#62;,226}. As we carefully set up in step 2, we use f as the top of stack node and dir as the side of f from which a node was deleted. These variables f and dir were formerly represented by pa[k - 1] and da[k - 1], respectively. Additionally, variable g is used to represent the parent of f. Formerly the same node was referred to as pa[k - 2].

The code at the end of the loop simply moves f and dir up one level in the tree. It has the same effect as did popping the stack with k--.

 
if (p-&#62;prb_color == PRB_BLACK) 
{ for (;;)
{ struct prb_node *x; /* Node we want to recolor black if possible. */ struct prb_node *g; /* Parent of f. */ struct prb_node *t; /* Temporary for use in finding parent. */ x = f-&#62;prb_link[dir]; if (x != NULL && x-&#62;prb_color == PRB_RED) { x-&#62;prb_color = PRB_BLACK; break; } if (f == (struct prb_node *) &tree-&#62;prb_root) break; g = f-&#62;prb_parent; if (g == NULL) g = (struct prb_node *) &tree-&#62;prb_root; if (dir == 0) {
&#60;@xref{\NODE\, , Left-side rebalancing after PRB deletion.&#62;,572}
} else
{
&#60;@xref{\NODE\, , Right-side rebalancing after PRB deletion.&#62;,578}
} t = f; f = f-&#62;prb_parent; if (f == NULL) f = (struct prb_node *) &tree-&#62;prb_root; dir = f-&#62;prb_link[0] != t; } }
This code is included in @refalso{566

The code to distinguish rebalancing cases in PRB trees is almost identical to &#60;@xref{\NODE\, , Left-side rebalancing after RB deletion.&#62;,227}.

 
struct prb_node *w = f-&#62;prb_link[1];
if (w-&#62;prb_color == PRB_RED) 
  { 
&#60;@xref{\NODE\, , Ensure w.&#62; is black in left-side PRB deletion rebalancing,573}
} if ((w-&#62;prb_link[0] == NULL
|| w-&#62;prb_link[0]-&#62;prb_color == PRB_BLACK) && (w-&#62;prb_link[1] == NULL
|| w-&#62;prb_link[1]-&#62;prb_color == PRB_BLACK)) {
&#60;@xref{\NODE\, , Case 1 in left-side PRB deletion rebalancing.&#62;,574}
} else
{ if (w-&#62;prb_link[1] == NULL
|| w-&#62;prb_link[1]-&#62;prb_color == PRB_BLACK) {
&#60;@xref{\NODE\, , Transform left-side PRB deletion rebalancing case 3 into case 2.&#62;,576}
} &#60;@xref{\NODE\, , Case 2 in left-side PRB deletion rebalancing.&#62;,575} break; }
This code is included in @refalso{571

Case Reduction: Ensure w is black

The case reduction code is much like that for plain RB trees (@pageref{rbdcr}), with pa[k - 1] replaced by f and pa[k - 2] replaced by g. Instead of updating the stack, we change g. Node f need not change because it's already what we want it to be. We also need to update parent pointers for the rotation.

prbdr1

 
w-&#62;prb_color = PRB_BLACK;
f-&#62;prb_color = PRB_RED;
f-&#62;prb_link[1] = w-&#62;prb_link[0];
w-&#62;prb_link[0] = f;
g-&#62;prb_link[g-&#62;prb_link[0] != f] = w;
w-&#62;prb_parent = f-&#62;prb_parent;
f-&#62;prb_parent = w;
g = w;
w = f-&#62;prb_link[1];
w-&#62;prb_parent = f;
This code is included in @refalso{572

Case 1: w has no red children

Case 1 is trivial. No changes from ordinary RB trees are necessary (@pageref{rbdelcase1}).

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

Case 2: w's right child is red

The changes from ordinary RB trees (@pageref{rbdelcase2}) for case 2 follow the same pattern.

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

Case 3: w's left child is red

The code for case 3 in ordinary RB trees (@pageref{rbdelcase3}) needs slightly more intricate changes than case 1 or case 2, so the diagram below may help to clarify:

prbdr3

 
struct prb_node *y = w-&#62;prb_link[0];
y-&#62;prb_color = PRB_BLACK;
w-&#62;prb_color = PRB_RED;
w-&#62;prb_link[0] = y-&#62;prb_link[1];
y-&#62;prb_link[1] = w;
if (w-&#62;prb_link[0] != NULL)
  w-&#62;prb_link[0]-&#62;prb_parent = w;
w = f-&#62;prb_link[1] = y;
w-&#62;prb_link[1]-&#62;prb_parent = w;
This code is included in @refalso{572


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

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