红黑树：
有错误请及时提出！！！
顾名思义，是由红色与黑色结点组成的树了。
这里为了方便复习，做了一次整理；
它有以下几种性质：
1、每个结点或是红色的，或是黑色的；
2、根结点是黑色的；
3、每个叶结点（这里的叶结点是由并不存在作用的NIL结点）都是黑色的；
4、如果一个结点是红色的，那么它的两个子结点都是黑色的；
5、对于每个结点，从该结点到其所有后代的叶结点的简单路径上，均包含相同数目的黑色结点。
2、4、5这三个性质是需要重点考虑的，也是在整个红黑树中最复杂的部分。
定义链表
先用结构体：
Struct point{
Int key;
Struct point *right,*left,*p;
};
下面将围绕这些方面进行操作。
1.旋转变化；
LEFT-ROTATE(T,x)
{//需要处理子结点，父结点的问题；
y=x.right;
X.right=y.left;
If (y.left!=T.nil)y.left.p=x;
Y.p=x.p;
Y.left=x;
If (x.p.left==x) x.p.left=y;
Else x.p.right=y;
X.p=y;
}
RIGHT=ROTATE(T,X)//右旋同左；对称；
{
y=x.left;
X.left=y.right;
If (y.right!=T.nil)y.right.p=x;
Y.right=x;
Y.p=x.p;
If (x.p.right==x)x.p.right=y;
Else x.p.left=y;
X.p=y;
}
2.插入操作：
RB-INSERT(T,z)
{
Y=T.nil;
X=T.root;
While(x!=y){//寻找适当的位置；
Y=x;//方便后面记录父结点；
If (z.key<x.key) x=x.left;
Else x=x.right;
}
Z.p=y;
If (y==T.nil) T.root=z;
Else if(z.left<y.key) y.left=z;
Else y.right=z;
Z.left=z.right=T.nil;
Z.color=red;
RB-INSERT-FIXUP(T,z);
}
RB-INSERT-FIXUP(T,z)//隐含条件z.color=red；注意他是怎样保持性质的；在这里性质2，4，5可能会被改变；
{
While(z.p.color==red)//这是调整的前提；违反了性质4；
{
@If (z.p==z.p.p.left){//左；
//为什么它的旋转一定要分为两步骤？
//因为当z父结点的兄弟结点是红色时，若发生旋转就会导致黑高（性质5）破坏，所以需要进行一些操作；
Y=z.p.p.right;
If (y.color==red){
Y.color=z.p.color=black;
Z.p.p.color=red;
Z=z.p.p;
}
@Else if (z==z.p.right){//将红结点左转，方便接下来右转时避免冲突；
Z=z.p;LEFT-ROTATE(T,z);
}
Z.p.p=red;z.p=black;
RIGHT-ROTATE(T,z.p.p);
}else if (z.p==z.p.p.right){//右；对称
Y=z.p.p.left;
If (y.color==red){
Y.color=z.p.color=black;
Z.p.p=red;Z=z.p.p;
}else if (z==z.p.left){
Z=z.p;RIGHT-ROTATE(T,z);
}
Z.p.color=black;Z.p.p=red;
LEFT-TOTATE(T,z.p.p);
}
}
T.root=black;
}
3.删除操作；
RB-TANSPLANT(T,u,v)//在变换时处理父结点的步骤；方便下面的操作；
{
If (u.p==T.nil){
T.root=v;
}
If (u.p.right==u) u.p.right=v;
Else u.p.left=v;
v.p=u.p;
}
//这里省略了搜索过程；
补：
X=T.root;
While(z.key!=x.key){
If (z.key>x.key)x=x.right;
Else x=x.left;
}
//
INT RB-MINMUM(x)
{
While (x.left!=T.nil) x=x.left;
Return x;
}
Delete过程；
RB-DELETE(T,z)
{
y=z;
Y-original-color=y.color;//y-original-color用于存放原先的（改变前的）颜色；
If (z.left=T.nil){//只有右子树；
X=z.right;
RB-TANSPLANT(T,z,z.right);
} else if(z.right==T.nil){//只有左子树；
X=z.left;
RB-TANSPLANT(T,z,z.left);
}else{
Y=RB-MINMUN(z.right);//上有补;
Y-original-color=y.color;x=y.right;
If (y.p==z)x.p=y;
Else {
RB-TANSPLANT(T.y,y.right);
Y.right=z.right;
Z.right.p=y;
}
RB-TANSPLANT(T,z,y);
Y.left=z.left;y.left.p=y;
Y.color=z.color;
//delete(z);删除结点；
}
If (y-original-color==black) RB-DELETE-FIXUP(T,x);
}
RB-DELETE-FIXUP(T,x)
{
While (x!=T.root&&x.color=black){
If (x==x.p.left){
W=x.p.right;
If (w.color==red){//保持w的值为black;
X.p.color=red;
w.color=blake;
LEFT-ROTATE(T,x,p);
}(此为情况1)这里是关键结点，其他结点省略；
If (w.right.color==w.left=color==black){
w.color=red;x=x.p;
}(此为情况2）这里是关键结点，其他结点省略；
else{
if (w.right.color==black){
W.left.color=black;w.color=red;
RIGHT-ROTATE(T,w);
W=x.p.right;
}（此为情况3）这里是关键结点，其他结点省略；
w.color=x.p.color;
X.p.color=black;w.right.color=black;
LEFT-ROTATE(T,x,p);
X=T.root;
}{此为情况四，与情况三在一起的}
}else {//x==x.p.right,对称；
W=x.p.left;
If (w.color==red){
W.color=black;
X.p.color=red;
RIGHT-ROTATE(T,x.p);
W=x.p.left;
}
If (w.left.color==w.right.color==black){
W.color=red;x=x.p;
}else {
If (w.left.color==black){
W.right.color==black;
w.color=red;
LEFT-ROTATE(T,w);
W=x.p.left;
}
W.left.color=black;
W.color=x.p.color;
X.p.color=black;
RIGHT-ROTATE(T,x.p);
X=T.root;
}
}
}
X.color=black;
}
这样，整个过程基本结束了。