15.3.3 Symmetric Case

564. <Right-side rebalancing after PRB insertion 564> =
struct prb_node *y = g->prb_link[0];
if (y != NULL && y->prb_color == PRB_RED)
  { 
    <Case 1 in right-side PRB insertion rebalancing 565> 
  }
else 
  {
    struct prb_node *h; /* Great-grandparent of q. */

    h = g->prb_parent;
    if (h == NULL)
      h = (struct prb_node *) &tree->prb_root;

    if (f->prb_link[0] == q)
      { 
        <Case 3 in right-side PRB insertion rebalancing 567> 
      }

    <Case 2 in right-side PRB insertion rebalancing 566>
    break;
  }

This code is included in 559.

565. <Case 1 in right-side PRB insertion rebalancing 565> =
f->prb_color = y->prb_color = PRB_BLACK;
g->prb_color = PRB_RED;
q = g;

This code is included in 564.

566. <Case 2 in right-side PRB insertion rebalancing 566> =
g->prb_color = PRB_RED;
f->prb_color = PRB_BLACK;

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

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

This code is included in 564.

567. <Case 3 in right-side PRB insertion rebalancing 567> =
f->prb_link[0] = q->prb_link[1];
q->prb_link[1] = f;
g->prb_link[1] = q;
f->prb_parent = q;
if (f->prb_link[0] != NULL)
  f->prb_link[0]->prb_parent = f;

f = q;

This code is included in 564.