#include <stdio.h>
#include<stdlib.h>
struct node
{
int data;
int emptybit; //empty bit 1 means node is empty
char colour;
struct node* parent;
struct node* left_child;
struct node* right_child;
};
struct node* root_node;
//visit function
void visit(struct node* x)
{
if(x!=NULL){
visit(x->left_child);
if(x->parent==NULL){
printf("%d %c NIL\n",x
->data
,x
->colour
); }
else{
printf("%d %c %d\n",x
->data
,x
->colour
,x
->parent
->data
); }
visit(x->right_child);
}
return;
}
// pre_fix_tour function will do the the tour of tree
void pre_fix_tour(struct node* x)
{
if(x==NULL)
else
visit(x);
return;
}
//uncle function will return the pointer to uncle of the node
struct node* uncle(struct node* x)
{
if(x->parent->data<x->parent->parent->data){
return x->parent->parent->right_child;
}
else {
return x->parent->parent->left_child;
}
}
//grandparent function will return the pointer to grandparent of node
struct node* grandparent(struct node *x)
{
return x->parent->parent;
}
//leftR will rotate the tree to the left about the given node
void leftR(struct node* x)
{
struct node* z;
z=x->parent;
if(z->parent==NULL){
z->right_child=x->left_child;
if(x->left_child!=NULL){
x->left_child->parent=z;
}
x->parent=NULL;
root_node=x;
//printf("%d ",root_node->data);
z->parent=x;
x->left_child=z;
}
else{
z->right_child=x->left_child;
if(x->left_child!=NULL){
x->left_child->parent=z;
}
x->parent=z->parent;
if(z->parent->data>z->data){ //z is a left child
z->parent->left_child=x;
}
else
z->parent->right_child=x;
x->left_child=z;
z->parent=x;
}
return;
}
//rightR will rotate the tree to right
void rightR(struct node* x)
{
struct node* z;
z=x->parent;
if(z->parent==NULL){
z->left_child=x->right_child;
if(x->right_child!=NULL){
x->right_child->parent=z;
}
x->parent=NULL;
root_node=x;
//printf("%d ",root_node->data);
z->parent=x;
x->right_child=z;
}
else{
z->left_child=x->right_child;
if(x->right_child!=NULL){
x->right_child->parent=z;
}
x->parent=z->parent;
if(z->parent->data>z->data){ //z is a left child
z->parent->left_child=x;
}
x->right_child=z;
z->parent=x;
}
return;
}
//make_far_child function will make the near child a far child
void make_far_child(struct node*x)
{
if(x->parent->data<x->parent->parent->data){
leftR(x);
}
else{
rightR( x);
}
return;
}
//near_child function will check if the given node is near
int near_child(struct node* x)
{
if(x->parent->data<x->parent->parent->data){
if(x->data>=x->parent->data)
return 1;
else
return 0;
}
else{
if(x->data<x->parent->data)
return 1;
else
return 0;
}
}
//modify function will re balance the tree
void modify(struct node* x)
{
if(x->parent==NULL ){
return;
}
else{
if(grandparent(x)==NULL){
if(x->parent->colour=='R'){
x->colour='B';
}
}
else{
if(x->parent->colour=='B'){
if(uncle(x)==NULL){
if(x->parent->data<grandparent(x)->data){
rightR(x->parent);
}
else
leftR(x->parent);
}
}
else if(x->parent->colour=='R'){
if(uncle(x)==NULL)
{
if(x->parent->data>=grandparent(x)->data){
leftR(x->parent);
if(x->parent->colour=='R'){
x->parent->colour='B';
x->parent->left_child->colour='R';
}
}
else{
rightR(x->parent);
if(x->parent->colour=='R'){
x->parent->colour='B';
x->parent->right_child->colour='R';
}
}
}
else if(uncle(x)->colour=='R'){ //case 1
x->parent->colour='B';
uncle(x)->colour='B';
grandparent(x)->colour='R';
modify(grandparent(x));
}
else{
if(near_child(x)){ //case2
make_far_child(x);
if(x->data>x->left_child->data){
modify(x->left_child);
}
else
modify(x->right_child);
}
else{ //case 3
if(x->parent->data>x->data){
x->parent->colour='B';
grandparent(x)->colour='R';
rightR(x->parent);
}
else{
x->parent->colour='B';
grandparent(x)->colour='R';
leftR(x->parent);
}
}
}
}
}
}
return;
}
//inert function takes argument a pointer to node
void insert(struct node* x,int a)
{
if(x->emptybit==1){
x->data=a;
x->emptybit=0;
x->colour='R';
//printf("%d ",x->data);
modify(x);
}
else{
if((x->data)>a){
if(x->left_child==NULL){
x
->left_child
=(struct node
*)malloc(sizeof(struct node
)); x->left_child->parent=x;
x->left_child->emptybit=1;
insert(x->left_child,a);
}
else{
insert(x->left_child,a);
}
}
else{
if(x->right_child==NULL){
x
->right_child
=(struct node
*)malloc(sizeof(struct node
)); x->right_child->parent=x;
x->right_child->emptybit=1;
insert(x->right_child,a);
}
else{
insert(x->right_child,a);
}
}
}
return;
}
// main function
int main()
{
int i,n;
int a[100];
struct node RBtree;
for(i=0;i<n;i++){
}
// all the elements to be inserted in the tree are stored in array a
RBtree.data=a[0];
RBtree.emptybit=0;
RBtree.colour= 'R';
RBtree.parent=NULL;
RBtree.left_child=NULL;
RBtree.right_child=NULL;
//declaration of RBtree
root_node=&RBtree;
for(i=1;i<n;i++){
insert(root_node,a[i]);
}
root_node->colour='B';
pre_fix_tour(root_node);
return 0;
}