#include <stdio.h>
#include <stdlib.h>
enum COLOR {Red, Black};
typedef struct tree_node {
int data;
struct tree_node *right;
struct tree_node *left;
struct tree_node *parent;
enum COLOR color;
}tree_node;
typedef struct red_black_tree {
tree_node *root;
tree_node *NIL;
}red_black_tree;
tree_node* new_tree_node(int data) {
tree_node* n = malloc(sizeof(tree_node));
n->left = NULL;
n->right = NULL;
n->parent = NULL;
n->data = data;
n->color = Red;
return n;
}
red_black_tree* new_red_black_tree() {
red_black_tree *t = malloc(sizeof(red_black_tree));
tree_node *nil_node = malloc(sizeof(tree_node));
nil_node->left = NULL;
nil_node->right = NULL;
nil_node->parent = NULL;
nil_node->color = Black;
nil_node->data = 0;
t->NIL = nil_node;
t->root = t->NIL;
return t;
}
void left_rotate(red_black_tree *t, tree_node *x) {
tree_node *y = x->right;
x->right = y->left;
if(y->left != t->NIL) {
y->left->parent = x;
}
y->parent = x->parent;
if(x->parent == t->NIL) { //x is root
t->root = y;
}
else if(x == x->parent->left) { //x is left child
x->parent->left = y;
}
else { //x is right child
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void right_rotate(red_black_tree *t, tree_node *x) {
tree_node *y = x->left;
x->left = y->right;
if(y->right != t->NIL) {
y->right->parent = x;
}
y->parent = x->parent;
if(x->parent == t->NIL) { //x is root
t->root = y;
}
else if(x == x->parent->right) { //x is left child
x->parent->right = y;
}
else { //x is right child
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
void insertion_fixup(red_black_tree *t, tree_node *z) {
while(z->parent->color == Red) {
if(z->parent == z->parent->parent->left) { //z.parent is the left child
tree_node *y = z->parent->parent->right; //uncle of z
if(y->color == Red) { //case 1
z->parent->color = Black;
y->color = Black;
z->parent->parent->color = Red;
z = z->parent->parent;
}
else { //case2 or case3
if(z == z->parent->right) { //case2
z = z->parent; //marked z.parent as new z
left_rotate(t, z);
}
//case3
z->parent->color = Black; //made parent black
z->parent->parent->color = Red; //made parent red
right_rotate(t, z->parent->parent);
}
}
else { //z.parent is the right child
tree_node *y = z->parent->parent->left; //uncle of z
if(y->color == Red) {
z->parent->color = Black;
y->color = Black;
z->parent->parent->color = Red;
z = z->parent->parent;
}
else {
if(z == z->parent->left) {
z = z->parent; //marked z.parent as new z
right_rotate(t, z);
}
z->parent->color = Black; //made parent black
z->parent->parent->color = Red; //made parent red
left_rotate(t, z->parent->parent);
}
}
}
t->root->color = Black;
}
void insert(red_black_tree *t, tree_node *z) {
tree_node* y = t->NIL; //variable for the parent of the added node
tree_node* temp = t->root;
while(temp != t->NIL) {
y = temp;
if(z->data < temp->data)
temp = temp->left;
else
temp = temp->right;
}
z->parent = y;
if(y == t->NIL) { //newly added node is root
t->root = z;
}
else if(z->data < y->data) //data of child is less than its parent, left child
y->left = z;
else
y->right = z;
z->right = t->NIL;
z->left = t->NIL;
insertion_fixup(t, z);
}
void rb_transplant(red_black_tree *t, tree_node *u, tree_node *v) {
if(u->parent == t->NIL)
t->root = v;
else if(u == u->parent->left)
u->parent->left = v;
else
u->parent->right = v;
v->parent = u->parent;
}
tree_node* minimum(red_black_tree *t, tree_node *x) {
while(x->left != t->NIL)
x = x->left;
return x;
}
void rb_delete_fixup(red_black_tree *t, tree_node *x) {
while(x != t->root && x->color == Black) {
if(x == x->parent->left) {
tree_node *w = x->parent->right;
if(w->color == Red) {
w->color = Black;
x->parent->color = Red;
left_rotate(t, x->parent);
w = x->parent->right;
}
if(w->left->color == Black && w->right->color == Black) {
w->color = Red;
x = x->parent;
}
else {
if(w->right->color == Black) {
w->left->color = Black;
w->color = Red;
right_rotate(t, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = Black;
w->right->color = Black;
left_rotate(t, x->parent);
x = t->root;
}
}
else {
tree_node *w = x->parent->left;
if(w->color == Red) {
w->color = Black;
x->parent->color = Red;
right_rotate(t, x->parent);
w = x->parent->left;
}
if(w->right->color == Black && w->left->color == Black) {
w->color = Red;
x = x->parent;
}
else {
if(w->left->color == Black) {
w->right->color = Black;
w->color = Red;
left_rotate(t, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = Black;
w->left->color = Black;
right_rotate(t, x->parent);
x = t->root;
}
}
}
x->color = Black;
}
void rb_delete(red_black_tree *t, tree_node *z) {
tree_node *y = z;
tree_node *x;
enum COLOR y_orignal_color = y->color;
if(z->left == t->NIL) {
x = z->right;
rb_transplant(t, z, z->right);
}
else if(z->right == t->NIL) {
x = z->left;
rb_transplant(t, z, z->left);
}
else {
y = minimum(t, z->right);
y_orignal_color = y->color;
x = y->right;
if(y->parent == z) {
x->parent = z;
}
else {
rb_transplant(t, y, y->right);
y->right = z->right;
y->right->parent = y;
}
rb_transplant(t, z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if(y_orignal_color == Black)
rb_delete_fixup(t, x);
}
void inorder(red_black_tree *t, tree_node *n) {
if(n != t->NIL) {
inorder(t, n->left);
printf("%d\n", n->data);
inorder(t, n->right);
}
}
int main() {
red_black_tree *t = new_red_black_tree();
tree_node *a, *b, *c, *d, *e, *f, *g, *h, *i, *j, *k, *l, *m;
a = new_tree_node(10);
b = new_tree_node(20);
c = new_tree_node(30);
d = new_tree_node(100);
e = new_tree_node(90);
f = new_tree_node(40);
g = new_tree_node(50);
h = new_tree_node(60);
i = new_tree_node(70);
j = new_tree_node(80);
k = new_tree_node(150);
l = new_tree_node(110);
m = new_tree_node(120);
insert(t, a);
insert(t, b);
insert(t, c);
insert(t, d);
insert(t, e);
insert(t, f);
insert(t, g);
insert(t, h);
insert(t, i);
insert(t, j);
insert(t, k);
insert(t, l);
insert(t, m);
rb_delete(t, a);
rb_delete(t, m);
inorder(t, t->root);
return 0;
}
