红黑树：
enum nodecolor {red,black};
struct red_black_node
{
int key;
red_black_node *left;
red_black_node *right;
red_black_node *p;
nodecolor color;
red_black_node(int a,nodecolor c=red)
{
key=a;
color=c;
}
};
static red_black_node *NIL=new red_black_node(0,black);
red_black_node* tree_minimum(red_black_node *x)
{
while(x->left!=NIL)
x=x->left;
return x;
}
red_black_node* tree_successor(red_black_node *x)
//寻找后继结点，没有则返回NIL,O(h)
{
if(x->right!=NIL)//如果x的右子树非空，后继即右子树的最左结点
return tree_minimum(x->right);
red_black_node* y=x->p;
//如果x的右子树为空，向上查找，直到遇到某个是其父结点的左儿子的结点为止
while(y!=NIL && x==y->right)
{
x=y;
y=y->p;
}
return y;
}
red_black_node* left_rotate(red_black_node *t,red_black_node *x)
//左旋，根为t，旋转结点为x，y为x的右儿子，返回旋转之后的根，O(1)
{
red_black_node *root=t;
red_black_node *y=x->right;
x->right=y->left;
if(y->left!=NIL)
y->left->p=x;
y->p=x->p;
if(x->p==NIL)//x是根的情况
root=y;
else if(x==x->p->left)
x->p->left=y;
else
x->p->right=y;
y->left=x;
x->p=y;
return root;
}
red_black_node* right_rotate(red_black_node *t,red_black_node *x)
//右旋，根为t，旋转结点为x，y为x的左儿子，返回旋转之后的根，O(1)
{
red_black_node *root=t;
red_black_node *y=x->left;
x->left=y->right;
if(y->right!=NIL)
y->right->p=x;
y->p=x->p;
if(x->p==NIL)//x是根的情况
root=y;
else if(x==x->p->left)
x->p->left=y;
else
x->p->right=y;
y->right=x;
x->p=y;
return root;
}
red_black_node* rb_insert_fixup(red_black_node *x,red_black_node *z)
//在插入z后，调用该函数来保持红黑性质，x为根，z为插入的结点，返回根结点，O(lgn)，最多旋转2次
{
red_black_node *y;
while(z->p->color==red)//z和z的父结点都为红色时才需要调整
{
if(z->p==z->p->p->left)
{
y=z->p->p->right;//y是z的叔叔结点，根据y的颜色分成3种情况
if(y->color==red)//情况1，y为红色
{
z->p->color=black;
y->color=black;//将父结点和叔叔结点都着黑色以解决z和z的父结点都为红色
z->p->p->color=red;//将祖父结点着红色以保持性质5
z=z->p->p;//将z的祖父的父结点可能也是红色，将z置为其祖父再次循环
}
else//情况2和3，y为黑色
{
if(z->p->right==z)//情况2，y黑色且z是右孩子
{
z=z->p;
x=left_rotate(x,z);//对z父亲使用一次左旋使之转变为情况3
}
//情况3，y黑色且z是左孩子
z->p->color=black;
z->p->p->color=red;
right_rotate(x,z->p->p);//此时z的父结点为黑色，无需再执行while循环
}
}
else//下面的跟上面一样，只要左右互换
{
y=z->p->p->left;
if(y->color==red)
{
z->p->color=black;
y->color=black;
z->p->p->color=red;
z=z->p->p;
}
else
{
if(z->p->left==z)
{
z=z->p;
x=right_rotate(x,z);
}
z->p->color=black;
z->p->p->color=red;
left_rotate(x,z->p->p);
}
}
}
x->color=black;//最后记得把根着为黑色
return x;
}
red_black_node* rb_insert(red_black_node *x,red_black_node *z)
//在根为x的红黑树中插入结点z，O(lgn),最多旋转2次
{
red_black_node *y=NIL;
red_black_node *root=x;
while(x!=NIL)
{
y=x;
if(z->key<x->key)
x=x->left;
else
x=x->right;
}
z->p=y;
if(y==NIL)
root=z;
else if(z->key<y->key)
y->left=z;
else
y->right=z;
z->left=NIL;
z->right=NIL;
z->color=red;//要将z的孩子置为NIL并着为红色
x=root;
x=rb_insert_fixup(x,z);//保持红黑性质
return x;
}
red_black_node* rb_delete_fixup(red_black_node *x,red_black_node *q)
//删除黑色结点后恢复红黑性质，x为根，q为删除结点y的唯一孩子或者为NIL，返回根结点，O(lgn)，最多旋转3次
{
red_black_node* w=NIL;
while(q!=x && q->color==black)
//while循环的目标是将额外的黑色沿树上移
{
if(q==q->p->left)
{
w=q->p->right;//w是q的兄弟，q为双重黑色，所以w不可能为NIL
if(w->color==red)//情况1，w是红色
{
w->color=black;
q->p->color=red;//改变w和q->p的颜色
x=left_rotate(x,q->p);//对q->p进行左旋，红黑性质继续保持
w=q->p->right;//w赋值为q的新兄弟，转到情况2，3，4
}
if(w->left->color==black && w->right->color==black)
//情况2，w是黑色且w两个孩子都是黑色
{
w->color=red;
q=q->p;
//通过while循环不断上升，如遇到红色结点跳出循环，在函数最后q被着黑色
//如果是通过情况1进入情况2，则q->p必为红色，直接循环结束
}
else//情况3，4
{
if(w->right->color==black)
//情况3，w是黑色且w的孩子左红右黑
{
w->left->color=black;
w->color=red;
x=right_rotate(x,w);
w=q->p->right;
//交换w和其左孩子颜色并对w右旋，转情况4
}
//情况4,w是黑色且右孩子是红色
w->color=q->p->color;
q->p->color=black;
w->right->color=black;
x=left_rotate(x,q->p);
//去掉q额外的黑色
q=x;//q置为根，循环结束
}
}
else
{
w=q->p->left;
if(w->color==red)
{
w->color=black;
q->p->color=red;
x=right_rotate(x,q->p);
w=q->p->left;
}
if(w->left->color==black && w->right->color==black)
{
w->color=red;
q=q->p;
}
else if(w->left->color==black)
{
w->right->color=black;
w->color=red;
x=left_rotate(x,w);
w=q->p->left;
}
w->color=q->p->color;
q->p->color=black;
w->left->color=black;
x=right_rotate(x,q->p);
q=x;
}
}
q->color=black;
return x;
}
red_black_node* rb_delete(red_black_node *x,red_black_node *z)
//在根为x的红黑树中删除结点z，O(lgn),最多旋转3次
{
red_black_node *y=NIL;
red_black_node *q=NIL;
red_black_node *root=x;
if(z->left==NIL||z->right==NIL)
y=z;
else
y=tree_successor(z);
if (y->left!=NIL)
q=y->left;
else
q=y->right;
q->p=y->p;//无条件赋值
if(y->p==NIL)
root=q;
else if(y==y->p->left)
y->p->left=q;
else
y->p->right=q;
if(y!=z)
z->key=y->key;
x=root;
if(y->color==black)//删除的是黑色结点才调用
x=rb_delete_fixup(x,q);//q是y的唯一孩子或者是哨兵NIL
return x;
}
void inorder_walk(red_black_node *x)
{
if(x!=NIL)
{
inorder_walk(x->left);
if(x->color==red)
cout<<"red";
else
cout<<"black";
cout<<x->key<<" ";
inorder_walk(x->right);
}
}