#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2

typedef int status;
typedef int KeyType;//關鍵域數據類型；
typedef enum color
{
	red,black
}color;
typedef struct RBTreeNode
{
	KeyType key;
	color clr;
	struct RBTreeNode *parent;
	struct RBTreeNode *lChild;
	struct RBTreeNode *rChild;
}RBTreeNode,*pRBTreeNode;


status LeftRotate(RBTreeNode **tRoot,pRBTreeNode x)
{//左旋
	if(x!=NULL&&x->rChild!=NULL)
	{
		pRBTreeNode y;
		y=x->rChild;	
		x->rChild=y->lChild;
		if(y->lChild!=NULL)
			y->lChild->parent=x;
		y->parent=x->parent;
		if(x->parent==NULL)
		{
			(*tRoot)=y;
			y->parent=NULL;
		}
		else if(x==x->parent->lChild)
			x->parent->lChild=y;
		else
			x->parent->rChild=y;
		y->lChild=x;
		x->parent=y;
		return OK;
	}
	else return FALSE;
}

status RightRotate(RBTreeNode **tRoot,pRBTreeNode y)
{//右旋
	if(y!=NULL&&y->lChild!=NULL)
	{
		pRBTreeNode x=y->lChild;
		y->lChild=x->rChild;
		if(x->rChild!=NULL)
			x->rChild->parent=y;
		x->parent=y->parent;
		if(y->parent==NULL)
		{
			(*tRoot)=x;
			x->parent=NULL;
		}
		else if(y==y->parent->lChild)
			y->parent->lChild=x;
		else
			y->parent->rChild=x;
		x->rChild=y;
		y->parent=x;
		return OK;
	}
	else return FALSE;
}

status RBTInsertFixup(RBTreeNode **tRoot,pRBTreeNode z)
{//插入調整
	pRBTreeNode y;
	while(z->parent!=NULL&&z->parent->clr==red)
	{
		if(z->parent==z->parent->parent->lChild)
		{
			y=z->parent->parent->rChild;
			if(y!=NULL&&y->clr==red)
			{//情況1
				z->parent->clr=black;
				y->clr=black;
				z->parent->parent->clr=red;
				z=z->parent->parent;

			}
			else
			{
				if(z==z->parent->rChild)
				{//情況2
					z=z->parent;
					LeftRotate(tRoot,z);
				}
				//情況3
				z->parent->clr=black;
				z->parent->parent->clr=red;
				RightRotate(tRoot,z->parent->parent);
			}
		}
		else
		{
			y=z->parent->parent->lChild;
			if(y!=NULL&&y->clr==red)
			{//情況4
				z->parent->clr=black;
				y->clr=black;
				z->parent->parent->clr=red;
				z=z->parent->parent;

			}
			else
			{
				if(z==z->parent->lChild)
				{//情況5
					z=z->parent;
					RightRotate(tRoot,z);
				}
				//情況6
				z->parent->clr=black;
				z->parent->parent->clr=red;
				LeftRotate(tRoot,z->parent->parent);
			}
		}
	}
	(*tRoot)->clr=black;
	return OK;
}

status RBTInsert(RBTreeNode **tRoot,pRBTreeNode z)
{//紅黑樹插入
	pRBTreeNode y=NULL;
	pRBTreeNode x=*tRoot;
	while(x!=NULL)
	{
		y=x;
		if(z->key<x->key)
			x=x->lChild;
		else
			x=x->rChild;
	}
	z->parent=y;
	if(y==NULL)
	{
		*tRoot=z;
		z->parent=NULL;
	}
	else if(z->key<y->key)
		y->lChild=z;
	else
		y->rChild=z;
	z->lChild=NULL;
	z->rChild=NULL;
	z->clr=red;
	RBTInsertFixup(tRoot,z);
	return OK;
}

status InorderRBTWalk(pRBTreeNode tRoot)
{//中序遍歷
	if(tRoot!=NULL)
	{
		InorderRBTWalk(tRoot->lChild);
		printf("key=%d,",tRoot->key);
		if(tRoot->clr==0)
			printf("color:red ");
		else 
			printf("color:black ");
		InorderRBTWalk(tRoot->rChild);
	}
	return OK;
}