struct prb_node *s = r->prb_link[0];
while (s->prb_link[0] != NULL)
  s = s->prb_link[0];
r = s->prb_parent;
r->prb_link[0] = s->prb_link[1];
s->prb_link[0] = p->prb_link[0];
s->prb_link[1] = p->prb_link[1];
q->prb_link[dir] = s;
if (s->prb_link[0] != NULL)
  s->prb_link[0]->prb_parent = s;
s->prb_link[1]->prb_parent = s;
s->prb_parent = p->prb_parent;
if (r->prb_link[0] != NULL)
  r->prb_link[0]->prb_parent = r;

t = p->prb_color;
p->prb_color = s->prb_color;
s->prb_color = t;

f = r;
dir = 0;