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

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

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

根节点是黑色的

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

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

每个叶子节点都是黑色的（这里的叶子节点是指的NIL节点（空节点））

#include<iostream>usingnamespacestd;enumCOL{RED,BLACK};template<classK,classV>structRBTreeNode{K_key;V_val;RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;COL_col;RBTreeNode(K&key,V&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){}boolInsert(K&key,V&val){if(_root==NULL){_root=newNode(key,val);}else{Node*parent=NULL;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(key,val);if(parent->_key<key)parent->_right=cur;elseparent->_left=cur;cur->_parent=parent;//符合红黑树规范while(cur!=_root&&parent->_col==RED){Node*grandfather=parent->_parent;if(grandfather->_left==parent){Node*uncle=grandfather->_right;if(uncle&&uncle->_col==RED)//1.{parent->_col=uncle->_col=BLACK;grandfather->_col=RED;//继续往上调cur=grandfather;parent=cur->_parent;}else{if(cur==parent->_right){RotateL(parent);swap(parent,cur);//*左旋后，指针位置yibian}parent->_col=BLACK;grandfather->_col=RED;RotateR(grandfather);break;}}else//反的情况{Node*uncle=grandfather->_left;if(uncle&&uncle->_col==RED){parent->_col=uncle->_col=BLACK;grandfather->_col=RED;//继续往上调cur=grandfather;parent=cur->_parent;}else{if(cur==parent->_left){RotateR(parent);swap(cur,parent);}parent->_col=BLACK;grandfather->_col=RED;RotateL(grandfather);break;}}}}_root->_col=BLACK;returntrue;}Node*Find(constK&key){Node*cur=_root;while(cur){if(cur->_key<key)cur=cur->_right;elseif(cur->_key>key)cur=cur->_left;elsereturncur;}returnNULL;}boolRemove(constK&key){}boolisBalance(){if(_root==NULL)returntrue;if(_root->_col==RED)returnfalse;intk=0;Node*cur=_root;while(cur){if(cur->_col==BLACK)++k;cur=cur->_left;}intcount=0;return_IsBalance(_root,k,count);}voidInOrder(){_InOrder(_root);}protected:void_InOrder(Node*root){if(root==NULL)return;_InOrder(root->_left);cout<<root->_key<<"";//cout<<root->_key<<"color"<<root->_col<<"";_InOrder(root->_right);}bool_IsBalance(Node*root,constintk,intcount){if(root==NULL)returntrue;if(root->_col==RED){if(root->_parent->_col==RED){cout<<"颜色不正确"<<root->_key<<endl;returnfalse;}}else++count;if(root->_left==NULL&&root->_right==NULL){if(count==k)returntrue;else{cout<<"黑色节点个数不对"<<root->_key<<endl;returnfalse;}}return_IsBalance(root->_left,k,count)&&_IsBalance(root->_right,k,count);}voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*ppNode=parent->_parent;subR->_left=parent;parent->_parent=subR;if(ppNode==NULL){subR->_parent=NULL;_root=subR;}else{if(ppNode->_left==parent){ppNode->_left=subR;}else{ppNode->_right=subR;}subR->_parent=ppNode;}}voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR)subLR->_parent=parent;Node*ppNode=parent->_parent;subL->_right=parent;parent->_parent=subL;if(ppNode==NULL){subL->_parent=NULL;_root=subL;}else{if(ppNode->_left==parent){ppNode->_left=subL;}else{ppNode->_right=subL;}subL->_parent=ppNode;}}private:Node*_root;};voidTest1(){RBTree<int,int>t;inta[]={4,2,6,1,3,5,15,7,16,14};for(inti=0;i<sizeof(a)/sizeof(a[0]);++i){t.Insert(a[i],i);}t.InOrder();t.isBalance();}#include"RBtree.h"intmain(){Test1();system("pause");return0;}