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

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

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个子节点是黑色的

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

#pragmaonceenumColor{RED,BLACK};template<classK,classV>structRBtreeNode{RBtreeNode(constK&key,constV&v,Colorcol=RED):_left(NULL),_right(NULL),_parent(NULL),_key(key),_vlaue(v),_col(col){}RBtreeNode<K,V>*_left;RBtreeNode<K,V>*_right;RBtreeNode<K,V>*_parent;K_key;V_vlaue;Color_col;};template<classK,classV>classRBtree{typedefRBtreeNode<K,V>Node;public:RBtree():_root(NULL){}boolInsert(constK&key,constV&v){if(_root==NULL){_root=newNode(key,v,BLACK);returntrue;}Node*parent=NULL;Node*cur=_root;while(cur){if(key<cur->_key){parent=cur;cur=cur->_left;}elseif(key>cur->_key){parent=cur;cur=cur->_right;}else{returnfalse;}}cur=newNode(key,v,RED);if(key<parent->_key){parent->_left=cur;cur->_parent=parent;}else{parent->_right=cur;cur->_parent=parent;}//调色while(cur!=_root&&parent->_col==RED){Node*GrandParent=parent->_parent;if(parent==GrandParent->_left)//往左子树插{Node*uncle=GrandParent->_right;if(uncle&&uncle->_col==RED){uncle->_col=parent->_col=BLACK;GrandParent->_col=RED;cur=GrandParent;parent=cur->_parent;}else{if(cur==parent->_right){_RotateL(parent);swap(cur,parent);}_RotateR(GrandParent);parent->_col=BLACK;GrandParent->_col=RED;}}else//往右子树插{Node*uncle=GrandParent->_left;if(uncle&&uncle->_col==RED){uncle->_col=parent->_col=BLACK;GrandParent->_col=RED;cur=GrandParent;parent=cur->_parent;}else{if(cur==parent->_left){_RotateR(parent);swap(cur,parent);}_RotateL(GrandParent);parent->_col=BLACK;GrandParent->_col=RED;}}}_root->_col=BLACK;returntrue;}boolIsBalanceTree(){return_IsBalance(_root);}voidInOrder(){_InOrder(_root);cout<<endl;}protected:int_Height(Node*root){if(root==NULL){return0;}intleft=_Height(root->_left)+1;intright=_Height(root->_right)+1;return(left>right)?left:right;}bool_IsBalance(Node*root){if(root==NULL){returntrue;}intleft=_Height(root->_left);intright=_Height(root->_right);intbf=abs(left-right);if(bf>1){returnfalse;}return_IsBalance(root->_left)&&_IsBalance(root->_right);}void_RotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL){subRL->_parent=parent;}subR->_left=parent;subR->_parent=parent->_parent;parent->_parent=subR;parent=subR;//连爸爸:)if(parent->_parent==NULL){_root=parent;}else{if(parent->_parent->_key<parent->_key){parent->_parent->_right=parent;}else{parent->_parent->_left=parent;}}}void_RotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR!=NULL){subLR->_parent=parent;}subL->_right=parent;subL->_parent=parent->_parent;parent->_parent=subL;parent=subL;if(parent->_parent==NULL){_root=parent;}else{if(parent->_parent->_key<parent->_key){parent->_parent->_right=parent;}else{parent->_parent->_left=parent;}}}void_InOrder(Node*&root){if(root==NULL){return;}_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}protected:Node*_root;};voidTestRBTree1(){RBtree<int,int>t1;inta[10]={5,2,9,6,7,3,4,0,1,8};for(size_ti=0;i<sizeof(a)/sizeof(int);++i){t1.Insert(a[i],i);t1.InOrder();}cout<<"IsBalanceTree?"<<t1.IsBalanceTree()<<endl;}