【数据结构】红黑树

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

红黑树满足下面的性质

1 . ? 每个节点，不是红色就是黑色的
2 . ? 根节点是黑色的
3 . ? 如果一个节点是红色的，则它的两个子节点是黑色的
4 . ? 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目
5 . ? 每个叶子节点都是黑色的（这里的叶子节点是指的NULL 节点（空节点））

红黑树的插入情况分析

cur表示当前节点，P为父节点，g为祖父节点，u为叔叔节点

1、第一种情况

cur 为红，p为红，g为黑，u存在且为红
则将p,u改为黑，g改为红，然后把g当成cur ，继续向上调整。

2、第二种情况

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

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

3 . 第三种情况
cur 为红，p为红，g为黑，u不存在/u为黑
p为g的左孩子，cur 为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur 为p的左孩子，则针对p做右单旋转，则转换成了情况2

另一种

代码

RBtree.h

#include<iostream>
#include<cstdlib>
using namespace std;
enum Colour
{
	RED,BLACK,};
template<class K,class V>
struct RBtreeNode
{
	RBtreeNode<K,V>* _left;
	RBtreeNode<K,V>* _right;
	RBtreeNode<K,V>* _parent;
	K _key;
	V _value;
	Colour _col;
	RBtreeNode(const K& key,const V& value)
		:_left(NULL),_right(NULL),_parent(NULL),_key(key),_value(value),_col(RED)
	{}

};
template<class K,class V>
class RBtree
{
	typedef RBtreeNode<K,V> Node;
public:
	RBtree()
		:_root(NULL)
	{}
	~RBtree()
	{}
	bool Insert(const K& key,const V& vlaue)
	{
		if(_root==NULL)
		{
			_root=new Node(key,vlaue);
			_root->_col=BLACK;
			return true;
		}
		Node* cur=_root;
		Node* parent=NULL;
     while (cur)
     {
		 if(cur->_key>key)
		 {
		  parent=cur;
		  cur=cur->_left;
		 }
		 else if(cur->_key<key)
		 {
		 parent=cur;
		 cur=cur->_right;
		 }
		 else
		 return false;
	 }
		 cur=new Node(key,vlaue);
		 if (parent->_key>key)
		 {
			 parent->_left=cur;
			 cur->_parent=parent;
		 }
		 else
		 {
			 parent->_right=cur;
			 cur->_parent=parent;
		 }
		 while (cur!=_root&&parent->_col==RED)
		 {
			 Node* grandfather=parent->_parent;
			 if(parent==grandfather->_left)//1、父节点为祖父节点的左孩子
			 {
			 Node* uncle=grandfather->_right;
			 if (uncle&&uncle->_col==RED)
			 {
				 //第一种情况，当前节点cur为红，父节点为红，
				 //存在叔叔节点且为红，祖父节点为红
				 parent->_col=uncle->_col=BLACK;
				 grandfather->_col=RED;
				 cur=grandfather;
				 parent=cur->_parent;
			 }

			 //else if(uncle==NULL||uncle->_col==BLACK)
			 else
			 {
				 //第二种情况，叔叔节点不存在
				 //第三种情况，叔叔节点存在且为黑
				 if(cur==parent->_right)
				 {
					 _RotatoL(parent);
					 swap(parent,cur);
				 }

				 _RotatoR(grandfather);
				 parent->_col=BLACK;
				 grandfather->_col=RED;

				 cur=parent;
				 parent=cur->_parent;

			 }
			 }
			 else if (parent==grandfather->_right)//2、父节点为祖父节点的右孩子
			 {
				 Node* uncle=grandfather->_left;
				 if (uncle&&uncle->_col==RED)
				 {
					 //第一种情况，当前节点cur为红，父节点为红，
					 //存在叔叔节点且为红，祖父节点为红
					 parent->_col=uncle->_col=BLACK;
					 grandfather->_col=RED;
					 /*grandfather=cur;
					 cur->_parent=parent;*/
					 cur=grandfather;
					 parent=cur->_parent;
				 }

				 //else if(uncle==NULL||uncle->_col==BLACK)
				 else
				 {
					 //第二种情况，叔叔节点不存在
					 //第三种情况，叔叔节点存在且为黑
					 if(cur==parent->_left)
					 {
						 _RotatoR(parent);
						 swap(cur,parent);
					 }

					 _RotatoL(grandfather);
					 parent->_col=BLACK;
					 grandfather->_col=RED;

					 cur=parent;
					 parent=cur->_parent;

				 }
			 }
		 }
	 _root->_col=BLACK;
	 return true;
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	bool IsBalance()
	{
		if(_root==NULL)
			return true;
		int count=0;//定义一条路上的黑节点树作为黑节点数目判断数
		Node* cur=_root;
		while(cur)
		{
			if(cur->_col==BLACK)
				count++;
			cur=cur->_left;
		}
		int BlackCount=0;
		return _IsBlance(_root,count,BlackCount);//递归判断每一条路径上黑节点数是否正确
	}
protected:
	void _RotatoL(Node* parent)
	{
		Node* subR=parent->_right;
		Node* subRL=subR->_left;
		Node* ppNode=parent->_parent;
        parent->_right=subRL;
		
		if(subRL)
		subRL->_parent=parent;
        subR->_left=parent;
		if(ppNode==NULL)
		{
			_root=subR;
			subR->_parent=NULL;
		}
		else if(ppNode->_left==parent)
		{
			ppNode->_left=subR;
			subR->_parent=ppNode;
		}
		else
		{
			ppNode->_right=subR;
			subR->_parent=ppNode;
		}
	}
	void _RotatoR(Node* parent)
	{
		Node* subL=parent->_left;
		Node* subLR=subL->_right;
		Node* ppNode=parent->_parent;

		parent->_left=subLR;
		
		if(subLR)
		subLR->_parent=parent;
        subL->_right=parent;
		if(ppNode==NULL)
		{
			_root=subL;
			subL->_parent=NULL;
		}
		else if(ppNode->_left==parent)
		{
			ppNode->_left=subL;
			subL->_parent=ppNode;
		}
		else
		{
			ppNode->_right=subL;
			subL->_parent=ppNode;
		}
	}
	void _Inorder(Node* root)
	{
		if(root==NULL)
			return;
		_Inorder(root->_left);
		cout<<root->_key<<" "<<root->_value<<" ";
		if(root->_col==0)
		{
			cout<<"红"<<endl;
		}
		else
			cout<<"黑"<<endl;
		_Inorder(root->_right);
	}
	bool _IsBlance(Node* root,int count,int BlackCount)
		//用左右每一条路径上的黑节点数
		//与判断数进行比较，相同为平衡，不同则为不平衡
	{
		if (root==NULL)
		{
			return count==BlackCount;
		}
		Node* parent=root->_parent;
		if(parent&&(parent->_col==RED&&root->_col==RED))
			return false;
		if(root->_col==BLACK)
			BlackCount++;
		return _IsBlance(root->_left,BlackCount)
		       &&_IsBlance(root->_right,BlackCount);
	}
private: 
	Node* _root;
};
void TestRBtree()
{
	RBtree<int,int> rb;
    rb.Insert(0,1);
	rb.Insert(1,1);
	rb.Insert(2,1);
	rb.Insert(3,1);
	rb.Insert(4,1);
	rb.Insert(5,1);
	rb.Insert(6,1);
	rb.Insert(7,1);
	rb.Insert(8,1);
	rb.Insert(9,1);
	rb.Inorder();
	if (rb.IsBalance())
	{
		cout<<"平衡"<<endl;
	}
	else
	{
		cout<<"不平衡"<<endl;
	}
	
	
}

#include "RBtree.h"
int main()
{
	TestRBtree();
	system("pause");
	return 0;
}