史上最详细的红黑树讲解(一篇文章教你手撕红黑树)

2023-05-18

node cur _col

🔥🔥欢迎来到小林的博客！！🛰️博客主页：✈️小林爱敲代码🛰️博客专栏：✈️数据结构与算法🛰️欢迎关注：👍点赞🙌收藏✍️留言今天给大家讲解红黑树，和AVL树一样，这章暂且不讲删除。后续有时间会为大家带来红黑树的删除操作。每日一句:生活原本沉闷，但跑起来就会有风。目录💖1.红黑树的概念�

🔥🔥 欢迎来到小林的博客！！
🛰️博客主页：✈️小林爱敲代码
🛰️博客专栏：✈️数据结构与算法
🛰️欢迎关注：👍点赞🙌收藏✍️留言

今天给大家讲解红黑树，和AVL树一样，这章暂且不讲删除。后续有时间会为大家带来红黑树的删除操作。

每日一句: 生活原本沉闷，但跑起来就会有风。

💖1. 红黑树的概念

红黑树，是一种二叉搜索树，与AVL树不同的是，它在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。因此红黑树相比于AVL树，没有那么平衡。30层高度的AVL树换成红黑树可能会有60层，但查找30次和60次并没有什么区别。AVL树的平衡是付出了代价的，它旋转的次数更多了。而红黑树也是平衡的，它旋转的次数并没有AVL多。

💖2. 红黑树的性质

红黑树必须满足以下五点性质，有一条不满足，就不是红黑树了。
1.每个节点不是红色就是黑色
2.根节点是黑色的
3.红节点的孩子必须是黑色
4.每条路径黑色节点的数量相同
5.空节点都是黑色的
满足上面性质的红黑树，它的最长路径中节点的个数不会超过最短路径的2倍

那我们先来观赏一颗红黑树

我们可以发现，
每个节点不是黑色就是红色，满足条件1
根节点 50 是黑色的，满足条件2
红色节点的孩子都是黑色，满足条件3
每条路径都有2个黑色节点，满足条件4
所有空节点的孩子都是黑色，不过是空节点，就不需要画出来了。
介绍完红黑树之后，接下来我们来实现一颗红黑树。

💖3. 红黑树的节点创建

首先，我们依旧采用三叉链，一个指针指向左孩子，一个指向右孩子，还有一个指向自己的父亲。再用一个枚举常量col 来记录节点的颜色，kv是存储的一对值。

代码：

enum Color
{
RED,
BLACK
};

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

💖4.红黑树的定义

红黑树的定义很简单，我们存一个节点指针_root来代表整棵树的根。

//红黑树实现
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree():_root(nullptr){}
private:
Node* _root;
};
1
2
3
4
5
6
7
8
9
10

💖5.节点的插入

个人认为，红黑树的插入并没有AVL那么繁琐。AVL插入时需要考虑的情况太多，而红黑树并不需要考虑太多情况。

假设我们有一颗红黑树

那么接下来我们要插入一个10，那么10应该插入20的左边。那么我们让新插入的节点颜色固定为10。根节点颜色固定为黑。

那么我们发现在插入10之后，这颗红黑树是还是正常的，满足了5条性质。此时我们在插入1个25。

我们发现插入25之后，这棵树还是正常的。所以我们可以得出一个结论，如果插入节点的父亲是黑色，那么这是一颗正常的红黑树。

那么我们此时再插入一个5，它的父亲节点就是10，也就是红色。

这种情况，这颗红黑树就不满足性质3了，因为红节点的孩子必须是黑节点。那么此时我们看它的叔叔，叔叔是25。
那么此时就会出现2种情况

情况1.叔叔存在且为红色
这种情况我们只需要把父亲和叔叔变成黑色，然后把祖父变红，再把cru给祖父，循环操作直到父亲为空即可。

这种操作会把我们的根节点变成红色，所以我们在最后的时候强制把根节点变成黑色即可。
最后这颗红黑树就会变成这样

我们可以发现它依然满足上面的五个性质。

情况2.叔叔不存在或者叔叔为黑色

叔叔不存在或者叔叔为黑色的情况是一样的。
我们先来看叔叔不存在的情况。
叔叔不存在
那么这颗红黑树是这样的

这种情况我们就要发生旋转了，因为叔叔不存在，就意味着这颗红黑树已经左边一边高了。所以我们来个右单旋即可。在右边就左单旋，具体的旋转细节可以看我上篇讲解AVL树的文章。

旋转完之后是这样的

这时候我们在把 c(新增节点) 和 g(祖父节点)变成红色，再把p(父亲节点)变为黑色。这颗红黑树就调整完毕了。

叔叔为黑的情况
叔叔为黑和叔叔不存在的情况是一样的。
我们来看看叔叔为黑的情况。

这时候我们一样要发生旋转。
旋转动图：

然后我们再把c和g变为红色，p变为黑色

这样我们的红黑树就调整完毕了。这是我们的parent在左边，uncle在右边的情况。反过来的逻辑也是一样的。

插入代码：

bool insert(const pair<K,V> kv)
{
//第一次插入
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->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
break;
}
//如果cur不为空说明有重复的值
if (cur)
return false;

//创建新节点
cur = new Node(kv);
cur->_parent = parent;
if (cur->_kv.first > parent->_kv.first)
parent->_right = cur;
else
parent->_left = cur;

cur->_col = RED;
//有连续的红节点,需要调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;//祖父节点
//parent是左孩子的情况
if (parent == grandparent->_left)
{
// 叔叔节点
Node* uncle = grandparent->_right;
//如果叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//父亲和叔叔变黑
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//迭代
cur = grandparent;
parent = cur->_parent;
}
else
{
//叔叔为黑或者叔叔不存在
if (cur == parent->_left)
{
//右单旋
RotateR(grandparent); //旋转祖父
parent->_col = BLACK;
grandparent->_col = cur->_col = RED;
}
else
{
//左右双旋
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
}
}
else
{
//parent是右孩子的情况
Node* uncle = grandparent->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
//叔叔不存在或为黑
if (cur = parent->_right)
{
//左单旋
RotateL(grandparent);
grandparent->_col = cur->_col = RED;
parent->_col = BLACK;
}
else
{
//右左双旋
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
}

}
}
_root->_col = BLACK;//不管如何，根节点的颜色一定为黑
return true;
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;

Node* grandparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (grandparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == grandparent->_left)
grandparent->_left = subL;
else
grandparent->_right = subL;
subL->_parent = grandparent;
}
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

Node* grandparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (grandparent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
grandparent->_left = subR;
else
grandparent->_right = subR;
subR->_parent = grandparent;
}
}
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

💖6.节点的查找

插入都会了，查找不是轻轻松松。从根开始找，要找的值比当前节点大，就往这棵树的右边找，小就往左边找，找到了就返回。

pair<K, V>* find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
cur = cur->_left;
else if (cur->_kv.first < key)
cur = cur->_right;
else
return &cur->_kv;
}
return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

💖7.检查红黑树

当我们代码写出来了之后，还要检查这棵树是否是红黑树。我们可以先找一个基准值(任意一条路径的黑节点数量)。因为红黑树每条路径的黑节点个数是一样的。然后我们有基准值之后，在遍历的过程计算黑节点的数量。如果与基准值一样，那么这棵树所有路径黑节点的数量是相同的。

//检查红黑树是否正常
bool IsBalance()
{
if (_root->_col == RED)
{
cout << "根节点为红色" << endl;
return false;
}

//找基准值
Node* min = _root;
int banchmark = 0;
while (min)
{
if (min->_col == BLACK)
banchmark++;
min = min->_left;
}
return _IsBalance(_root,banchmark,0);
}
bool _IsBalance(Node* root,int banchmark,int BNNum)
{
if (root == nullptr)
{
if (banchmark != BNNum)
{
cout << "路径中黑节点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "出现连续红节点"<<endl;
return false;
}

if (root->_col == BLACK)
BNNum++;

return _IsBalance(root->_left, banchmark, BNNum) &&
_IsBalance(root->_right, banchmark, BNNum);
}
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

全部代码：

#include<iostream>
using namespace std;
#include<time.h>

namespace wyl
{
enum Color
{
RED,
BLACK
};

//红黑树节点
template<class K,class V>
struct RBTreeNode
{
RBTreeNode(const pair<K,V>& kv)
: _left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
,_kv(kv){}
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Color _col;
pair<K, V> _kv;
};

//红黑树实现
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
RBTree():_root(nullptr){}
bool insert(const pair<K,V> kv)
{
//第一次插入
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->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
break;
}
//如果cur不为空说明有重复的值
if (cur)
return false;


//创建新节点
cur = new Node(kv);
cur->_parent = parent;
if (cur->_kv.first > parent->_kv.first)
parent->_right = cur;
else
parent->_left = cur;

cur->_col = RED;
//有连续的红节点,需要调整
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;//祖父节点
//parent是左孩子的情况
if (parent == grandparent->_left)
{
// 叔叔节点
Node* uncle = grandparent->_right;
//如果叔叔存在且为红
if (uncle && uncle->_col == RED)
{
//父亲和叔叔变黑
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//迭代
cur = grandparent;
parent = cur->_parent;
}
else
{
//叔叔为黑或者叔叔不存在
if (cur == parent->_left)
{
//右单旋
RotateR(grandparent); //旋转祖父
parent->_col = BLACK;
grandparent->_col = cur->_col = RED;
}
else
{
//左右双旋
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
}
}
else
{
//parent是右孩子的情况
Node* uncle = grandparent->_left;
//叔叔存在且为红
if (uncle && uncle->_col == RED)
{
uncle->_col = parent->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else
{
//叔叔不存在或为黑
if (cur = parent->_right)
{
//左单旋
RotateL(grandparent);
grandparent->_col = cur->_col = RED;
parent->_col = BLACK;
}
else
{
//右左双旋
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
parent->_col = grandparent->_col = RED;
}
}

}
}
_root->_col = BLACK;//不管如何，根节点的颜色一定为黑
return true;
}

pair<K, V>* find(const K& key)
{
if (_root == nullptr)
return nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first > key)
cur = cur->_left;
else if (cur->_kv.first < key)
cur = cur->_right;
else
return &cur->_kv;
}
return nullptr;
}


//检查红黑树是否正常
bool IsBalance()
{
if (_root->_col == RED)
{
cout << "根节点为红色" << endl;
return false;
}

//找基准值
Node* min = _root;
int banchmark = 0;
while (min)
{
if (min->_col == BLACK)
banchmark++;
min = min->_left;
}
return _IsBalance(_root,banchmark,0);
}

private:
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = parent->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;

Node* grandparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (grandparent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == grandparent->_left)
grandparent->_left = subL;
else
grandparent->_right = subL;
subL->_parent = grandparent;
}
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

Node* grandparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (grandparent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
grandparent->_left = subR;
else
grandparent->_right = subR;
subR->_parent = grandparent;
}
}

bool _IsBalance(Node* root,int banchmark,int BNNum)
{
if (root == nullptr)
{
if (banchmark != BNNum)
{
cout << "路径中黑节点数量不相等" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "出现连续红节点"<<endl;
return false;
}

if (root->_col == BLACK)
BNNum++;

return _IsBalance(root->_left, banchmark, BNNum) &&
_IsBalance(root->_right, banchmark, BNNum);
}

private:
Node* _root;
};

//以下是红黑树的测试代码
void RBTTest1()
{
RBTree<int, int> rb;
srand(time(0));
int N = 10000000;
size_t begin1 = clock();
for (int i = 0; i < N; i++)
{
rb.insert(make_pair(i, i));
}
size_t end1 = clock();
cout << "insert " << N << ":" << end1 - begin1 << endl;
//rb.insert(make_pair(20, 20));
//rb.insert(make_pair(10, 10));
//rb.insert(make_pair(5, 5));
//rb.insert(make_pair(3, 3));
rb.IsBalance();
}
}
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
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295