C++：红黑树

目录

一、关于红黑树

1、红黑树和AVL树区别

2、红黑树规则

二、红黑树

1、红黑树变色举例

2、红黑树具体情况分析

①、情况一：只变色

②、情况二：单旋 + 变色

③、情况三：双旋 + 变色

三、红黑树的模拟实现

---

一、关于红黑树

1、红黑树和AVL树区别

我们前面学过的AVL树是左右子树的高度差不超过1

而红黑树则是最长路径不超过最短路径的2倍

由于AVL树是严格要求平衡的，而红黑树并不严格要求，是接近平衡的，所以在插入相同的数据时，AVL树旋转更多，而红黑树旋转更少

---

2、红黑树规则

首先红黑树也是一种二叉搜索树，但是结点增加了颜色属性，红色或黑色，同时红黑树确保了：最长路径不超过最短路径的2倍，具体红黑树性质如下：

①、每个结点不是红色就是黑色

②、根结点必须是黑色

③、如果一个结点是红色的，那么它的孩子必须是黑的（也就是说，红黑树中不会出现连续的红色结点）

④、对于每个结点，从该结点到后代叶节点的简单路径上，都包含相同数量的黑色结点（每条路径的黑结点个数相同）

⑤、每个叶子结点(NIL结点)都是黑色的（空结点是黑色的）

---

需要注意的是，为什么满足这几条规则就可以保证最长路径不超过最短路径的2倍：

因为我们可以想想，由于根结点是黑色，那么为了保证两个红结点不能连续出现，每个路径黑结点个数相同，那么最短路径最极限的情况就是只出现黑结点

而我们知道红结点的左右字树必须是黑结点，且每条路径的黑结点数量必须相同，因此想要增加结点只能增加红结点，所以最短路径假设有n个黑结点，那么在最长路径中，这n个黑结点每一个黑结点的下面，极限情况来说最多跟着一个红结点，如下图所示：

因此理想情况最长路径也就是多了与最短路径的黑结点数量相同的红结点，所以在最极限的情况下，最长路径也只是2n个结点，而最短路径是n个结点，因此可以保证最长路径不超过最短路径的2倍

---

二、红黑树

1、红黑树变色举例

先举个例子，现在我们想在红黑树中插入一个结点，那么就有两个选择，插入的结点是红色或黑色，接下来就要考虑到底是选红色还是黑色 

首先，如果选红色，可能会违反红黑树的规则3，因为插入结点的父结点也可能是红色的

如果选黑色，则一定会违反红黑树的规则4，因为在一个路径下插入黑色结点，会导致无法满足该路径与其他路径的黑色结点相同

所以对比来看，我们一定选择的插入结点是红色的，因为选红色，可能会违反规则，也可能不会违反，而选黑色一定会违反；其次，选红色如果违反，相比较而言，规则3比规则4好修正一些

下面举个只变色例子方便理解红黑树的插入：

图中的cur、par、un、grapar代表某一个结点

cur就是当前位置的结点

par就是parent，即cur的父结点

grapar就是grandparent，即parent的父结点

un就是uncle，即parent的兄弟结点

cur插入到par的左边，这时两个红结点相连了，而规则3表示不能两个红结点相连，由于我们已经选择了cur为红色，所以唯一的措施就是将par变黑，这时需要注意，如果par有兄弟结点，如上图的un，也需要一同变黑，随着un和par变黑，会让他们这两条路径多一个黑结点，不满足规则4，所以将他们的父结点grapar变红，这时满足规则4，第一次更改结束

---

下面是第二次更改：

将第一次的四个位置对应的结点做以改变，如上图，接着重复第一步的操作，cur和par都是红色，所以改par为黑，而par的兄弟结点un也改为黑，这两条路径都多了个黑结点，所以grapar变为红，第二次改变结束

---

第三次：

将对应位置改变完后，发现不满足规则2，根结点cur是红色的，又发现cur的parent为空，所以将cur变为黑色，从而满足规则2，第三次改变结束，整个红黑树的插入过程就结束了

当然也有变色+旋转的情况，下面会说到，上面就是为了方便说清楚红黑树是怎么变的

---

2、红黑树具体情况分析

图中的cur就是当前位置的结点

p就是parent，即cur的父结点

g就是grandparent，即parent的父结点

u就是uncle，即parent的兄弟结点

①、情况一：只变色

情况一是cur为红，p为红，g为黑，u存在为红

为了方便起见，上图中出现的cur、par、un、grapar这几个单词分别在图中用cur、p、u、g表示

具体情况太多，所以这里用抽象图做以说明，且抽象图可能是完整的树，也可能是子树：

其中三角形a/b/c/d/e是子树，可能存在也可能不存在

场景1：a/b/c/d/e是空树，cur是新增结点

按照上面举例的红黑树变色样例的规则，变色处理

如果g不是根，把g当做cur继续往上处理

如果g是根，把g变为黑色，处理结束

---

场景2：cur不是新增，a/b/c/d/e子树不为空

可能是由下面的新增变化得来的

cur不是新增结点，而是由新增节点变色后得到情况1的场景

接着继续继续变色处理：

就和场景1一样，如果g不是根，把g当做cur继续往上处理

如果g是根，把g变为黑色，处理结束

---

②、情况二：单旋 + 变色

注意，下面的单旋双旋就不具体说怎么操作的，在AVL树部分的博客已经详细说明了

情况二是cur为红，p为红，g为黑，u不存在/u存在且为黑

场景1：a/b/c/d/e是空树，cur是新增结点，u不存在

这时u不存在，不能直接将p变黑，相当于凭空多了一个黑结点，情况1有u的时候，可以将p和u同时变黑，再将g变红，相当于黑结点不多不少，而u不存在的情况，直接将p变黑，如果将来是下图这种情况，就会有问题：

如上图，如果依然只进行变色处理会导致最左边路径的黑结点多于其他路径的黑结点

这时要进行右单旋 + 变色处理：

即完成处理

---

场景2：a/b/c/d/e不是空树，cur不是新增结点，u存在且为黑

这种场景下，d/e可以是空树或者一个红结点，我们当做空树处理

c可以是根是黑结点的子树，即下面四种的任意一种，我们选择第一种

上图变为：

这时第一步变色处理后，如图：

接着和场景1一样，g结点进行右单旋处理，且p变黑g变红：

场景2处理结束

---

③、情况三：双旋 + 变色

情况三是cur为红，p为红，g为黑，u不存在/u存在且为黑

与情况二不同的是情况三cur、g、p三个结点是折线，而情况二是直线，模型图如下：

a/b/c/d/e是子树

---

场景1：a/b/c/d/e是空树，cur是新增结点，u不存在

p结点先左单旋：

这时图形就变为和情况二一样的形状了

这时再将结点g进行右单旋，并且g变为红，cur变为黑

这时变处理完成了

---

场景2：a/b/c/d/e不是空树，cur不是新增结点，u存在且为黑

这种场景下，d/e可以是空树或者一个红结点，我们当做空树处理

a可以是根是黑结点的子树，即下面四种的任意一种，我们选择第一种

这时上图变为：

这时第一步变色处理后，如图：

变色处理后，上半部分的样子就场景1的形状一样了

接着和上面场景1一样，结点p左单旋：

这时就和情况二一样，再将结点g右单旋，同时将g变为红，cur变为黑

至此这种场景也处理完成了

---

通过这三种情况，我们可以发现，uncle这个结点是至关重要的

uncle存在且为红色，则变色继续网上处理

uncle存在且为黑或是uncle不存在，则需要旋转+变色处理，具体单旋还是双旋看具体情况

---

三、红黑树的模拟实现

具体见代码，有详细注释

//颜色：红色或黑色，使用枚举
enum Color
{
	RED,
	BLACK
};
 
//和AVL树构造差不多，多了颜色，少了平衡因子
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
 
	pair _kv;
	
	//颜色
	Color _col;
 
	//构造函数
	RBTreeNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
	{}
};
 
 
template<class K, class V>
struct RBTree
{
	typedef RBTreeNode Node;
public:
	bool insert(const pair& kv)
	{
		//如果根结点为空，则用kv来new一个新结点
		//并将颜色给为黑色
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		//遍历，直到找到空结点
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			//插入的值大于该结点
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			//插入的值小于该结点
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			//插入的值相等于该结点
			else
			{
				return false;
			}
		}
 
		//判断插入结点在父结点的左还是右
		cur = new Node(kv);
		//新插入结点是红色
		cur->_col = RED; 
 
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		//链接插入结点的parent
		cur->_parent = parent;
 
		//循环判断是否处理结束
		while (parent && parent->_col == RED)
		{
			Node* grandparent = parent->_parent;
			//断言检查grandparent颜色及是否存在
			assert(grandparent);
			assert(grandparent->_col == BLACK);
 
			//判断uncle结点在grandparent的左还是右
			if (parent == grandparent->_left)
			{
				Node* uncle = grandparent->_right;
				//情况一	:u存在且为红，变色+继续往上处理
				if (uncle && uncle->_col == RED)
				{
					//p和u变黑，g变红
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
 
					//接着将g当做cur继续往上执行
					cur = grandparent;
					//找到cur的父结点
					parent = cur->_parent;
				}
				//情况二 + 情况三  
				else
				{
					//情况二：右单旋 + 变色处理
					//    g
					//  p   u  
					//c
					if (cur == parent->_left)
					{
						RotateR(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						//情况三：左右双旋 + 变色处理
						//    g
						//  p   u  
						//   c
						RotateL(parent);
						RotateR(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
 
					//情况二和情况三处理完后
					//不论g是否是根结点都不影响
					//所以不用往上执行，直接break
					break;
				}
			}
			else//parent == grandparent->_right
			{
				Node* uncle = grandparent->_left;
				//情况一:u存在且为红，变色+继续往上处理
				if (uncle && uncle->_col == RED)
				{
					//p和u变黑，g变红
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;
 
					//接着将g当做cur继续往上执行
					cur = grandparent;
					//找到cur的父结点
					parent = cur->_parent;
				}
				//情况二 + 情况三  
				else
				{
					//情况二：左单旋 + 变色处理
					//    g
					//  u   p  
					//        c
					if (cur == parent->_right)
					{
						RotateL(grandparent);
						parent->_col = BLACK;
						grandparent->_col = RED;
					}
					else
					{
						//情况三：右左双旋 + 变色处理
						//    g
						//  u   p  
						//     c
						RotateR(parent);
						RotateL(grandparent);
						cur->_col = BLACK;
						grandparent->_col = RED;
					}
 
					//情况二和情况三处理完后
					//不论g是否是根结点都不影响
					//所以不用往上执行，直接break
					break;
				}
			}
		}
 
		//将根结点的颜色保持黑色
		_root->_col = BLACK;
		return true;
	}
 
	//判断是否是红黑树
	bool IsRBTree()
	{
		if (_root == nullptr)
		{
			return true;
		}
			
		if (_root->_col == RED)
		{
			cout << "根结点为红色" << endl;
			return false;
		}
 
		//黑色结点数量的一条路径的值
		//用以比较和其他路径是否相同
		int mark = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++mark;
			}
			cur = cur->_left;
		}
 
		return PrevCheck(_root, 0, mark);
	}
 
 
 
private:
	//在检查是否是红黑树时
	//前序遍历检查每条路径的黑色节点数量是否相同
	bool PrevCheck(Node* root, int blackNum, int mark)
	{
		//当走到空结点时
		if (root == nullptr)
		{
			//如果不相等，return false
			if (blackNum != mark)
			{
				cout << "有条路径黑色结点数量不相同" << endl;
				return false;
			}
			//如果相等，return true
			else
			{
				return true;
			}
		}
 
		//是黑色就++blackNum
		if (root->_col == BLACK)
		{
			++blackNum;
		}
 
		//判断是否有两个连续的红结点
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在两个连续的红结点" << endl;
			return false;
		}
 
		//前序遍历
		return PrevCheck(root->_left, blackNum, mark)
			&& PrevCheck(root->_right, blackNum, mark);
 
	}
 
	//左单旋
	void RotateL(Node* parent)
	{
		//parR是parent的右孩子
		//parRL是parR的左孩子
		Node* parR = parent->_right;
		Node* parRL = parR->_left;
 
		parent->_right = parRL;
		//链接_parent的关系
		//可能出现parR为空的情况
		if (parRL)
			parRL->_parent = parent;
 
		parR->_left = parent;
		//记录一下parent->_parent，为下面的第二种情况
		Node* parP = parent->_parent;
		//链接_parent的关系
		parent->_parent = parR;
 
		//两种情况，平衡因子是2的结点是否是整棵树的根结点
		//1、平衡因子为2的结点是整棵树的根结点
		if (_root == parent)
		{
			_root = parR;
			parR->_parent = nullptr;
		}
		//2、平衡因子为2的结点是子树的根结点
		else
		{
			if (parP->_left == parent)
			{
				parP->_left = parR;
			}
			else
			{
				parP->_right = parR;
			}
			parR->_parent = parP;
		}
	}
 
	//右单旋
	void RotateR(Node* parent)
	{
		//定义parL和parLR
		//parL指parent的左子树
		//parLR指parL的右子树
		Node* parL = parent->_left;
		Node* parLR = parL->_right;
 
 
		parL->_right = parent;
		//记录parent的_parent，为下面的情况2做准备
		Node* parP = parent->_parent;
		parent->_parent = parL;
 
		parent->_left = parLR;
		if (parLR)
			parLR->_parent = parent;
 
		//两种情况，平衡因子是-2的结点是否是整棵树的根结点
		//1、平衡因子为-2的结点是整棵树的根结点
		if (_root == parent)
		{
			_root = parL;
			parL->_parent = nullptr;
		}
		//2、平衡因子为-2的结点是子树的根结点
		else
		{
			if (parP->_left == parent)
			{
				parP->_left = parL;
			}
			else if (parP->_right == parent)
			{
				parP->_right = parL;
			}
 
			parL->_parent = parP;
		}
	}
 
 
 
 
private:
	Node* _root = nullptr;
};
 
 
void testRBTree()
{
	int arr[] = { 5,9,1,2,6,7,3 };
	RBTree<int, int> rb;
	for (auto e : arr)
	{
		rb.insert(make_pair(e, e));
	}
	cout << "_IsRBtree:" << rb.IsRBTree() << endl;
}