数据结构——红黑树（详解性质+C++模拟）

前言

本篇博客将为大家重点讲述红黑树这一数据结构，讲解其实现的方式即其具有的性质，并且最后用C++进行模拟实现这一数据结构，和AVL树相同，这篇文章也着重讲解关于其的插入操作。

由于其本质是一颗搜索二叉树，所以想要学习这一数据结构的同学需要首先了解二叉搜索树是什么，下面是博主以前写的关于二叉搜索树的博客链接，不清楚二叉搜索树是什么的伙伴可以先看看下面这篇博客：

博客链接: 数据结构 ——二叉搜索树(附C++模拟实现)

红黑树的概念

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

红黑树的性质

现在，我们的问题就是，为什么红黑树能保证：其最长路径种节点个数不会超过最短的两倍呢？
这就要从红黑树的性质出发了，看如下性质:

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

由于满足这五个性质，我们考虑最短路径的情况: 路径上的结点都是黑色的，最长路径:路径上的结点都是红黑相间的，那么又由于每条路径都有相同数量的黑色结点，所以一定有最长路径不超过最短路径的两倍。

---

在了解了性质之后，接下来就我们就边模拟实现红黑树边讲解其是如何操作来维护这些特性的把！

红黑树结点的定义

//用一个枚举常量来表示颜色
enum Color
{
	RED,
	BLACK
};

template<typename K, typename V>
struct RBTree_Node
{
	//为了提高对该结构操作的效率需要使用三叉链
	RBTree_Node<K, V>* _parent = nullptr;
	RBTree_Node<K, V>* _right = nullptr;
	RBTree_Node<K, V>* _left = nullptr;

	std::pair<K, V> _kv;
	int _color = RED;

	RBTree_Node(const std::pair<K,V>& kv)
		:_kv(kv)
	{}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这里有一个问题是，为什么要将结点的默认颜色给成红色？

我们考虑插入操作，由于插入，我们有可能会破坏红黑树的性质，那么，大家觉得性质3和性质4哪个更好维护？
显然是性质3（不能有连续的红节点），而插入一个红节点一定不会破坏性质4，因此我们选择默认插入红节点。

红黑树的插入操作

与AVL树相同，红黑树也是在二叉搜索树的基础上加上其平衡条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索树的规则插入新结点

	bool insert(const std::pair<K, V>& kv)
	{
		//如果root是空节点，直接插入即可
		if (!_root)
		{
			node* newNode = new node(kv);
			//根节点的颜色一定是黑色
			newNode->_color = BLACK;
			_root = newNode;
			return true;
		}
		const K& newKey = kv.first;
		//寻找插入位置
		node* parent = nullptr, * cur = _root;
		while (cur)
		{
			const K& Key = cur->_kv.first;
			parent = cur;
			if (Key < newKey)
				cur = cur->_right;
			else if (Key > newKey)
				cur = cur->_left;
			else
				return false;
		}
		//到达此位置，说明插入的是一个新数据
		node* newNode = new node(kv);
		//插入一个红色节点，对旧树的影响最小
		//只需要修改连续的两个红色节点即可
		if (parent->_kv.first > newKey)
			parent->_left = newNode;
		else
			parent->_right = newNode;
		newNode->_parent = parent;
		cur = newNode;
		//新结点插入后，需要检查红黑树的性质是否遭到破坏，如果破坏，需要进行一系列的调整
		//....
		
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

2. 检测新节点插入后，红黑树的性质是否遭到破坏

因为新节点默认颜色是红色，因此：如果双亲结点的颜色是黑色，那就不需要继续调整，但当双亲结点颜色是红色的时候，就违反了不能有连续红节点的性质，此时需要分类讨论来调整红黑树：

在此之前，先对一些符号做一些解释：
cur: 当前结点p：父节点
g：祖父节点 u：叔叔结点（父结点的兄弟结点）

首先由于插入前一定是红黑树，所以如果p为红，g一定为黑，因此有些情况不存在

情况一：cur为红，p为红，g为黑，u存在且为红
下图种的a，b, c, d, e是任意红黑树子树，也可以是空

此时，为了同时维护性质3和性质4，我们把p和u变黑，然后让g变红，这样这两条路径的黑色结点数量相当于没有变化。

但是调整为g之后，g有可能是整棵树的根节点，也有可能是子树的根，而如果不是根节点，我们还需要继续向上判断是否有连续红节点存在，如果是根节点，直接将其变为黑色之后即可结束调整

//修改红色节点的逻辑
while (parent && parent->_color == RED)
{
	//双亲是红色，那么爷爷节点一定是黑色
	if (parent == _root)
	{
		parent->_color = BLACK;
		break;
	}
	node* grandfather = parent->_parent;
	//由于不知道p是g的左孩子还是右孩子，所以需要判断一下
	node* uncle = parent == grandfather->_left ? grandfather->_right : grandfather->_left;
	if (uncle && uncle->_color == RED)
	{
		//通过这一个操作就可以保证两条路径上的黑色节点的数量不变
		grandfather->_color = RED;
		uncle->_color = parent->_color = BLACK;
		//由于将爷爷节点变成红色，所以有可能会导致前面的节点也出现连续红节点的情形，需要继续判断
		cur = grandfather;
		parent = cur->_parent;
	}
	else
	{
		//...
	}
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

---

对于接下来两种情况，需要使用AVL树中的旋转操作，如果有不知道旋转操作如何实现的可以看看博主的另一篇博客:
链接 --> AVL详解
在这篇文章中有详细介绍旋转如何实现的部分，大家可以通过目录直接跳转观看即可。

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

1. u不存在
   

如果u节点不存在，那么cur一定是新插入的结点，如果cur不是新插入的结点，那么根据性质3: cur和p一定有一个在调整前是黑色，那么以g为根结点的树就不满足红黑树的性质四:每条路径黑色结点个数相同

2. u结点存在并且是黑色
   

如果u结点存在并且是黑色，那么cur结点原来的颜色一定是黑色，现在是红色的原因是cur子树调整的过程中变成了红色。

这是由于如果cur是新增结点，那么在插入cur之前就已经不满足性质四，p，g路径上的黑色结点数目一定比u,g路径上的黑色结点数目少

对于这种情况，如果

p为g的左孩子，cur为p的左孩子，则进行右单旋操作
如果p为g的右孩子，cur为p的右孩子，则进行左单旋操作。
最后将p变成黑色，g变成红色即可完成调整
对于上图中的情况，旋转完之后得到：

我们来看一下为什么旋转之后能够维护红黑树的性质:
首先，很容易可以发现旋转只会对旋转前g的子树造成影响，并且通过图可以得知a, b, c, d, e这五个子树的路径上的黑色结点数量和旋转前并没有发生变化，因此这样子的操作是完全可行的。

并且如果我们不考虑各个结点上的值的话，这种做法可以理解为让p的左边路径少一个红节点，p的右边路径多一个红节点，并没有改变黑结点的数量，所以这个方法可行。

情况三:cur为红色，p为红，g为黑，u不存在/u存在且为黑
该情况和情况二不同的地方在于p和cur在其双亲的不同位置，对于这种情况，我们需要使用双旋的方法。

1. 如果p为g的左孩子，cur为p的右孩子，则针对p做左单旋，之后就转换成了情况2，再使用一次右单旋即可恢复平衡
2. 如果p为g的右孩子，cur为p的左孩子，则针对p做右单旋，同样转换为情况2，然后再使用一次左单旋即可。

上图第一步转换完成后:

由于这里的第一步是为了转换成情况2，所以我们只需要分析第一步是否会破坏红黑树的性质即可。

根据上图可知，第一步旋转完成之后，五颗子树的黑节点数量也斌没有发生变化，因此方法可行。

如此，我们就分析完了所有调整操作了，下面附上完整插入代码：

public:
	bool insert(const std::pair<K, V>& kv)
	{
		//如果root是空节点，直接插入即可
		if (!_root)
		{
			node* newNode = new node(kv);
			//根节点的颜色一定是黑色
			newNode->_color = BLACK;
			_root = newNode;
			return true;
		}
		const K& newKey = kv.first;
		//寻找插入位置
		node* parent = nullptr, * cur = _root;
		while (cur)
		{
			const K& Key = cur->_kv.first;
			parent = cur;
			if (Key < newKey)
				cur = cur->_right;
			else if (Key > newKey)
				cur = cur->_left;
			else
				return false;
		}
		//到达此位置，说明插入的是一个新数据
		node* newNode = new node(kv);
		//插入一个红色节点，对旧树的影响最小
		//只需要修改连续的两个红色节点即可
		if (parent->_kv.first > newKey)
			parent->_left = newNode;
		else
			parent->_right = newNode;
		newNode->_parent = parent;
		cur = newNode;
		//修改红色节点的逻辑
		while (parent && parent->_color == RED)
		{
			//双亲是红色，那么爷爷节点一定是黑色
			if (parent == _root)
			{
				parent->_color = BLACK;
				break;
			}
			node* grandfather = parent->_parent;
			//由于不知道p是g的左孩子还是右孩子，所以需要判断一下
			node* uncle = parent == grandfather->_left ? grandfather->_right : grandfather->_left;
			if (uncle && uncle->_color == RED)
			{
				//通过这一个操作就可以保证两条路径上的黑色节点的数量不变
				grandfather->_color = RED;
				uncle->_color = parent->_color = BLACK;
				//由于将爷爷节点变成红色，所以有可能会导致前面的节点也出现连续红节点的情形，需要继续判断
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				//如果叔叔不存在或者叔叔节点位黑色，需要进行旋转操作
				bool parent_in_right = true, cur_in_right = true;
				if (grandfather->_left == parent) parent_in_right = false;
				if (parent->_left == cur) cur_in_right = false;
				if (parent_in_right && cur_in_right)
				{
					rotateL(grandfather);
					grandfather->_color = RED;
					parent->_color = BLACK;
				}
				else if (!parent_in_right && !cur_in_right)
				{
					rotateR(grandfather);
					grandfather->_color = RED;
					parent->_color = BLACK;
				}
				else if (parent_in_right && !cur_in_right)
				{
					rotateRL(grandfather);
					cur->_color = BLACK;
					grandfather->_color = RED;
				}
				else
				{
					rotateLR(grandfather);
					cur->_color = BLACK;
					grandfather->_color = RED;
				}
				_root->_color = BLACK;
				break;
			}
		}
		//如果插入节点的双亲是一个黑节点，不需要处理
		return true;
	}
private:
	void rotateL(node* parent)
	{
		node* cur = parent->_right, * curL = cur->_left;
		node* ppnode = parent->_parent;
		//连接cur和parent
		cur->_left = parent;
		parent->_parent = cur;
		//连接parent和curL
		parent->_right = curL;
		if (curL) curL->_parent = parent;
		//连接ppnode和cur
		cur->_parent = ppnode;
		if (!ppnode) _root = cur;
		else
		{
			if (ppnode->_left == parent)
				ppnode->_left = cur;
			else if (ppnode->_right == parent)
				ppnode->_right = cur;
			else
				throw "二叉树连接异常";
		}
	}
	void rotateR(node* parent)
	{
		node* cur = parent->_left, * ppnode = parent->_parent;
		node* curR = cur->_right;
		//连接cur和parent
		cur->_right = parent;
		parent->_parent = cur;
		//连接parent和curR
		parent->_left = curR;
		//注意判断curR为空的情况
		if (curR) curR->_parent = parent;
		//连接ppnode和cur
		cur->_parent = ppnode;
		if (!ppnode)
			_root = cur;
		else
		{
			if (ppnode->_right == parent)
				ppnode->_right = cur;
			else if (ppnode->_left == parent)
				ppnode->_left = cur;
			else
				throw "二叉树链接异常\n";
		}
	}
	void rotateRL(node* parent)
	{
		rotateR(parent->_right);
		rotateL(parent);
	}
	void rotateLR(node* parent)
	{
		rotateL(parent->_left);
		rotateR(parent);
	}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

---

红黑树的验证

完成了红黑树的插入操作，我们当然要有办法验证手搓的红黑树是否满足其性质。
红黑树的检测分为两部分：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2. 检测其是否满足红黑树的性质

public:
	bool isRBTree() { return _isRBTree(_root); }
private:
	bool _isRBTree(node* root)
	{
		if (!root) return true;
		if (root->_color == RED) return false;
		bool RB1 = no_seriesRed(root);
		if (!RB1)
			return false;
		int blackNum = -1;
		bool RB2 = equalBlack(root, 0, blackNum);
		if (!RB2)
			return false;
		return true;
	}
	//验证没有连续的红节点
	bool no_seriesRed(node* root)
	{
		if (!root) return true;
		if (root->_color == RED)
			if (root->_parent && root->_parent->_color == RED)
			{
				std::cout << "连续红节点\n";
				return false;
			}
		return no_seriesRed(root->_left)
			&& no_seriesRed(root->_right);
	}
	//验证每条路径上的黑色结点数量是否都相同
	bool equalBlack(node* root, int now, int& blackNum)
	{
		if (!root)
		{
			if (blackNum == -1) blackNum = now;
			else if (now != blackNum)
			{
				std::cout << "黑节点数量不一致\n";
				return false;
			}
			return true;
		}

		if (root->_color == BLACK) now += 1;
		return equalBlack(root->_left, now, blackNum)
			&& equalBlack(root->_right, now, blackNum);
	}
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
40
41
42
43
44
45
46
47

总结

以上就是关于红黑树的所有内容啦，大家如果想要真正掌握红黑树，光看代码肯定是不够的，一定要自己下去模拟实践一次才能真正的掌握其核心，并且一定要深入理解它的性质！！以上就是本篇博客的所有内容啦，如果博主有哪里写的有问题或者有大家疑惑的地方，欢迎在评论区指出！！