#include<iostream>usingnamespacestd;enumColor{RED,BLACK,};template<classK,classV>structRBTreeNode{K_key;V_value;RBTreeNode*_left;RBTreeNode*_right;RBTreeNode*_parent;Color_color;RBTreeNode(constK&key,constV&value):_key(key),_value(value),_left(NULL),_right(NULL),_parent(NULL),_color(RED){}};template<classK,classV>classRBTree{public:typedefRBTreeNode<K,V>Node;RBTree():_root(NULL){}boolInsert(constK&key,constV&value){if(_root==NULL){_root=newNode(key,value);_root->_color=BLACK;returntrue;}Node*cur=_root,*prev=NULL;while(cur){if(cur->_key<key){prev=cur;if(cur->_right){cur=cur->_right;}else{cur->_right=newNode(key,value);cur=cur->_right;cur->_parent=prev;break;}}elseif(cur->_key>key){prev=cur;if(cur->_left){cur=cur->_left;}else{cur->_left=newNode(key,value);cur=cur->_left;cur->_parent=prev;break;}}elsereturnfalse;}Node*gf=prev->_parent;while(gf){if(prev->_color==BLACK)break;Node*uc=NULL;if(prev==gf->_left)uc=gf->_right;elseuc=gf->_left;if(uc==NULL||uc->_color==BLACK){//单旋if(prev==gf->_left&&cur==prev->_left){//右旋RotateR(prev,gf);prev->_color=BLACK;gf->_color=RED;}elseif(prev==gf->_right&&cur==prev->_right){//左旋RotateL(prev,gf);prev->_color=BLACK;gf->_color=RED;}//双旋elseif(prev==gf->_right&&cur==prev->_left)//右左旋{RotateR(cur,prev);RotateL(prev,gf);prev->_color=BLACK;gf->_color=RED;}else//左右旋{RotateL(cur,prev);RotateR(prev,gf);prev->_color=BLACK;gf->_color=RED;}}else{prev->_color=BLACK;uc->_color=BLACK;if(gf==_root)returntrue;gf->_color=RED;cur=gf;prev=cur->_parent;gf=prev->_parent;}}returntrue;}voidRotateR(Node*subL,Node*parent){Node*ppNode=parent->_parent;Node*subLR=subL->_right;subL->_right=parent;parent->_left=subLR;if(subLR)subLR->_parent=parent;if(ppNode){subL->_parent=ppNode;if(ppNode->_left==parent)ppNode->_left=subL;elseppNode->_right=subL;}else_root=subL;}voidRotateL(Node*subR,Node*parent){Node*ppNode=parent->_parent;Node*subRL=subR->_left;subR->_left=parent;parent->_right=subRL;if(subRL)subRL->_parent=parent;if(ppNode){subR->_parent=ppNode;if(ppNode->_left==parent)ppNode->_left=subR;elseppNode->_right=subR;}else_root=subR;}boolRemove(constK&key){}boolIsBalance()//是否平衡{if(_root==NULL)returntrue;intnum=0;Node*tmp=_root;while(tmp){if(tmp->_color==BLACK)num++;tmp=tmp->_left;}return_IsBalance(_root,num);}private:Node*_root;bool_IsBalance(Node*root,intnum){if(root==NULL)returntrue;if(root->_color==BLACK)num--;if(root->_color==RED){if(root->_left&&root->_left->_color==RED||root->_right&&root->_right->_color==RED){cout<<"colornotbalance!key:"<<root->_key<<endl;returnfalse;}}if(root->_left==NULL&&root->_right==NULL){if(num==0)returntrue;else{cout<<"numnotbalance!key:"<<root->_key<<endl;returnfalse;}}return_IsBalance(root->_left,num)&&_IsBalance(root->_right,num);}};