【数据结构】红黑树

一. 红黑树的概念

红黑树是一颗二叉搜索树，它的每个结点增加一个存储单位来表示结点的颜色，这个颜色是red或者black，通过对任何一条从根结点到叶子结点上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似平衡。

二. 红黑树的性质

1.每个结点不是黑色就是红色；

2.根结点的颜色是黑色；

3.没有两个连续的红色结点；

4.每条路径上黑色结点的数量是相等的。

例如图中的树：

三. 红黑树插入结点的实现

同AVL树类似，首先确定插入结点的位置，然后插入结点，最后调节结点，使树上结点的颜色满足以上的性质。

我们做如下假定：

1. 每个结点的颜色默认为红色，这样方便调节，
2. 新增的结点标记为cur，p为父结点，g为祖父结点，u为叔叔结点。

由此可以将其分为五种情况：

情况一：树为空，直接插入结点，并将新增的结点改为黑色；

情况二：插入结点的父结点为黑色，直接插入，不违反任何性质；

对于后面三种情况，我只画了p为g左子树的情况，对于当p为g右子树的情况与上面的类似，只是方向略有不同，因此不在赘述。

具体实现代码如下：

#pragma once
#include <iostream>
using namespace std;
enum COLOR { RED,BLACK };
template <class K,class V>
struct RBNode
{
	RBNode(const K& key,const V& value,const cOLOR color = RED)
	: _pLeft(NULL),_pRight(NULL),_pParent(NULL),_key(key),_value(value),_color(color)
	{}
	RBNode<K,V>* _pLeft;
	RBNode<K,V>* _pRight;
	RBNode<K,V>* _pParent;
	K _key;
	V _value;
	COLOR _color;
};

template < class K,class V>
class RBTree
{
	typedef RBNode<K,V> Node;
	typedef Node* pNode;
public:
	RBTree()
		: _pRoot(NULL)
	{}

	bool Insert(const K& key,const V& value)
	{
		if (NULL == _pRoot)//空树：直接插入
		{
			_pRoot = new Node(key,value,BLACK);
			return true;
		}

		pNode pCur = _pRoot;//非空树：(1)查找待插入的结点的位置
		pNode pParent = NULL;
		while (pCur)
		{
			if (key < pCur->_key)
			{
				pParent = pCur;
				pCur = pCur->_pLeft;
			}
			else
			{
				pParent = pCur;
				pCur = pCur->_pRight;
			}
		}
		pCur = new Node(key,value);//(2)插入结点
		if (key < pParent->_key)
			pParent->_pLeft = pCur;
		else if (key > pParent->_key)
			pParent->_pRight = pCur;
		else
			return false;
		pCur->_pParent = pParent;

		while (_pRoot != pCur && pParent->_color == RED)//(3)调节
		{
			pNode grandFather = pParent->_pParent;
			if (pParent == grandFather->_pLeft)
			{
				pNode uncle = grandFather->_pRight;

				if (uncle && uncle->_color == RED)//情况三
				{
					pParent->_color = BLACK;
					uncle->_color = BLACK;
					grandFather->_color = RED;
					pCur = grandFather;
					pParent = pCur->_pParent;
				}
				else
				{
					if (pCur == pParent->_pRight)//情况五可以合并到情况四
					{
						RotateL(pParent);
						swap(pCur,pParent);
					}
					pParent->_color = BLACK;//情况四
					grandFather->_color = RED;
					RotateR(grandFather);
				}
			}
			else
			{
				pNode uncle = grandFather->_pLeft;

				if (uncle && uncle->_color == RED)//情况三
				{
					pParent->_color = BLACK;
					uncle->_color = BLACK;
					grandFather->_color = RED;
					pCur = grandFather;
					grandFather = pCur->_pParent;
				}
				else
				{
					if (pCur == pParent->_pLeft)
					{
						RotateR(pParent);
						swap(pCur,pParent);
					}
					pParent->_color = BLACK;
					grandFather->_color = RED;
					RotateL(grandFather);
				}
			}
		}
		_pRoot->_color = BLACK;
		return true;
	}

	void InOrder()
	{
		return _InOrder(_pRoot);
	}

	bool Ischeck()//对于红黑树的检验，我们可以通过四条性质中的后三条进行检验
	{
		if (NULL == _pRoot)
			return true;

		if (_pRoot->_color == RED)//检验性质2
		{
			cout << "根结点颜色不是黑色" << endl;
			return false;
		}

		pNode pCur = _pRoot;
		int blackCount = 0;//记录最左边的一条路径黑色结点的个数
		int k = 0;
		while (pCur)
		{
			if (pCur->_color == BLACK)
				blackCount++;
			pCur = pCur->_pLeft;
		}
		return _Ischeck(_pRoot,k,blackCount);
	}

private:
	void RotateL(pNode pParent)//左单旋
	{
		pNode pSubR = pParent->_pRight;
		pNode pSubRL = pSubR->_pLeft;

		pParent->_pRight = pSubRL;
		if (pSubRL)
			pSubRL->_pParent = pParent;
		pNode pPParent = pParent->_pParent;
		pSubR->_pLeft = pParent;
		pParent->_pParent = pSubR;
		pSubR->_pParent = pPParent;
		if (pParent == _pRoot)
			_pRoot = pSubR;
		else
		{
			if (pParent == pPParent->_pLeft)
				pPParent->_pLeft = pSubR;
			else
				pPParent->_pRight = pSubR;
		}
	}

	void RotateR(pNode pParent)//右单旋
	{
		pNode pSubL = pParent->_pLeft;
		pNode pSubLR = pSubL->_pRight;

		pParent->_pLeft = pSubLR;
		if (pSubLR)
			pSubLR->_pParent = pParent;
		pNode pPParent = pParent->_pParent;
		pSubL->_pRight = pParent;
		pParent->_pParent = pSubL;
		pSubL->_pParent = pPParent;
		if (pParent == _pRoot)
			_pRoot = pSubL;
		else
		{
			if (pParent == pPParent->_pLeft)
				pPParent->_pLeft = pSubL;
			else
				pPParent->_pRight = pSubL;
		}
	}

	void _InOrder(pNode pRoot)
	{
		if (pRoot)
		{
			_InOrder(pRoot->_pLeft);
			cout << "<" << pRoot->_key << "," << pRoot->_value << ">" << endl;
			_InOrder(pRoot->_pRight);
		}
	}

	bool _Ischeck(pNode pRoot,int k,int blackCount)
	{
		if (pRoot == NULL)
			return true;
		if (pRoot->_color == BLACK)
		{
			pNode pParent = pRoot->_pParent;
			if (pParent && pParent->_color == RED && pRoot->_color == RED)//检验性质4
			{
				cout << "连在一起的红色结点" << endl;
				return false;
			}
		}
		if (pRoot->_color == BLACK)
			k++;
		if (pRoot->_pLeft == NULL && pRoot->_pRight == NULL)
		{
			if (k != blackCount)//检验性质3
			{
				cout << "每条路径上黑色结点的个数不相等" << endl;
				return false;
			}
		}
		return _Ischeck(pRoot->_pLeft,blackCount) &&
			_Ischeck(pRoot->_pRight,blackCount);
	}
private:
	pNode _pRoot;
};

void Test()
{
	int arr[] = { 10,7,8,15,5,6,11,13,12 };
	RBTree<int,int> rbt;

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
		rbt.Insert(arr[i],arr[i]);
	cout << "中序遍历结果：" << endl;
	rbt.InOrder();
	if (rbt.Ischeck())
		cout << "是红黑树" << endl;
	else
		cout << "不是红黑树" << endl;
}

测试结果：