+/* Restore red-black property after violation due to a deletion */
+void rbl_delete_fixup(rbl_t *x)
+{
+ rbl_t *w;
+
+ while(x != x->tree->top && x->color == RBL_BLACK)
+ {
+ if(x == x->parent->left)
+ {
+ w = x->parent->right;
+ if(w->color == RBL_RED)
+ {
+ w->color = RBL_BLACK;
+ x->partent->color = RBL_RED;
+ rbl_left_rotate(x->parent);
+ w = x->parent->right;
+ }
+ if(w->left->color == RBL_BLACK && w->right->color == RBL_BLACK)
+ {
+ w->color = RBL_RED;
+ x = x->parent;
+ }
+ else
+ {
+ if(w->right->color == RBL_BLACK)
+ {
+ w->left->color = RBL_BLACK;
+ w->color = RBL_RED;
+ rbl_right_rotate(w);
+ w = x->parent->right;
+ }
+ w->color = x->parent->color;
+ x->parent->color = RBL_BLACK;
+ w->right->color = RBL_BLACK;
+ rbl_left_rotate(x->parent);
+ x = x->tree->top;
+ }
+ }
+ else
+ {
+ w = x->parent->left;
+ if(w->color == RBL_RED)
+ {
+ w->color = RBL_BLACK;
+ x->partent->color = RBL_RED;
+ rbl_right_rotate(x->parent);
+ w = x->parent->left;
+ }
+ if(w->right->color == RBL_BLACK && w->left->color == RBL_BLACK)
+ {
+ w->color = RBL_RED;
+ x = x->parent;
+ }
+ else
+ {
+ if(w->left->color == RBL_BLACK)
+ {
+ w->right->color = RBL_BLACK;
+ w->color = RBL_RED;
+ rbl_left_rotate(w);
+ w = x->parent->left;
+ }
+ w->color = x->parent->color;
+ x->parent->color = RBL_BLACK;
+ w->left->color = RBL_BLACK;
+ rbl_right_rotate(x->parent);
+ x = x->tree->top;
+ }
+ }
+ }
+
+ x->color = RBL_BLACK;
+}
+
+/* Unlink node from the tree, but keep the node intact. */