一、红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
可以保证最长路径不超过最短路径的2倍，近似平衡。
二、性质
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点（NIL节点，空节点）是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
三、实现代码：
（1） 插入新的节点：
第一种情况：cur（新）为红，p（父）为红，g（祖）为黑，u（叔）存在且为红；-------->p变为黑，g为红，u为黑
第二种情况：cur（新）为红，p（父）为红，g（祖）为黑，u（叔）不存在或者u为黑；-------->p变为黑，g为红，u为黑
第三种情况：cur（N）为红，p为红，g为黑，u不存在或者u为黑；------>旋转为第二种情况，交换N和P节点。
（2）判断是否平衡
判断是否出现连续红色的情况；
判断各支路是否黑色节点相等；
（3）实现如下：
#pragma once
#include<iostream>
using namespace std;
enum color{BLACK,REB};
template<class K,class V>
struct RBTreeNode
{
RBTreeNode(K key,V value)
:_left(NULL)
,_right(NULL)
,_parent(NULL)
,_key(key)
,_value(value)
,_col(REB)
{}
RBTreeNode<K,V>* _left;
RBTreeNode<K,V>* _right;
RBTreeNode<K,V>* _parent;
K _key;
V _value;
color _col;
};
template<class K,class V>
class RBTree
{
typedef RBTreeNode<K,V> Node;
public:
RBTree()
:_root(NULL)
{}
void Insert(K key,V value)
{
if(_root==NULL)
{
_root=new Node(key,value);
_root->_col=BLACK;
return;
}
Node* cur=_root;
Node* parent=NULL;
while(cur)
{
parent=cur;
if(cur->_key>key)
{
cur=cur->_left;
}
else if(cur->_key<key)
cur=cur->_right;
}
if(parent->_key>key)
{
parent->_left=new Node(key,value);
parent->_left->_parent=parent;
cur=parent->_left;
}
else if(parent->_key<key)
{
parent->_right=new Node(key,value);
parent->_right->_parent=parent;
cur=parent->_right;
}
//_root->_col=BLACK;
//第一种情况:cur为红，p为红，g为黑，u不存在或者为红
while(cur!=_root&&parent->_col==REB)
{
Node* grandfather=parent->_parent;
if(grandfather->_left==parent)
{
Node* uncle=grandfather->_right;
if(uncle&&uncle->_col==REB)
{
parent->_col=uncle->_col=BLACK;
grandfather->_col=REB; //
cur=grandfather;
parent=cur->_parent;
}
else
{
if(cur==parent->_right) //第三种情况：
{
RotateL(parent);//以parent为轴左旋
swap(cur,parent);
}
parent->_col=BLACK; //第二种情况：
grandfather->_col=REB;
RotateR(grandfather); //以grandfather为轴右旋
break;
}
}
else
{
Node* uncle=grandfather->_left;
if(uncle&&uncle->_col==REB)
{
parent->_col=uncle->_col=BLACK;
grandfather->_col=REB;
cur=grandfather;
parent=cur->_parent;
}
else
{
if(parent->_left==cur) //第三种情况
{
RotateR(parent);
swap(parent,cur);
} //第二种情况
parent->_col=BLACK;
grandfather->_col=REB;
RotateL(grandfather);
break;//以grandfather为轴左旋
}
}
}
_root->_col=BLACK;
}
bool IsBalance()
{
int key=0;
Node* cur=_root;
while(cur)
{
if(cur->_col==BLACK)
{
key++;
}
cur=cur->_left;
}
int count=0;
return _IsBalance(_root,key,count);
}
void InOrder()
{
_InOrder(_root);
}
private:
void RotateL(Node* parent)
{
Node* subR=parent->_right;
Node* subRL=subR->_left;
Node* ppNode=parent->_parent;
subR->_left=parent;
parent->_parent=subR;
if(subRL)
{
parent->_right=subRL;
subRL->_parent=parent;
}
else
parent->_right=NULL;
if(ppNode&&ppNode->_left==parent)
{
ppNode->_left=subR;
subR->_parent=ppNode;
}
else if(ppNode&&ppNode->_right==parent)
{
ppNode->_right=subR;
subR->_parent=ppNode;
}
else if(ppNode==NULL)
{
_root=subR;
subR->_parent=NULL;
}
}
void RotateR(Node* parent)
{
Node* subL=parent->_left;
Node* subLR=subL->_right;
Node* ppNode=parent->_parent;
subL->_right=parent;
parent->_parent=subL;
if(subLR)
{
subLR->_parent=parent;
parent->_left=subLR;
}
else
parent->_left=NULL;
if(ppNode&&ppNode->_left==parent)
{
ppNode->_left=subL;
subL->_parent=ppNode;
}
else if(ppNode&&ppNode->_right==parent)
{
ppNode->_right=subL;
subL->_parent=ppNode;
}
else if(ppNode==NULL)
{
_root=subL;
subL->_parent=NULL;
}
}
void _InOrder(Node* root)
{
if(root==NULL)
{
return;
}
_InOrder(root->_left);
cout<<root->_key<<"->";
_InOrder(root->_right);
}
bool _IsBalance(Node* root,int key,int count)
{
if(root==NULL)
{
return true;
}
if(root->_col==REB&&root->_parent->_col==REB)
{
cout<<"连续红色"<<endl;
return false;
}
if(root->_col==BLACK)
{
count++;
}
if(root->_left==NULL&&root->_right==NULL&&key!=count)
{
cout<<"黑色不等"<<endl;
return false;
}
return _IsBalance(root->_left,key,count)&&_IsBalance(root->_right,key,count);
}
private:
Node* _root;
};
#include"RBTree.h"
int main()
{
RBTree<int,int> t1;
int a[]={1,2,3,4,5,6,7,8,9};
for(int i=0;i<(sizeof(a)/sizeof(a[0]));i++)
{
//cout<<a[i]<<t1.IsBalance()<<endl;
t1.Insert(a[i],i);
cout<<a[i]<<t1.IsBalance()<<endl;
//cout<<a[i]<<endl;
}
t1.InOrder();
cout<<t1.IsBalance()<<endl;
system("pause");
return 0;
}
4、结果：
