15.4.2 Step 3: Rebalance

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

573. <Step 3: Rebalance tree after PRB deletion 573> =
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 574> 
          }
        else 
          { 
            <Right-side rebalancing after PRB deletion 580> 
          }

        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 568.

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

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

if (w->prb_color == PRB_RED) 
  { 
    <Ensure w is black in left-side PRB deletion rebalancing 575> 
  }

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 576> 
  }
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 578> 
      }

    <Case 2 in left-side PRB deletion rebalancing 577>
    break;
  }

This code is included in 573.

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.

575. <Ensure w is black in left-side PRB deletion rebalancing 575> =
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 574.

Case 1: w has no red children

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

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

This code is included in 574.

Case 2: w's right child is red

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

577. <Case 2 in left-side PRB deletion rebalancing 577> =
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 574.

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:

578. <Transform left-side PRB deletion rebalancing case 3 into case 2 578> =
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 574.