#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
// red or black colour
char colour;
struct node *parent;
struct node *left_child;
struct node *right_child;
};
struct node* root=NULL;
//global_variable
void visit(struct node* p);
void pre_fix_tour(struct node* p);
void left_rotate(struct node *x)
{
struct node *y;
// set y
y=x->right_child;
// y's left made x's right child
x->right_child=y->left_child;
if(y->left_child != NULL)
y->left_child->parent = x;
// x's parent made y's parent
y->parent=x->parent;
if(x->parent == NULL)
root=y;
// if x was left child
else if(x == x->parent->left_child)
x->parent->left_child=y;
else
x->parent->right_child=y;
// put x on y's left
y->left_child=x;
x->parent=y;
}
void right_rotate(struct node *y)
{
struct node *x;
// set x as y's left child
x=y->left_child;
y->left_child=x->right_child;
if (x->right_child != NULL)
x->right_child->parent=y;
// x's parent made y's parent
x->parent=y->parent;
if(y->parent == NULL)
root=x;
else if(y == y->parent->left_child)
y->parent->left_child=x;
else
y->parent->right_child=x;
// put y on x's right
x->right_child=y;
y->parent=x;
}
void re_balance(struct node *z)
{
struct node *y;
//no problem if z has black parent
while ((z->parent!=NULL)&&(z->parent->colour == 'R'))
{
// z's parent is left child
if (z->parent == z->parent->parent->left_child)
{
// uncle of z
y=z->parent->parent->right_child;
//case 1 parent and uncle of z are red
if ((y!= NULL)&&(y->colour == 'R'))
{
z->parent->colour='B';
y->colour='B';
z->parent->parent->colour='R';
z=z->parent->parent;
}
//uncle black
//case 2 z is right child and uncle is black
else if (z == z->parent->right_child)
{
z=z->parent;
left_rotate(z);
}
//case 3
// z is left child and uncle is black
z->parent->colour='B';
z->parent->parent->colour='R';
right_rotate(z->parent->parent);
}
//z's parent is right child
//same as if only 'right' and 'left' interchanged
else
{
y=z->parent->parent->left_child;
if((y!= NULL)&&(y->colour == 'R'))
{
z->parent->colour='B';
y->colour='B';
z->parent->parent->colour='R';
z=z->parent->parent;
}
else if(z == z->parent->left_child)
{
z=z->parent;
right_rotate(z);
}
z->parent->colour='B';
z->parent->parent->colour='R';
left_rotate(z->parent->parent);
}
}
root->colour='B';
}
void insert(int data)
{
//memory allocation
struct node
*z
=(struct node
*)malloc(sizeof(struct node
)); z->data=data;
z->left_child=NULL;
z->right_child=NULL;
// new node has red colour to easily satisfy tree properties
z->colour='R';
struct node *x=root;
struct node *y=NULL;
//if tree is empty make new node as the root
if (x == NULL )
{
root=z;
// root should be black in colour
root->colour='B';
return;
}
// if tree has elements
while (x != NULL)
{
y=x;
//to get parent of x as loop ends
if (z->data < x->data)
x=x->left_child;
else
x=x->right_child;
}
z->parent=y;
if (y == NULL)
root=z;
//checks whether a be left or right child
else if(z->data < y->data )
y->left_child=z;
else
y->right_child=z;
// z is leaf node here
z->left_child=NULL;
z->right_child=NULL;
z->colour='R';
// to satisfy red black tree properties
re_balance(z);
}
void pre_fix_tour(struct node* p)
{
//no element
if(p == NULL)
return ;
//if element present
else
visit(p);
}
// prints in ascending order
void visit(struct node* p)
{
pre_fix_tour(p->left_child);
if (p->parent == NULL)
printf("%d %c NIL \n",p
->data
,p
->colour
);
else
printf("%d %c %d \n",p
->data
,p
->colour
,p
->parent
->data
);
pre_fix_tour(p->right_child);
}
int main()
{
int n;
//no of elements
int i,a_i;
for(i=0;i<n;i++)
{
insert(a_i);
}
pre_fix_tour(root);
//visits elements in sorted order
return 0;
}