C++手撕红黑树

一、什么是红黑树

红黑树在表意上就是一棵每个节点带有颜色的二叉搜索树，并通过对节点颜色的控制，使该二叉搜索树达到尽量平衡的状态。所谓尽量平衡的状态就是：红黑树确保没有一条路径比其他路径长两倍。
和AVL树不同的是，AVL树是一棵平衡树，而红黑树可能平衡也可能不平衡(因为是尽量平衡的状态)

二、红黑树的约定

要实现一棵红黑树，即要红黑树确保没有一条路径比其他路径长两倍。通过对节点颜色的约定来实现这一目标。

1.根节点是黑色的。
2.如果一个节点是红色的，则它的两个孩子都是黑色的。
3.对于每个节点，从该节点到其所有后代节点的简单路径上，均包含相同数量的黑色节点。

实现了这三条颜色规则的二叉搜索树，即也实现了没有一条路径比其他路径长两倍，即实现了一棵红黑树。
注意性质三所说的叶子节点是空节点，空节点都看成是黑色节点。

三、红黑树vsAVL

1、调整平衡的实现机制不同

红黑树根据节点颜色(同一父节点出发到叶子节点，所有路径上的黑色节点数目一样)，一些约定和旋转实现。
AVL根据树的平衡因子(所有节点的左右子树高度差的绝对值不超过1)和旋转决定。

2、红黑树的插入效率更高

红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，红黑树并不追求“完全平衡”，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能
而AVL是严格平衡树(高度平衡的二叉搜索树)，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高

3、AVL查找效率高

如果你的应用中，查询的次数远远大于插入和删除，那么选择AVL树，如果查询和插入删除次数几乎差不多，应选择红黑树。即，有时仅为了排序（建立-遍历-删除），不查找或查找次数很少，R-B树合算一些。

四、红黑树的实现

实现一棵红黑树，本质是实现它的插入函数，使插入函数可以实现红黑树的颜色约定，它的实现分为两步，即先找到插入的位置，再控制平衡。插入函数返回值设计为bool，插入成功返回true，失败返回false。控制平衡时，需要关注四个节点，即新插入的节点，它的父节点，它的叔叔节点，它的祖父节点。

1.找到插入的位置

当为第一个节点的时候，颜色设为黑，直接插入。
当插入的不是第一个节点时，颜色设为红，需要根据二叉搜索树的性质找到插入位置。并实现三叉链。

		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = Black;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		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;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = 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

2.控制平衡

(1)当父节点为黑

当父节点为黑的时候，由于插入的子节点的颜色为红，对三个约定没有任何影响，因此不需要调整平衡。

(2)判断父节点在祖父节点的位置

通过判断父节点在祖父节点的位置，来定义叔叔节点的位置，以及之后的旋转方向的判断。

while (parent && parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
   Node* uncle = grandfather->_right;
   //三种情况的处理
}
else
{
   Node* uncle = grandfather->_left;
   //三种情况的处理
}
1
2
3
4
5
6
7
8
9
10
11
12
13

首先需要使用大循环，这个循环是为情况1而准备的，情况2和3直接跳出循环即可，因为只有情况1对上层循环有影响。
下面我们以父节点在祖父节点的左侧为例，右侧同理。

(3)叔叔节点存在且为红

解决方案：将父节点和叔叔节点设为黑，将祖父节点设为红。然后将祖父节点作为新节点继续向上平衡。如果祖父节点是根节点，那么需要再将其置为黑。

注意，这种情况和其他情况不同的是，需要将祖父节点作为新插入的节点继续向上遍历，这说明需要一个循环。而其他类型的情况直接break跳出这个循环即可。

//第一种情况
if (uncle && uncle->_col == Red)
{
	parent->_col = uncle->_col = Black;
	grandfather->_col = Red;
	cur = grandfather;
	parent = cur->_parent;
}
1
2
3
4
5
6
7
8

这种情况只需要控制颜色即可，但是要继续向上循环。

(4)父节点为红，叔叔不存在或存在且为黑，新插入的节点在父节点左侧

解决方案：对祖父节点右旋操作，并将祖父节点置为红，父节点置为黑。

关于旋转的细节，我在AVL树中有详细的解释：C++手撕AVL树

//第二种情况，右单旋
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
1
2
3
4
5
6
7

(5)父节点为红，叔叔不存在或存在且为黑，新插入的节点在父节点右侧

解决方案：进行双旋，即对父节点进行左单旋，祖父节点进行右单旋。将子节点置为黑，将祖父节点置为红。

else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
1
2
3
4
5
6
7

(6)最后置黑

每一次插入都对根节点置为黑操作，因为第一种情况可能导致根节点不是黑。同时对根节点置黑也并不违反三条规定。

3.测试代码

当我们处理完父节点在祖父节点的左侧后，处理父节点在祖父节点的右侧。
全部处理之后，我们的插入代码就完成了，接下来要对整个树进行测试，即对三个约定来进行测试：

1.当根节点为红时，返回false。
2.判断一个节点和其父节点的颜色是否都为红，若都为红返回false。
3.以最左的一条路径上的根节点数量为基准，通过递归遍历每一条路径上的根节点的数量，当每条路径遍历节点到空时，将两者进行比较，如果最终结果不相等则返回false。

	bool IsBalance()
	{
		if (_root && _root->_col == Red)
		{
			cout << "根节点不是黑色的" << endl;
			return false;
		}
		int banchmark = 0;
		//以最右边一条路径为基准
		Node* left = _root;
		while (left)
		{
			if (left->_col == Black)
			{
				++banchmark;
			}
			left = left->_left;
		}
		int blackNum = 0;
		return _IsBalance(_root, banchmark, blackNum);
	}
	bool _IsBalance(Node* root, int banchmark, int blackNum)
	{
		if (root == nullptr)
		{
			if (banchmark != blackNum)
			{
				cout << "黑色根节点数目不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == Red && root->_parent->_col == Red)
		{
			cout << "出现连续的红色节点" << endl;
			return false;
		}
		if (root->_col == Black)
		{
			++blackNum;
		}
		return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, 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

五、完整代码

1.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"RBtree.h"
#include<vector>
int main()
{
	RBTree<int, int> t;
	vector<int> v;
	srand(time(0));
	int N = 100000;
	int count = 0;
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());
	}
	for (auto e : v)
	{
		pair<int,int> kv(e, e);
		t.insert(kv);
		if (t.IsBalance())
		{
			cout << "insert" << e << endl;
			count++;
			cout << count << endl;
		}
		else
		{
			cout << e << "插入失败" << endl;
			cout << "不是平衡的" << endl;
			break;
		}
	}
}
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

2.RBTree.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
enum Color
{
	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;
	Color _col;
	RBTreeNode(pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(Red)
		, _kv(kv)
	{}
};
template<class K,class V>
struct RBTree
{
	typedef RBTreeNode<K, V> Node;
private:
	Node* _root;
public:
	RBTree()
		:_root(nullptr)
	{}
	bool IsBalance()
	{
		if (_root && _root->_col == Red)
		{
			cout << "根节点不是黑色的" << endl;
			return false;
		}
		int banchmark = 0;
		//以最右边一条路径为基准
		Node* left = _root;
		while (left)
		{
			if (left->_col == Black)
			{
				++banchmark;
			}
			left = left->_left;
		}
		int blackNum = 0;
		return _IsBalance(_root, banchmark, blackNum);
	}
	bool _IsBalance(Node* root, int banchmark, int blackNum)
	{
		if (root == nullptr)
		{
			if (banchmark != blackNum)
			{
				cout << "黑色根节点数目不相等" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == Red && root->_parent->_col == Red)
		{
			cout << "出现连续的红色节点" << endl;
			return false;
		}
		if (root->_col == Black)
		{
			++blackNum;
		}
		return _IsBalance(root->_left, banchmark, blackNum) && _IsBalance(root->_right, banchmark, blackNum);
	}
	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curL = cur->_left;
		Node* curR = cur->_right;
		Node* parentParent = parent->_parent;
		parent->_left = curR;
		if (curR)
			curR->_parent = parent;
		cur->_right = parent;
		parent->_parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = cur;
				cur->_parent = parentParent;
			}
			else if (parentParent->_right == parent)
			{
				parentParent->_right = cur;
				cur->_parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curL = cur->_left;
		Node* parentParent = parent->_parent;
		parent->_right = curL;
		if (curL)
			curL->_parent = parent;
		cur->_left = parent;
		parent->_parent = cur;
		if (parent == _root)
		{
			_root = cur;
			_root->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = cur;
				cur->_parent = parentParent;
			}
			else if (parentParent->_right == parent)
			{
				parentParent->_right = cur;
				cur->_parent = parentParent;
			}
			else
			{
				assert(false);
			}
		}
	}
	bool insert(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 (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;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		while (parent && parent->_col == Red)
		{
			Node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				//第一种情况
				if (uncle && uncle->_col == Red)
				{
					parent->_col = uncle->_col = Black;
					grandfather->_col = Red;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//第二种情况，右单旋
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = Black;
						grandfather->_col = Red;
					}
					//第三种情况，左右双旋
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = Black;
						grandfather->_col = Red;
					}
					break;
				}
				_root->_col = Black;
			}
			else
			{
				Node* uncle = grandfather->_left;
				//第一种情况
				if (uncle && uncle->_col == Red)
				{
					parent->_col = uncle->_col = Black;
					grandfather->_col = Red;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//第二种情况，左单旋
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = Black;
						grandfather->_col = Red;
					}
					//第三种情况，右左双旋
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = Black;
						grandfather->_col = Red;
					}
					break;
				}
				_root->_col = Black;
			}
		}
	}
};

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257