【C++】红黑树_c++ 红黑树

---

1. 红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 红色(Red) 或 黑色(Black)。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

红黑树通过对每个节点颜色的限制，从而使得整棵树的最长路径不超过最短路径的两倍（这里说的是整棵树），虽然红黑树达不到像AVL树那样绝对平衡，但却可以达到接近平衡。

---

2. 红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

这里我们需要注意的是：最后一点说到了此处的叶子节点不是指我们平时的普通叶子节点，而是指空节点(下图种的NIL节点)，其实最后一条性质并不会影响第四条性质，因为不计算叶子节点，树中所有的路径中的黑色节点都会减一，对第四点没有任何影响。

那么为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

其实这是因为红黑树中会存在两个特殊的路径，最短路径和最长路径，当一条路径中仅有黑色节点时这条路径是最短路径，当一条路径中黑色节点和红色节点相交排列时为最长路径。当满足以上性质时，红黑树的最长路径刚好是最短路径的两倍。

---

3. 红黑树节点的定义

红黑树的节点和AVL树很相似，都需要实现三叉链（左孩子、右孩子和父亲），但不同的是红黑树节点中不需要定义控制平衡因子的变量。但是红黑树在定义节点之前需要定义一个枚举类型来控制节点的颜色。然后在节点定义的结构体中定义一个枚举类型的变量来控制每个节点的颜色。

enum Colour {
	RED,
	BLACK,
};
template <class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	
	pair<K, V> _kv;
	Colour _col;//枚举红黑树的颜色
	
	RBTreeNode(const pair<K,V> &kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在构造函数中我们默认给每个节点的颜色初始化为红色，这是因为：

我们在初始化节点的颜色时，必然会违反性质3和性质4中的一条，如果我们定义的是黑色节点，那么根据性质4的要求，每新增一个黑色节点都必须调整整棵红黑树，保证每一条路径上的黑色节点数目都相同。如果我们定义的是红色节点，根据性质3，我们只需要保证它的孩子节点是黑色就可以了。所以
为了降低每次插入节点后对红黑树的调整，我们首相初始化时将节点初始化为红色。

当然了，如果新增的节点是根节点，我们只需要将节点的颜色改为黑色即可。当新增节的父节点颜色是红色时，我们需要对该路径上的节点颜色进行进一步的调整。当新增节点的父节点颜色为黑色时，此时我们不需要做任何事情。

---

4. 红黑树的插入

红黑树的插入操作，前面的部分和普通的二叉搜索树没什么区别。唯一需要注意的是，当我们插入的节点是根节点时，我们需要将该节点的颜色修改为黑色，因为红黑树根节点的颜色只能是黑色。

bool Insert(const pair<K, V>& kv)
{
	//搜索树的插入过程
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}
	//链接节点
	cur = new Node(kv);
	if (parent->_kv.first > kv.first)
		parent->_left = cur;
	else
		parent->_right = cur;
	//红黑树的调整
	//...
	cur->_parent = parent;//链接父节点
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

当我们新增一个节点时，需要先判断一下该节点的父节点的颜色。如果该节点的父节点的颜色是黑色，不违反红黑树的性质，所以不需要进行任何调整。

如果该节点父节点的颜色是红色，此时出现了连续的红节点，不满足红黑树的性质，所以我们需要根据不同的情况来进行调整，使整棵树依然是一棵红黑树。

红黑树的调整分为两种情况：仅变色 和 旋转 + 变色