C++实现红黑树

发布时间：2023-11-11 11:30

一、红黑树的性质

红黑树也是二叉搜索树，它的每个节点增加了一个单位用来表示颜色，可以是Red也可以是Black，通过对任意一条根到叶子节点的颜色来约束，红黑树保证最长路径是最短路径的两倍，因此近似平衡。
红黑树的性质：
1、每个节点不是红色就是黑色
2、树的根节点是黑色
3、如果一个节点是红色，则它的两个孩子节点是黑色的（没有连续的红色）
4、 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(每条路径上黑色结点的数量相等）
看一下红黑树的节点结构： 
enum COLOR
{
	BLACK,
	RED
};

template
struct RBTreeNode
{
	RBTreeNode(const K& key, const V& value, COLOR color = RED)
	:_pLeft(NULL)
	, _pRight(NULL)
	, _pParent(NULL)
	, _key(key)
	, _value(value)
	, _color(color)
	{}

	RBTreeNode *_pLeft;
	RBTreeNode *_pRight;
	RBTreeNode *_pParent;

	K _key;
	V _value;
	COLOR _color;
};

二、插入节点后分析
1、插入的位置若为根节点，根据性质可知调整为黑色。
2、插入节点后，违反了性质，需要做调整，可能遇到下面三种情况：
注：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：
cur为红，p为红，g为黑，u存在且为红，如下图：

C++实现红黑树_第1张图片

不能将p直接改为黑色，这样会改变某路径黑色节点的个数。
情况二：

cur为红，p为红，g为黑，u不存在/u为黑，如下图，对树g右旋：

C++实现红黑树_第2张图片
 上图，p为g的左孩子，cur为p的左孩子，则进行右单旋转；同理，p为g的右孩子，cur 为p的右孩子，则进行左单旋转。
注：左旋及右旋的具体过程和AVL树很像，只有少了平衡因子的更新，但是多了变色处理。具体可以参考上篇AVL树。
情况三：

cur为红，p为红，g为黑，u不存在/u为黑，如下图，对树cur左旋：
C++实现红黑树_第3张图片
转化为情况二，对g进行右旋。

上图，p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；同理，p为g的右孩子， cur为p的左孩子，则针对p做右单旋转。
插入算法代码如下： 
	bool Insert(const K& key, const V& value)
	{
		if (NULL == _pRoot)
		{
			_pRoot = new Node(key, value, BLACK);   //根节点为黑色
			return true;
		}

		//找插入位置
		pNode pCur = _pRoot;
		pNode pParent = NULL;

		while (pCur)
		{
			if (key < pCur->_key)
			{
				pParent = pCur;
				pCur = pCur->_pLeft;
			}
			else if (key > pCur->_key)
			{
				pParent = pCur;
				pCur = pCur->_pRight;
			}
			else
			{
				return false;
			}
		}

		pCur = new Node(key, value);
		if (key < pParent->_key)
			pParent->_pLeft = pCur;
		else
			pParent->_pRight = pCur;

		pCur->_pParent = pParent;

		//有可能会违反红黑树的性质---3
		while (pParent&&pParent->_color == RED)
		{
			pNode grandParent = pParent->_pParent;
			if (pParent == grandParent->_pLeft)
			{
				pNode uncle = grandParent->_pRight;
				//情况一，叔叔节点存在且为红
				if (uncle&&uncle->_color == RED)
				{
					pParent->_color = BLACK;
					uncle->_color = BLACK;
					grandParent->_color = RED;

					pCur = grandParent;   //继续向上调整
					pParent = pCur->_pParent;
				}

				//叔叔不存在或者存在且为黑
				else
				{
					//若是第三种情况转化为第二种
					if (pCur == pParent->_pRight)
					{
						RotateL(pParent);
						swap(pParent, pCur);
					}

					RotateR(grandParent);
					pParent->_color = BLACK;
					grandParent->_color = RED;
					break;
				}
			}
			//父亲节点为双亲的右节点
			else
			{
				pNode uncle = grandParent->_pLeft;
				//情况一，叔叔节点存在且为红
				if (uncle&&uncle->_color == RED)
				{
					pParent->_color = BLACK;
					uncle->_color = BLACK;
					grandParent->_color = RED;

					pCur = grandParent;   //继续向上调整
					pParent = pCur->_pParent;
				}

				//叔叔不存在或者存在且为黑
				else
				{
					//若是第三种情况转化为第二种
					if (pCur == pParent->_pLeft)
					{
						RotateR(pParent);
						swap(pParent, pCur);
					}

					RotateL(grandParent);
					pParent->_color = BLACK;
					grandParent->_color = RED;
				}
			}
		}
		_pRoot->_color = BLACK;
		return true;
	}

三、判断是否为红黑树
根据红黑树的性质，根节点为黑色；要满足任何一个路径黑色节点的个数相等， 我们可以分别统计每条黑色节点的个数，当相等时就判断是不是红黑树 ；以及有没有相邻的红色节点。 

bool IsRBTree()
	{
		if (_pRoot == NULL)
			return true;
		if (_pRoot->_color == RED)  //根节点为红色
			return false;

		int blackNum = 0;  //黑色节点的个数
		int num = 0;     //任意路径的黑色节点个数
		pNode pCur = _pRoot;
		while (pCur)
		{
			if (pCur->_color == BLACK)
			{
				blackNum++;
			}
			pCur = pCur->_pLeft;
		}

		return _IsRBTree(_pRoot, blackNum, num);
	}
bool _IsRBTree(pNode pRoot, const int blackNum, int num)
	{
		if (NULL == pRoot)  //一条路径结束
		{
			if (num != blackNum)
			{
				return false;
			}
			else
			{
				return true;
			}
		}
		if (pRoot->_color == BLACK)
		{
			++num;
		}
		//两个相邻的红色节点
		if ((pRoot->_color == RED) && (pRoot->_pParent->_color == RED))
		{
			return false;
		}
		return _IsRBTree(pRoot->_pLeft, blackNum, num) && _IsRBTree(pRoot->_pRight, blackNum, num);
	}

完整代码如下： 
#pragma once

enum COLOR
{
	BLACK,
	RED
};

template
struct RBTreeNode
{
	RBTreeNode(const K& key, const V& value, COLOR color = RED)
	:_pLeft(NULL)
	, _pRight(NULL)
	, _pParent(NULL)
	, _key(key)
	, _value(value)
	, _color(color)
	{}

	RBTreeNode *_pLeft;
	RBTreeNode *_pRight;
	RBTreeNode *_pParent;

	K _key;
	V _value;
	COLOR _color;
};

template
class RBTree
{
	typedef RBTreeNode 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;
		pNode pParent = NULL;

		while (pCur)
		{
			if (key < pCur->_key)
			{
				pParent = pCur;
				pCur = pCur->_pLeft;
			}
			else if (key > pCur->_key)
			{
				pParent = pCur;
				pCur = pCur->_pRight;
			}
			else
			{
				return false;
			}
		}

		pCur = new Node(key, value);
		if (key < pParent->_key)
			pParent->_pLeft = pCur;
		else
			pParent->_pRight = pCur;

		pCur->_pParent = pParent;

		//有可能会违反红黑树的性质---3
		while (pParent&&pParent->_color == RED)
		{
			pNode grandParent = pParent->_pParent;
			if (pParent == grandParent->_pLeft)
			{
				pNode uncle = grandParent->_pRight;
				//情况一，叔叔节点存在且为红
				if (uncle&&uncle->_color == RED)
				{
					pParent->_color = BLACK;
					uncle->_color = BLACK;
					grandParent->_color = RED;

					pCur = grandParent;   //继续向上调整
					pParent = pCur->_pParent;
				}

				//叔叔不存在或者存在且为黑
				else
				{
					//若是第三种情况转化为第二种
					if (pCur == pParent->_pRight)
					{
						RotateL(pParent);
						swap(pParent, pCur);
					}

					RotateR(grandParent);
					pParent->_color = BLACK;
					grandParent->_color = RED;
					break;
				}
			}
			//父亲节点为双亲的右节点
			else
			{
				pNode uncle = grandParent->_pLeft;
				//情况一，叔叔节点存在且为红
				if (uncle&&uncle->_color == RED)
				{
					pParent->_color = BLACK;
					uncle->_color = BLACK;
					grandParent->_color = RED;

					pCur = grandParent;   //继续向上调整
					pParent = pCur->_pParent;
				}

				//叔叔不存在或者存在且为黑
				else
				{
					//若是第三种情况转化为第二种
					if (pCur == pParent->_pLeft)
					{
						RotateR(pParent);
						swap(pParent, pCur);
					}

					RotateL(grandParent);
					pParent->_color = BLACK;
					grandParent->_color = RED;
				}
			}
		}
		_pRoot->_color = BLACK;
		return true;
	}

	bool IsRBTree()
	{
		if (_pRoot == NULL)
			return true;
		if (_pRoot->_color == RED)  //根节点为红色
			return false;

		int blackNum = 0;  //黑色节点的个数
		int num = 0;     //任意路径的黑色节点个数
		pNode pCur = _pRoot;
		while (pCur)
		{
			if (pCur->_color == BLACK)
			{
				blackNum++;
			}
			pCur = pCur->_pLeft;
		}

		return _IsRBTree(_pRoot, blackNum, num);
	}
	void InOrder()
	{
		if (NULL == _pRoot)
			return;
		_InOrder(_pRoot);
	}
private:
	bool _IsRBTree(pNode pRoot, const int blackNum, int num)
	{
		if (NULL == pRoot)  //一条路径结束
		{
			if (num != blackNum)
			{
				return false;
			}
			else
			{
				return true;
			}
		}
		if (pRoot->_color == BLACK)
		{
			++num;
		}
		//两个相邻的红色节点
		if ((pRoot->_color == RED) && (pRoot->_pParent->_color == RED))
		{
			return false;
		}
		return _IsRBTree(pRoot->_pLeft, blackNum, num) && _IsRBTree(pRoot->_pRight, blackNum, num);
	}
	//左单旋
	void RotateL(pNode pParent)
	{
		pNode pSubR = pParent->_pRight;
		pNode pSubRL = pSubR->_pLeft;

		//处理pSubR
		pParent->_pRight = pSubRL;
		if (pSubRL)
			pSubRL->_pParent = pParent;

		pSubR->_pLeft = pParent;
		pNode pPParent = pParent->_pParent;
		pSubR->_pParent = pPParent;
		pParent->_pParent = pSubR;

		//判断是否为根
		if (pParent == _pRoot)
			_pRoot = pSubR;
		//判断是左子树还是右子树
		else
		{
			if (pPParent->_pLeft == pParent)
				pPParent->_pLeft = pSubR;
			else
				pPParent->_pRight = pSubR;
		}
	}

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

		//处理pSubR
		pParent->_pLeft = pSubLR;
		if (pSubLR)
			pSubLR->_pParent = pParent;

		pSubL->_pRight = pParent;
		pNode pPParent = pParent->_pParent;
		pSubL->_pParent = pPParent;
		pParent->_pParent = pSubL;

		//判断是否为根
		if (pParent == _pRoot)
			_pRoot = pSubL;
		//判断是左子树还是右子树
		else
		{
			if (pPParent->_pLeft == pParent)
				pPParent->_pLeft = pSubL;
			else
				pPParent->_pRight = pSubL;
		}
	}

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

void RBTreeTest()
{
	int array[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	RBTree t;
	for (size_t i = 0; i < sizeof(array) / sizeof(array[0]); i++)
	{
		t.Insert(array[i], i);
	}
	t.InOrder();

	if (t.IsRBTree())
		cout << "是红黑树" << endl;
	else
		cout << "不是红黑树" << endl;
}

相关推荐

python中temp是什么

一文详解Python中的重试机制

C++编程之内存分区模型

数据库三大范式和事务四大特性

机器学习入门基础（二）

5.MSDN的下载和使用

(4)vue组件传值

深入理解JavaScript内存管理和GC算法

利用yaml定义卷积网络【附代码】

本地连接服务器mysql

关于JDBC连接MySQL数据库发生的异常

1.初识C语言（1）

边车容器下的服务网格istio

Spring学习笔记（4）Spring 事件原理及其应用

RocketMQ可以应用于哪些场景？

QT显示当前日期时间

亲测SQL Server2019安装的详细步骤

Vue分页组件的封装方法

前端vue3+token实现用户认证

Spring 核心

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网，如有侵权请联系：561261067@qq.com

桂ICP备16001015号