#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
struct node
{
	struct node *parent;
	struct node *left;
	struct node *right;
	int value;
	bool isRed;
};
void yazdir (int * A, int length)
{
		int i;
        for(i=1;i<=length;i++)
                printf("%4d",A[i]);  
		printf("\n\n");
}
void inorder_yazdir(struct node * tree)
{
  if(tree == NULL)
	  return;
  inorder_yazdir(tree->left);
  printf("%4d",tree->value);
  inorder_yazdir(tree->right);
}
void tum_bilgi_yazdir(struct node * tree)
{
  if(tree == NULL)
	  return;
  printf("Node:%4d\nAddress:%d\nParent:%d\nLeft:%d\nRight:%d\nColor:%c\n\n",tree->value,tree,tree->parent,tree->left,tree->right,(tree->isRed==true?'R':'B'));
  tum_bilgi_yazdir(tree->left);
  tum_bilgi_yazdir(tree->right);
}
void right_rotate(struct node *& tree,struct node * new_node)
{
	struct node * y = new_node->left;
	new_node->left = y->right;
	if(y->right!=NULL)
	{
		y->right->parent = new_node;
	}
	y->parent = new_node->parent;
	if(new_node->parent == NULL)
		tree = y;
	else if(new_node == new_node->parent->right)
		new_node->parent->right = y;
	else
		new_node->parent->left = y;
	y->right = new_node;
	new_node ->parent = y;
}
void left_rotate(struct node *& tree,struct node * new_node)
{
	struct node * y = new_node->right;
	struct node * temp;
	new_node->right = y->left;
	if(y->left!=NULL)
	{
		y->left->parent = new_node;
	}
	temp = new_node->parent;
	y->parent = temp;
	if(new_node->parent == NULL)
		tree = y;
	else if(new_node == new_node->parent->left)
		new_node->parent->left = y;
	else
		new_node->parent->right = y;
	y->left = new_node;
	new_node ->parent = y;
}
void rb_insert_fixup(struct node *& tree,struct node *& new_node)
{
	struct node * y;
	while(new_node!= tree && new_node->parent->isRed==true)
	{
		if(new_node->parent==new_node->parent->parent->left)
		{
			y = new_node->parent->parent->right;
			if(y!=NULL && y->isRed==true)
			{
				//case1
				new_node->parent->isRed=false;
				y->isRed=false;
				new_node->parent->parent->isRed= true;
				new_node = new_node->parent->parent;
			}
			else 
			{
				if(new_node == new_node->parent->right)
				{
				//case2
				new_node = new_node->parent;
				left_rotate(tree,new_node);
				}
				//case3
				new_node->parent->isRed = false;
				new_node->parent->parent->isRed = true;
				right_rotate(tree,new_node->parent->parent);
			}
 
		}
		else
		{
			y = new_node->parent->parent->left;
			if(y!=NULL && y->isRed==true)
			{
				//case1
				new_node->parent->isRed=false;
				y->isRed=false;
				new_node->parent->parent->isRed= true;
				new_node = new_node->parent->parent;
			}
			else 
			{
				if(new_node == new_node->parent->left)
				{
				//case2
				new_node = new_node->parent;
				right_rotate(tree,new_node);
				}
				//case3
				new_node->parent->isRed = false;
				new_node->parent->parent->isRed = true;
				left_rotate(tree,new_node->parent->parent);
			}
 
		}
	}
	tree->isRed = false;
}
void rb_insert(struct node *& tree, struct node *& new_node)
{
	struct node * y = NULL;
	struct node * x = tree;
	while(x!=NULL)
	{
		y=x;
		if(new_node->value<x->value)
			x=x->left;
		else
			x=x->right;
	}
	new_node->parent = y;
	if(y==NULL)
		tree = new_node;
	else if(new_node->value<y->value)
		y->left=new_node;
	else
		y->right=new_node;
 
	new_node->left=NULL;
	new_node->right=NULL;
	new_node->isRed=true;
	rb_insert_fixup(tree,new_node);
}
void main()
{
		int *A;
        struct node * tree = NULL;
		struct node * new_node;
		int n;//eleman sayısı
		int i,j,k;		
		int secim;
		srand(time(NULL));
		printf("Rastgele sayilar icin - 1 \n Kendiniz girmek icin - 2 ");
        scanf("%d",&secim);
		if(secim == 1)
		{
			printf("Eklenecek eleman sayisi : ");
			scanf("%d",&n);
			A = (int *)malloc(sizeof(int)*n+1);
			for(i=1;i<=n;i++)
			{
				new_node = (struct node*)malloc(sizeof(struct node));
				new_node->isRed=true;
				new_node->left=NULL;
				new_node->parent=NULL;
				new_node->right=NULL;
				A[i]=rand()%100;
				new_node->value = A[i];
				rb_insert(tree,new_node) ;
			}
		}
		else
		{
			printf("Eklenecek eleman sayisi : ");
			scanf("%d",&n);
			A = (int *)malloc(sizeof(int)*n+1);
			for(i=1;i<=n;i++){
 
				new_node = (struct node*)malloc(sizeof(struct node));
				new_node->isRed=true;
				new_node->left=NULL;
				new_node->parent=NULL;
				new_node->right=NULL;
				printf("Eleman : ");
				scanf("%d",&A[i]);
				new_node->value = A[i];
				rb_insert(tree,new_node);
			}
		}
		printf("Eklenmesi gereken sayilar :");
		yazdir(A,n);
		printf("Tum Bilgiler:\n");
		tum_bilgi_yazdir(tree);
		printf("\n\n");
		//heap_sort(A,n);		
		printf("Inorder Gezinti Sonrasi:");
        inorder_yazdir(tree);	
		printf("\n\n");
 
}