while ( (x->p != &s->root) && IS_BLACK(x->v) )
{
p = x->p;
-
+
if ( x == p->l )
{
w = p->r;
/* Get new sibling W. */
w = p->r;
}
-
+
if ( IS_BLACK(w->l->v) && IS_BLACK(w->r->v) )
{
w->v = MK_RED(w->v);
/* Old w is new w->r. Old w->l is new w.*/
w = p->r;
}
-
+
w->v = SET_COLOUR(GET_VALUE(w->v), GET_COLOUR(p->v));
p->v = MK_BLACK(p->v);
w->r->v = MK_BLACK(w->r->v);
/* Get new sibling W. */
w = p->l;
}
-
+
if ( IS_BLACK(w->l->v) && IS_BLACK(w->r->v) )
{
w->v = MK_RED(w->v);
/* Old w is new w->l. Old w->r is new w.*/
w = p->l;
}
-
+
w->v = SET_COLOUR(GET_VALUE(w->v), GET_COLOUR(p->v));
p->v = MK_BLACK(p->v);
w->l->v = MK_BLACK(w->l->v);
x = y;
if ( k == x->k ) break;
}
-
+
if ( k == x->k )
{
ov = x->v;