#include<iostream>
#include<cstdlib>
using namespace std;

#define RED 1    
#define BLACK 0
typedef struct TreeNode
{
int Element;
int Color;
TreeNode *Parent;
TreeNode *Left;
TreeNode *Right;
TreeNode()
{
Color=BLACK;   //let initial node become black
}
}*MyRBTree;

MyRBTree NullNode=NULL;
MyRBTree Root;

void MakeEmpty(MyRBTree &T);
void InorderTraverse(const MyRBTree T);
MyRBTree Find(const MyRBTree T,int X);  
MyRBTree FindMin(const MyRBTree T);
MyRBTree FindMax(const MyRBTree T);
void LeftSingleRotate(MyRBTree X);
void RightSingleRotate(MyRBTree X);
void FixUpInsert(MyRBTree Z);  
void Insert(int Data); //insert a element by non-recursive way
void Transplant(MyRBTree U,MyRBTree V);
void FixUpDelete(MyRBTree X);
void Delete(MyRBTree &Z);
int Height(MyRBTree T);

int main()
{
NullNode=new TreeNode;
MyRBTree Temp=NULL;
int H;  //tree's height
//MakeEmpty(Root);
Root=NullNode;
int i,a[16]={1,2,3,5,6,7,9,11,12,8,15,22,17,20,21,29};
for(i=0;i<16;i++)
{
cout <<a[i] <<' ' ;
Insert(a[i]);
}
cout <<endl ; 
InorderTraverse(Root);
H=Height(Root);
cout <<endl <<"树高为 "<<H <<endl ;

Temp=FindMin(Root);
cout <<Temp->Element <<endl ;

Temp=FindMax(Root);
cout <<Temp->Element <<endl ;

Temp=Find(Root,1);      //delete 1
if(Temp)
{
   Delete(Temp);
   InorderTraverse(Root);
   cout <<endl ;
    }

Temp=Find(Root,17);  //delete 2
if(Temp)
{
Delete(Temp);
   InorderTraverse(Root);
   cout <<endl ;
    }
    
    Temp=Find(Root,22);  //delete 22
if(Temp)
{
Delete(Temp);
   InorderTraverse(Root);
   cout <<endl ;
    }
    
    Temp=Find(Root,8);  //delete 8
if(Temp)
{
Delete(Temp);
   InorderTraverse(Root);
   H=Height(Root);
   cout <<endl <<"树高为 "<<H <<endl ;
   cout <<endl ;
    }
    
MakeEmpty(Root);
return 0;
}

void MakeEmpty(MyRBTree &T)   
{
if(T!=NullNode)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
delete T;
T=NULL;
}
}

void InorderTraverse(const MyRBTree T)
{
if(T!=NullNode)
{
InorderTraverse(T->Left);
cout <<T->Element <<' ' ;
InorderTraverse(T->Right);
}
}

MyRBTree Find(const MyRBTree T,int X)  //find a element's position
{
if(T==NULL) return NULL;
else if(X<T->Element) return Find(T->Left,X);
else if(X>T->Element) return Find(T->Right,X);
else return T;
}

MyRBTree FindMin(const MyRBTree T)  //find the min's position
{
if(T->Left!=NullNode) return FindMin(T->Left);
else return T;
}

MyRBTree FindMax(const MyRBTree T)  //find the max position
{
if(T->Right!=NullNode) return FindMax(T->Right);
else return T;
}

int Height(MyRBTree T)   //get tree's height
{
int HeightLeft;
int HeightRight;
if(T==NullNode) return 0;
HeightLeft=Height(T->Left);
HeightRight=Height(T->Right);
return HeightLeft>HeightRight?(HeightLeft+1):(HeightRight+1);
}

/*
因为RB树之间的节点连接相比AVL树多了一个Parent指针，所以比AVL的单旋转略为复杂
其增加部分主要是为了消除旧节点间的Parent和增加新节点间的Parent连接 
*/
void LeftSingleRotate(MyRBTree X)       
{
MyRBTree Y=X->Right;                                //get y
X->Right=Y->Left;                                  //1.link x and y'left by *right
if(Y->Left!=NullNode)       Y->Left->Parent=X;    //2.link y'left and x by *parent

Y->Parent=X->Parent;                              //3.link y and x'parent by *parent
if(X->Parent==NullNode)     Root=Y;               //4.root y is just have left and right
else if(X==X->Parent->Left) X->Parent->Left=Y;    //4.link x'parent and y by *left
else                        X->Parent->Right=Y;   //4.link x'parent and y by *right

Y->Left=X;                                        //5.link y and x by *left
X->Parent=Y;                                      //6.link x and y by *parent //6 steps:because 3 nodes and every nodes include 2 linking ways
}

void RightSingleRotate(MyRBTree X) //a same theory
{
MyRBTree Y=X->Left;
X->Left=Y->Right;
if(Y->Right!=NullNode)       Y->Right->Parent=X; 

Y->Parent=X->Parent;
if(X->Parent==NullNode)      Root=Y;
else if(X==X->Parent->Left)  X->Parent->Left=Y;
else                         X->Parent->Right=Y;

Y->Right=X;
X->Parent=Y;
} 

/*
建议参考《算法导论》中的红黑树，里面考虑的比较全面
这里基本是按照书上的图编程上去的
还有就是自己也要画图 
*/
void FixUpInsert(MyRBTree Z)
{
while(Z->Parent->Color==RED)
{
if(Z->Parent==Z->Parent->Parent->Left)  //case 1.a  just re-color
{
MyRBTree Y=Z->Parent->Parent->Right;    //if Z'parent is at left
if(Z->Color==RED)
{
Z->Parent->Color=BLACK;
Y->Color=BLACK;
Z->Parent->Parent->Color=RED;
Z=Z->Parent->Parent;
}
else 
   {
       if(Z==Z->Parent->Right)     //case 2.a  need rotate and re-color 
       {
       Z=Z->Parent;
       LeftSingleRotate(Z);
   }
   Z->Parent->Color=BLACK;  //case 3.a
   Z->Parent->Parent->Color=RED;
   RightSingleRotate(Z->Parent->Parent);
   }
}
else              
{
MyRBTree Y=Z->Parent->Parent->Left;  //if Z'parent is at right,a same theory such as Z'parent is at left
if(Y->Color==RED)    //case 1.b
{
Z->Parent->Color=BLACK;
Y->Color=BLACK;
Z->Parent->Parent->Color=RED;
Z=Z->Parent->Parent;
}
else
{
if(Z==Z->Parent->Left)  //case 2.b
{
Z=Z->Parent;
RightSingleRotate(Z);
}
Z->Parent->Color=BLACK;  //case 3.b
Z->Parent->Parent->Color=RED;
LeftSingleRotate(Z->Parent->Parent);
}
}
}
Root->Color=BLACK;
}


void Insert(int Data) //insert a element by non-recursive way
{
MyRBTree Z=new TreeNode;
Z->Element=Data;
Z->Color=RED;
Z->Parent=Z->Left=Z->Right=NullNode;
MyRBTree Y=NullNode;
MyRBTree X=Root;
while(X!=NullNode)   //find the position Z should insert
{
Y=X;
if(Z->Element<X->Element)
   X=X->Left;
else 
   X=X->Right;
}
Z->Parent=Y;    
if(Y==NullNode)
   Root=Z;
else if(Z->Element<Y->Element)
       Y->Left=Z;
    else 
       Y->Right=Z;
FixUpInsert(Z);
}


void Transplant(MyRBTree U,MyRBTree V)  //
{
if(U->Parent==NullNode)
   Root=V;
else if(U==U->Parent->Left)
       U->Parent->Left=V;
else if(U==U->Parent->Right)
       U->Parent->Right=V;
V->Parent=U->Parent;
}

void FixUpDelete(MyRBTree X)  
{
while(X!=Root&&X->Color==BLACK)
{
if(X==X->Parent->Left)
{
MyRBTree W=X->Parent->Right;     //x's brother

if(W->Color==RED)   //case 1.a
{
W->Color=BLACK;
X->Parent->Color=RED;
LeftSingleRotate(X->Parent);   //generally use X'p ,not W'p
W=X->Parent->Right;
}
if(W->Left->Color==BLACK&&W->Right->Color==BLACK) //case 2.a
{
W->Color=RED;
X=X->Parent;
}
else     
{
if(W->Left->Color==RED)  //case 3.a
{
W->Color=RED;
W->Left->Color=BLACK;
RightSingleRotate(W);
W=X->Parent->Right;
   }
W->Color=W->Parent->Color;  //case 3.a >> case 4.a
W->Parent->Color=BLACK;
W->Right->Color=BLACK;
LeftSingleRotate(X->Parent);
X=Root;  //case 4.a >>loop end 
}
}
else
{
MyRBTree W=X->Parent->Left;

if(W->Color==RED)  //case 1.b
{
W->Color=BLACK;
X->Parent->Color=RED;
RightSingleRotate(X->Parent);
W=X->Parent->Left;
}
if(W->Left->Color==BLACK&&W->Right->Color==BLACK) //case 2.b
{
W->Color=RED;
X=X->Parent;
}
else
{
if(W->Right->Color==RED)      
{
W->Color=BLACK;        //case 3.b
W->Right->Color=BLACK;
LeftSingleRotate(W);
W=X->Parent->Left;
}
W->Color=W->Parent->Color;  //case 3.b >> case 4.b
W->Parent->Color=BLACK;
W->Left->Color=BLACK;
RightSingleRotate(X->Parent);  //case 4.b >> loop end
X=Root; 
}
}
}
X->Color=BLACK;
}

void Delete(MyRBTree &Z)
{
MyRBTree X=NULL;
MyRBTree Y=Z;
int YColor=Y->Color; //record y original color

if(Z->Left==NullNode)  //if Z just have right
{
X=Z->Right;
Transplant(Z,Z->Right);
}
else if(Z->Right==NullNode) //if Z just have left
{
X=Z->Left;
Transplant(Z,Z->Left);
}
else    //Z have two childnode
{
Y=FindMin(Z->Right);
YColor=Y->Color;
X=Y->Right;
if(Y->Parent==Z)  
   X->Parent=Y;
else    //if y isn't z'childnode
{
Transplant(Y,Y->Right);   //let y's rightnode become y ,and then change z' pointer
Y->Right=Z->Right;
Y->Right->Parent=Y;  //let Y'before is a RBT
}
Transplant(Z,Y);        //let y become z
Y->Left=Z->Left;
Y->Left->Parent=Y;
Y->Color=Z->Color;
}
if(YColor==BLACK)   //not balanced because there is a black node become red
   FixUpDelete(X);
}