15.4.4 Symmetric Case

578. <Right-side rebalancing after PRB deletion 578> =
struct prb_node *w = f->prb_link[0];

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

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 right-side PRB deletion rebalancing 580> 
  }
else 
  {
    if (w->prb_link[0] == NULL 
        || w->prb_link[0]->prb_color == PRB_BLACK)
      { 
        <Transform right-side PRB deletion rebalancing case 3 into case 2 582> 
      }

    <Case 2 in right-side PRB deletion rebalancing 581>
    break;
  }

This code is included in 571.

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

f->prb_link[0] = w->prb_link[1];
w->prb_link[1] = 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[0];

w->prb_parent = f;

This code is included in 578.

580. <Case 1 in right-side PRB deletion rebalancing 580> =
w->prb_color = PRB_RED;

This code is included in 578.

581. <Case 2 in right-side PRB deletion rebalancing 581> =
w->prb_color = f->prb_color;
f->prb_color = PRB_BLACK;
w->prb_link[0]->prb_color = PRB_BLACK;

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

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

This code is included in 578.

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

This code is included in 578.