红黑树为一种二叉查找树，红黑树有五个特点:(1)红黑树节点要么为红，要么为黑；
（2）红黑树的根节点为黑；
（3）红黑树的叶子节点为黑；
（4）红黑树从一个节点为红色，则它的儿子节点们必定为黑的；
（5）红黑树从某一节点起到期子孙叶子节点的黑高度一样；
红黑树进行任何的操作的话都必须要保持以上的五个特点不被改变，下面是为了保持不改变红黑树的特性的一种操作：左旋和右旋；
void rbtree::leftrotate(rbtree* T,node* tn)//左旋,在rbtree中对于某一节点*tn，进行左旋，下面类似
{
node* y=tn->right;
tn->right=y->left;
if(y->left!=NULL)
y->left->p=x;
y->p=tn->p;
if(tn->p==NULL)
T->root=y;
else
if(tn==tn->p->left)
tn->p->left=y;
else
tn->p->right=y;
tn->left=y;
y->p=tn;
}
void rbtree::rightrotate(rbtree* T,node* tn)//右旋，
{
node* x=tn->left;
tn->left=x->right;
if(x->right!=NULL)
x->right->p=tn;
x->p=tn->p;
if(tn->p==NULL)
T->root=x;
else
if(tn==tn->p->left)
tn->p->left=x;
else
tn->p->right=x;
tn->p=x;
x->right=tn;
}
那么对于一个红黑树来进行插入的话必须要保证的就是不改变上面的五个特性，所以插入的节点的颜色必须是红色的，否则必定会对红黑树各个节点黑高度产生影响。那么下面简单的描述下红黑树的插入：
插入第一步就是如二叉查找树一样进行插入，不过插入的节点最终染为红色，这样的话可以保证性质5不会被影响，其次如果插入的一个节点为红颜色会影响到的性质有：性质2和4，如果插入的节点是根节点，那么影响2，如果插入的节点的父亲节点为红色的话，影响4，这里如下的代码是对插入的操作：
#include<iostream>
#include<string>
using namespace std;
enum c {black,red};
class rbtree;
class node* nil;
class node
{
public:
friend class rbtree;
//string color;
c color;
int key;
node* left;
node* right;
node* p;
class node()//default constructor
{
color=black;
key=0;
left=NULL;
right=NULL;
p=NULL;
}
class node(c colour,int k,node* lchild,node* rchild,node* parent):color(colour),key(k),left(lchild),right(rchild),p(parent){}//constructor
};
class rbtree
{
public:
class node* root;
class rbtree(class node* N):root(N){}//constructor
void leftrotate(rbtree* T,node* tn);
void rightrotate(rbtree* T,node* tn);
void rbinsert(rbtree* T,node* tn);
void rbinsertfixup(rbtree* T,node* tn);
//void rbdele(rbtree* T,node* tn);
//void rbdelefixup(rbtree* T,node* tn);
};
void rbtree::leftrotate(rbtree* T,node* tn)
{
node* y=tn->right;
tn->right=y->left;
if(y->left!=nil)
y->left->p=tn;
y->p=tn->p;
if(tn->p==nil)
T->root=y;
else
if(tn==tn->p->left)
tn->p->left=y;
else
tn->p->right=y;
tn->left=y;
y->p=tn;
}
void rbtree::rightrotate(rbtree* T,node* tn)
{
node* x=tn->left;
tn->left=x->right;
if(x->right!=nil)
x->right->p=tn;
x->p=tn->p;
if(tn->p==nil)
T->root=x;
else
if(tn==tn->p->left)
tn->p->left=x;
else
tn->p->right=x;
tn->p=x;
x->right=tn;
}
void rbtree::rbinsertfixup(rbtree* T,node* tn)
{
node* y=new node();//(1)
while(tn->p->color==red)
{
if(tn->p==tn->p->p->left)
node *y=tn->p->p->right;//这里犯了一个错误，因为这里的y是定义在if下面管辖的一句内，而这个if函数只管辖一句，y是定义在栈中，这个语句结束之后，y就消除了，所以如果上面（1）没有在堆中分配空间的话，这里会报错，或者另一种方法就是把if的函数空间扩大。!易犯错！还有一点就是如果输入的时候有输入法的半角和全角的分别，也会有空格的错误。
if(y->color==red)
{
tn->p->color=black;
tn->p->p->color=red;
y->color=black;
tn=tn->p->p;
}
else if(tn==tn->p->right)
//这里是第二种情况y的颜色是黑色的，同时tn需要是右子树。记住如果此时tn->p->color为黑就跳出循环
{
tn=tn->p;//把tn的地位向上移动一个
rbtree::leftrotate(T,tn);
//上面的操作把tn地位下移一个
}
//下面是第三种情况:tn为红，其父为红，其祖父为黑，其叔叔为黑，其祖父为何为黑呢？因为
//这里的循环是其父为红，（不为红就跳出循环，那么就完成插入）那么如果其爷爷为红的话，其父必定为黑
tn->p->color=black;
tn->p->p->color=red;//如果仅仅这样的话会导致叔叔那支黑高度变化，故要如下的操作；
rbtree::rightrotate(T,tn->p->p);//这样的话，叔叔那支的黑高度和自己的黑高度保持不变，而且tn的父为黑。
}
//唯一的担心的就是这样操作的话根节点的颜色变化比如说这样修改的祖父就是根节点呢？那就改变了根节点特性，所以有下面的收尾的工作
//放心的是不会改变黑高度，因为这里的话根节点算起的话等于每一个分支黑高度加而已。
T->root->color=black;
}
void rbtree::rbinsert(rbtree* T,node* tn)
{
node* y=new node(black,0,nil,nil,nil);
node* x=T->root;
while(x!=nil)//这里有问题
{
y=x;
if(tn->key<x->key)
x=x->left;
else
x=x->right;
}
tn->p=y;
if(y==nil)
T->root=tn;
else
if(tn->key<y->key)
y->left=tn;
else
y->right=tn;
tn->color=red;
tn->left=nil;
tn->right=nil;
rbinsertfixup(T,tn);
}
int main()
{
class rbtree rb(new node(black,86,nil,nil,nil));
node* tn1=new node(black,56,nil,nil,nil);
node* tn2=new node(red,122,nil,nil,nil);
node* tn3=new node(red,89,nil,nil,nil);
node* tn4=new node(red,123,nil,nil,nil);
rb.rbinsert(&rb,tn1);
rb.rbinsert(&rb,tn2);
rb.rbinsert(&rb,tn3);
rb.rbinsert(&rb,tn4);
cout<<rb.root->key<<":"<<rb.root->color<<endl;
cout<<rb.root->right->key<<":"<<rb.root->right->color<<endl;
cout<<rb.root->right->right->key<<":"<<rb.root->right->right->color<<endl;
cout<<rb.root->right->right->left->key<<":"<<rb.root->right->right->left->color<<endl;
cout<<rb.root->right->right->right->key<<":"<<rb.root->right->right->right->color<<endl;
return 0;
}
