15.3.3 Symmetric Case [ToC] [Index]     [Skip Back]     [Prev] [Up] [Next]

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.