15.4.2 Step 3: Rebalance [ToC] [Index]     [Skip Back] [Skip Fwd]     [Prev] [Up] [Next]

The rebalancing code is easily related to the analogous code for ordinary RB trees in <Rebalance after RB deletion 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–.

571. <Step 3: Rebalance tree after PRB deletion 571> =
if (p->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->prb_link[dir]; if (x != NULL && x->prb_color == PRB_RED) { x->prb_color = PRB_BLACK; break; } if (f == (struct prb_node *) &tree->prb_root) break; g = f->prb_parent; if (g == NULL) g = (struct prb_node *) &tree->prb_root; if (dir == 0) {
            <Left-side rebalancing after PRB deletion 572>
          } else
          {
            <Right-side rebalancing after PRB deletion 578>
          } t = f; f = f->prb_parent; if (f == NULL) f = (struct prb_node *) &tree->prb_root; dir = f->prb_link[0] != t; } }

This code is included in 566.

The code to distinguish rebalancing cases in PRB trees is almost identical to <Left-side rebalancing after RB deletion 227>.

572. <Left-side rebalancing after PRB deletion 572> =
struct prb_node *w = f->prb_link[1];

if (w->prb_color == PRB_RED) 
  { 
    <Ensure w is black in left-side PRB deletion rebalancing 573>
  } if ((w->prb_link[0] == NULL
     || w->prb_link[0]->prb_color == PRB_BLACK) && (w->prb_link[1] == NULL
        || w->prb_link[1]->prb_color == PRB_BLACK)) {
    <Case 1 in left-side PRB deletion rebalancing 574>
  } else
  { if (w->prb_link[1] == NULL
        || w->prb_link[1]->prb_color == PRB_BLACK) {
        <Transform left-side PRB deletion rebalancing case 3 into case 2 576>
      } <Case 2 in left-side PRB deletion rebalancing 575> break; }

This code is included in 571.

Case Reduction: Ensure w is black

The case reduction code is much like that for plain RB trees (see 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.

[Click here for plain-text rendering]

573. <Ensure w is black in left-side PRB deletion rebalancing 573> =
w->prb_color = PRB_BLACK;
f->prb_color = PRB_RED;

f->prb_link[1] = w->prb_link[0];
w->prb_link[0] = f;
g->prb_link[g->prb_link[0] != f] = w;

w->prb_parent = f->prb_parent;
f->prb_parent = w;

g = w;
w = f->prb_link[1];

w->prb_parent = f;

This code is included in 572.

Case 1: w has no red children

Case 1 is trivial. No changes from ordinary RB trees are necessary (see rbdelcase1).

574. <Case 1 in left-side PRB deletion rebalancing 574> =
<Case 1 in left-side RB deletion rebalancing; rb => prb 229>

This code is included in 572.

Case 2: w's right child is red

The changes from ordinary RB trees (see rbdelcase2) for case 2 follow the same pattern.

575. <Case 2 in left-side PRB deletion rebalancing 575> =
w->prb_color = f->prb_color;
f->prb_color = PRB_BLACK;
w->prb_link[1]->prb_color = PRB_BLACK;

f->prb_link[1] = w->prb_link[0];
w->prb_link[0] = f;
g->prb_link[g->prb_link[0] != f] = w;

w->prb_parent = f->prb_parent;
f->prb_parent = w;
if (f->prb_link[1] != NULL)
  f->prb_link[1]->prb_parent = f;

This code is included in 572.

Case 3: w's left child is red

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

[Click here for plain-text rendering]

576. <Transform left-side PRB deletion rebalancing case 3 into case 2 576> =
struct prb_node *y = w->prb_link[0];
y->prb_color = PRB_BLACK;
w->prb_color = PRB_RED;
w->prb_link[0] = y->prb_link[1];
y->prb_link[1] = w;
if (w->prb_link[0] != NULL)
  w->prb_link[0]->prb_parent = w;
w = f->prb_link[1] = y;
w->prb_link[1]->prb_parent = w;

This code is included in 572.