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

红黑树满足的性质：

根节点是黑色的

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

每条路径的黑色节点的数量相等

红黑树保证最长路径不超过最短路径的两倍，如下图所示

插入节点时的三种情况

cur为红，p为红，g为黑，u存在且为红

cur为红，p为红，g为黑，u不存在/u为黑，p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红

cur为红，p为红，g为黑，u不存在/u为黑，p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

#pragmaonce#include<iostream>usingnamespacestd;enumColor{RED,BALCK};template<classK,classV>structRBTreeNode{RBTreeNode<K,V>*_left;RBTreeNode<K,V>*_right;RBTreeNode<K,V>*_parent;K_key;V_value;Color_col;RBTreeNode(constK&key,constV&value):_left(NULL),_right(NULL),_parent(NULL),_key(key),_value(value),_col(RED){}};template<classK,classV>classRBTree{typedefRBTreeNode<K,V>Node;public:RBTree():_root(NULL){}Node*Find(constK&key){if(_root==NULL)returnNULL;Node*cur=_root;while(cur){if(cur->_key==key)returncur;elseif(cur->_key<key)cur=cur->_right;elsecur=cur->_left;}returnNULL;}boolInsert(constK&key,constV&value){if(_root==NULL){_root=newNode(key,value);_root->_col=BALCK;returntrue;}Node*cur=_root;Node*parent=NULL;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{cout<<"该节点已存在"<<endl;returnfalse;}}cur=newNode(key,value);if(parent->_key>key){parent->_left=cur;}else{parent->_right=cur;}cur->_parent=parent;//调整节点颜色while(cur!=_root&&parent->_col==RED){//规定根节点必须为黑色，若parent的颜色为红色，则它一定不为根节点，它的父节点也一定存在Node*ppNode=parent->_parent;//不用判空Node*uncle=NULL;if(parent==ppNode->_left){//parent为它的父节点的左孩子，则叔节点若存在，肯定在右边uncle=ppNode->_right;if(uncle&&uncle->_col==RED){//1.cur为红，parent为红，ppNode为黑，u存在且为红parent->_col=uncle->_col=BALCK;ppNode->_col=RED;cur=ppNode;ppNode=cur->_parent;}else{//2.cur为红，parent为红，uncle不存在或者为黑if(cur==parent->_right){RotateL(parent);swap(cur,parent);}parent->_col=BALCK;ppNode->_col=RED;RotateR(ppNode);}}else{//另一边uncle=ppNode->_left;if(uncle&&uncle->_col==RED){//1.cur为红，parent为红，ppNode为黑，u存在且为红parent->_col=uncle->_col=BALCK;ppNode->_col=RED;cur=ppNode;ppNode=cur->_parent;}else{if(cur==parent->_left){RotateR(parent);swap(cur,parent);}parent->_col=BALCK;ppNode->_col=RED;RotateL(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;if(parent==_root||ppNode==NULL)//若要调整的节点为根节点{_root=subL;subL->_parent=NULL;}else{if(parent==ppNode->_left){ppNode->_left=subL;}else{ppNode->_right=subL;}subL->_parent=ppNode;}}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;if(parent==_root||ppNode==NULL)//若要调整的节点为根节点{_root=subR;subR->_parent=NULL;}else{if(parent==ppNode->_left){ppNode->_left=subR;}else{ppNode->_right=subR;}subR->_parent=ppNode;}}boolIsBalance(){intBlackNodeCount=0;Node*cur=_root;while(cur){if(cur->_col==BALCK){BlackNodeCount++;}cur=cur->_left;}intcount=0;return_IsBalance(_root,BlackNodeCount,count);}voidInOrder(){_InOrder(_root);cout<<endl;}~RBTree(){}protected:bool_IsBalance(Node*root,constintBlackNodeCount,intcount){if(root==NULL)returnfalse;if(root->_parent){if(root->_col==RED&&root->_parent->_col==RED){cout<<"不能有两个连续的红节点"<<endl;returnfalse;}}if(root->_col==BALCK)++count;if(root->_left==NULL&&root->_right==NULL&&count!=BlackNodeCount){cout<<"该条路径上黑色节点数目与其它不相等"<<endl;returnfalse;}return_IsBalance(root->_left,BlackNodeCount,count)&&_IsBalance(root->_right,BlackNodeCount,count);}void_InOrder(Node*root){if(root==NULL)return;_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}protected:Node*_root;};voidTest(){RBTree<int,int>bt;intarr[]={4,2,6,1,3,5,15,7,16,14};for(inti=0;i<sizeof(arr)/sizeof(arr[0]);++i){bt.Insert(arr[i],i);}bt.IsBalance();bt.InOrder();cout<<bt.Find(6)<<endl;;cout<<bt.Find(9)<<endl;}

红黑树与AVL树的异同：

红黑树和AVL树都是高效的平衡二叉树，增删查改的时间复杂度都是O(lg(N))

红黑树的不追求完全平衡，保证最长路径不超过最短路径的2倍，相对而言，降低了旋转的要求，所以性能跟AVL树差不多，但是红黑树实现更简单，所以实际运用中红黑树更多。

红黑树的应用：

STL库中的map、set

多路复用epoll模式在linux内核的实现

JAVA的TreeMap实现