【数据结构】红黑树

一. 红黑树的概念    


     红黑树是一颗二叉搜索树,它的每个结点增加一个存储单位来表示结点的颜色,这个颜色是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, k, blackCount) &&
			_IsCheck(pRoot->_pRight, k, 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;
}

测试结果:

相关文章
相关标签/搜索