红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是red或black。通过对任何一条从根到叶子简单路径上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似于平衡。

红黑树是满足下面红黑性质的二叉搜索树：

每个节点，不是红色就是黑色的

根节点是黑色的

如果一个节点是红色的，则它的两个子节点是黑色的(没有连续的红节点)

对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。（每条路径的黑色节点的数量相等）

这里分析一下为什么红黑树能保证最长路径不超过最短路径的两倍：首先因为第4条约束条件假设一棵树如下所示：

B

B B

B B B表示为黑色结点，那么要在其中插入任何一个黑色结点就需要保证第4条约定，而如果要插入红色结点，则第3条约束又使得红色结点只能插在黑色结点之间，因此一条路径最多变成：

B

B R

B B

R

B 因此，最长路径不超过最短路径的两倍，也就保证了搜索的效率；

下面是实现红黑树的插入过程：

#pragmaonce#include<iostream>usingnamespacestd;//结点的颜色红or黑enumColor{RED,BLACK};//结点结构体template<classK,classV>structRBTreeNode{K_key;V_val;RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;Color_col;RBTreeNode(constK&key,constV&val):_key(key),_val(val),_left(NULL),_right(NULL),_parent(NULL),_col(RED){}};//红黑树类template<classK,classV>classRBTree{typedefRBTreeNode<K,V>Node;public:RBTree():_root(NULL){}~RBTree(){_Clear(_root);}//插入结点boolInsert(constK&key,constV&val){if(_root==NULL)//如果根结点为NULL，创建新的结点为根结点返回true{_root=newNode(key,val);_root->_col=BLACK;returntrue;}//如果根结点不为NULL，则遍历树直到找到合适的插入位置Node*cur=_root;Node*prev=cur;while(cur!=NULL){if(cur->_key==key)//如果树中已经有该结点，则返回falsereturnfalse;elseif(cur->_key>key)//如果关键值小于结点的关键值，则去左子树找{prev=cur;cur=cur->_left;}else//否则关键值大于结点的关键值，去右子树找{prev=cur;cur=cur->_right;}}//循环结束，找到了合适的插入位置，判断应该插入到结点的左边还是右边Node*tmp=newNode(key,val);if(prev->_key>key)prev->_left=tmp;elseprev->_right=tmp;tmp->_parent=prev;//插入结点之后，就要开始判断目前的树是否符合红黑树的性质while((tmp!=_root)&&(prev->_col==RED)){Node*grandfather=prev->_parent;//提取出tmp的祖父结点if(grandfather->_left==prev)//如果prev是grandfather的左结点{//第一种情况//tmp为红，prev为红，grandfather为黑，uncle存在且为红//则将prev,uncle改为黑，grandfather改为红，然后把grandfather当成tmp，继续向上调整。Node*uncle=grandfather->_right;if(uncle!=NULL&&uncle->_col==RED){prev->_col=BLACK;uncle->_col=BLACK;grandfather->_col=RED;tmp=grandfather;prev=tmp->_parent;}else//第二种情况:tmp为红，prev为红，grandfather为黑，uncle不存在/uncle为黑//prev为grandfather的左孩子，tmp为prev的左孩子，则进行右单旋转；//prev、grandfather变色--prev变黑，grandfather变红{//第三种情况//tmp为红，prev为红，grandfather为黑，uncle不存在/uncle为黑//prev为grandfather的左孩子，tmp为prev的右孩子，则针对prev做左单旋转；//则转换成了情况二if(prev->_right==tmp){_RotateL(prev);swap(tmp,prev);}_RotateR(grandfather);//进行右单旋prev->_col=BLACK;grandfather->_col=RED;break;}}else//当perv是grandfather的右结点的时候，和上面的情况相反{//第一种情况//tmp为红，prev为红，grandfather为黑，uncle存在且为红//则将prev,uncle改为黑，grandfather改为红，然后把grandfather当成tmp，继续向上调整。Node*uncle=grandfather->_left;if(uncle!=NULL&&uncle->_col==RED){prev->_col=BLACK;uncle->_col=BLACK;grandfather->_col=RED;tmp=grandfather;prev=tmp->_parent;}else//第二种情况:tmp为红，prev为红，grandfather为黑，uncle不存在/uncle为黑//prev为grandfather的右孩子，tmp为prev的右孩子，则进行左单旋转//prev、grandfather变色--prev变黑，grandfather变红{//第三种情况//tmp为红，prev为红，grandfather为黑，uncle不存在/uncle为黑//prev为grandfather的右孩子，tmp为prev的左孩子，则针对prev做右单旋转//则转换成了情况二if(prev->_left==tmp){_RotateR(prev);swap(tmp,prev);}_RotateL(grandfather);//进行右单旋prev->_col=BLACK;grandfather->_col=RED;break;}}}//如果根结点被调整成了红色，将其改为黑色，并会不影响左右黑结点的个数if(_root->_col==RED)_root->_col=BLACK;returntrue;}voidInOrder(){_InOrder(_root);cout<<endl;}/*boolFind(constK&key){}*/private:void_Clear(Node*root){if(root==NULL)return;_Clear(root->_left);_Clear(root->_right);deleteroot;root=NULL;}void_RotateL(Node*parent)//左单旋{Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL!=NULL)subRL->_parent=parent;Node*ppNode=parent->_parent;subR->_left=parent;parent->_parent=subR;if(ppNode==NULL)_root=subR;else{if(ppNode->_left==parent)ppNode->_left=subR;elseppNode->_right=subR;}subR->_parent=ppNode;}void_RotateR(Node*parent)//右单旋{Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR!=NULL)subLR->_parent=parent;Node*ppNode=parent->_parent;subL->_right=parent;parent->_parent=subL;if(ppNode==NULL)_root=subL;else{if(ppNode->_left==parent)ppNode->_left=subL;elseppNode->_right=subL;}subL->_parent=ppNode;}void_InOrder(Node*root){if(root!=NULL){_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}}private:Node*_root;};voidTest(){intarr[]={3,4,6,1,7,2,8};RBTree<int,int>t;for(inti=0;i<sizeof(arr)/sizeof(arr[0]);++i)t.Insert(arr[i],i);t.InOrder();}

运行程序：

《完》