-
数据结构：红黑树讲解（C++）
1.前言
- 本文旨在理解红黑树基本概念以及变色旋转规则，以理解C++map和set的底层原理，不会讲红黑树的删除操作。
- 对于基本的旋转操作(单旋和双旋)，本文不会展开讲，详细讲解在这里：
AVL树旋转讲解。
2.红黑树简述
2.1概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保最长路径不超过最短路径两倍，因而是接近平衡的。
2.2性质
- 每个节点不是红色就是黑色。
- 根部节点是黑色的。(为了减少旋转次数，后面讲旋转大家就明白了）
- 对于一个红节点，它的孩子只能是黑色。(即一条路径上不能出现连续的红色节点)
- 每条路径都必须包含相同数量的黑色节点。
通过上面规则的限制，红黑树最长路径一定不会超过最短路径两倍，也就维持了高度的相对平衡。
结合3、4来看下面的两条路径：
最长：黑、红、黑、红、黑、红…………
最短：黑、黑、黑…………3.红黑树的插入
3.1关于新插入节点的颜色
对于新插入节点，我们设置为红色，原因是红黑树每条路径都必须包含相同数量的黑色节点（性质4），新插入红节点不一定破坏红黑树的结构，新插入黑色节点一定不符合性质4而且很难调整。
3.2节点的定义
//用枚举来定义颜色 enum Color { RED, BLACK }; //这里直接实现key_value模型 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(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
- 23
- 24
3.3插入新节点
这里比较简单，按二叉搜索树的规则插入即可：
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 (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 (kv.first > parent->_kv.first) //新节点在父亲右子树 { parent->_right = cur; } else //新节点在父亲左子树 { parent->_left = cur; } cur->_parent = parent; //记得更新父亲指针 /// 变色旋转维持红黑树结构（暂时省略） // _root->_col = BLACK; //可能改变根部颜色，保持根部为黑色 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
- 40
- 41
- 42
- 43
3.4判断插入后是否需要调整
其实红黑树插入后只需要看当前节点和父亲的颜色即可，其中新节点一定为红。
- 父亲为黑，符合规则，不需要调整。
- 父亲为红，此时出现红红的连续节点，需要进行调整。
3.5插入后维持红黑树结构（重点）
为了方便叙述，我们做如下定义：
- cur表示当前节点
- p表示cur父亲节点
- u表示叔叔节点
- g表示祖父(p和u的父亲)节点
3.5.1cur、p、u为红，g为黑
代码：while (parent && parent->_col == RED) //父亲为红就调整，调整到根部要结束 { Node* granderfather = parent->_parent; //祖父 //需要对叔叔进行操作，需要判断叔叔是祖父的左还是右 if (parent == granderfather->_left) //父亲是祖父的左子树 { Node* uncle = granderfather->_right; if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可 { uncle->_col = parent->_col = BLACK; granderfather->_col = RED; //当前子树可能为部分，继续向上调整 cur = granderfather; parent = cur->_parent; } else //叔叔为空或为黑色 { //先省略 } } else //父亲是祖父的右子树 { Node* uncle = granderfather->_left; if (uncle && uncle->_col == RED) //叔叔不空并且为红 { parent->_col = uncle->_col = BLACK; granderfather->_col = RED; //当前可能为部分子树，需要继续上调 cur = granderfather; 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
3.5.2cur、p为红，g为黑，u为空/u存在为黑
下面是一会要用到的旋转接口：
void RotateL(Node* parent) //左单旋,rotate->旋转 { Node* SubR = parent->_right; Node* SubRL = SubR->_left; //这个有可能为空 Node* ppnode = parent->_parent; //原来父亲的父亲 parent->_right = SubRL; if (SubRL) SubRL->_parent = parent; SubR->_left = parent; parent->_parent = SubR; if (ppnode == nullptr) //旋转的是整颗树 { _root = SubR; SubR->_parent = nullptr; } else //旋转的是部分 { if (ppnode->_left == parent) //是左子树 { ppnode->_left = SubR; } else //是右子树 { ppnode->_right = SubR; } SubR->_parent = ppnode; } } void RotateR(Node* parent) //右单旋细节处理和左单旋差不多 { Node* SubL = parent->_left; Node* SubLR = SubL->_right; //这个有可能为空 Node* ppnode = parent->_parent; parent->_left = SubLR; if (SubLR) SubLR->_parent = parent; SubL->_right = parent; parent->_parent = SubL; if (ppnode == nullptr) //旋转的是整颗树 { _root = SubL; SubL->_parent = nullptr; } else //旋转部分 { if (ppnode->_left == parent) //是左子树 { ppnode->_left = SubL; } else //右子树 { ppnode->_right = SubL; } SubL->_parent = ppnode; } }- 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
涉及旋转情况比较复杂，分开讨论：
（1）p为g的左孩子，cur为p的左孩子
（2）p为g的左孩子，cur为p的右孩子
（3）p为g的右孩子，cur为p的右孩子
（4）p为g的右孩子，cur为p的左孩子
整合一下（1、2、3、4）得到下面的调整代码：
//到这里插入新节点的工作完成，下面进行结构调整： while (parent && parent->_col == RED) //父亲为红就调整，调整到根部要结束 { Node* granderfather = parent->_parent; //祖父 if (parent == granderfather->_left) //父亲是祖父的左子树，p为g的左孩子 { Node* uncle = granderfather->_right; if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可 { uncle->_col = parent->_col = BLACK; granderfather->_col = RED; //当前子树可能为部分，继续向上调整 cur = granderfather; parent = cur->_parent; } else //叔叔为空或为黑色 { // g // p u // c if (cur == parent->_left) //当前为父亲的左子树，cur为p的左孩子 { RotateR(granderfather); granderfather->_col = RED; parent->_col = BLACK; } else //当前为父亲的右子树，cur为p的右孩子 { // g // p u // c //左右双旋 RotateL(parent); RotateR(granderfather); granderfather->_col = RED; cur->_col = BLACK; } break; //这两种情况调整完可以结束 } } else //父亲是祖父的右子树，p为g的右孩子 { Node* uncle = granderfather->_left; if (uncle && uncle->_col == RED) //叔叔不空并且为红 { parent->_col = uncle->_col = BLACK; granderfather->_col = RED; //当前可能为部分子树，需要继续上调 cur = granderfather; parent = cur->_parent; } else //叔叔为空或为黑色 { if (cur == parent->_right) //当前为父亲的右，cur为p的右孩子 { // g // u p // c //左旋 RotateL(granderfather); parent->_col = BLACK; granderfather->_col = RED; } else //当前为父亲的左，cur为p的左孩子 { // g // u p // c //右左双旋 RotateR(parent); RotateL(granderfather); cur->_col = BLACK; granderfather->_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
4.一些简单的测试接口
void InOrder() //中序遍历，验证是否为二叉搜索树 { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } // 根节点->当前节点这条路径的黑色节点的数量 bool Check(Node* root, int blacknum, const int refVal) { if (root == nullptr) //到根部看看当前路径黑色节点和标准值是否一致 { //cout << balcknum << endl; if (blacknum != refVal) { cout << "存在黑色节点数量不相等的路径" << endl; return false; } return true; } /检查子比较复杂，可以反过来去检查红节点父是否为黑色 if (root->_col == RED && root->_parent->_col == RED) { cout << "有连续的红色节点" << endl; return false; } if (root->_col == BLACK) { ++blacknum; //为黑节点加一 } return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal); } bool IsBalance() { if (_root == nullptr) return true; if (_root->_col == RED) return false; //参考值，即先算出一条路径的黑色节点数 int refVal = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refVal; } cur = cur->_left; } int blacknum = 0; return Check(_root, blacknum, refVal); }- 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
5.完整代码
#pragma once #include#include using namespace std; //用枚举来定义颜色 enum Color { RED, BLACK }; //这里直接实现key_value模型 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(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) ,_col(RED) //新节点颜色为红色 {} }; template<class K, class V> class RBTree { public: typedef RBTreeNode<K, V> Node; 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 (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 (kv.first > parent->_kv.first) //在右子树 { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; while (parent && parent->_col == RED) //父亲为红就调整，调整到根部要结束 { Node* granderfather = parent->_parent; //祖父 if (parent == granderfather->_left) //父亲是祖父的左子树 { Node* uncle = granderfather->_right; if (uncle && uncle->_col == RED) //叔叔不为空并且叔叔为红，变色即可 { uncle->_col = parent->_col = BLACK; granderfather->_col = RED; //当前子树可能为部分，继续向上调整 cur = granderfather; parent = cur->_parent; } else //叔叔为空或为黑色 { // g // p u // c if (cur == parent->_left) //当前为父亲的左子树 { RotateR(granderfather); granderfather->_col = RED; parent->_col = BLACK; } else //当前为父亲的右子树 { // g // p u // c //左右双旋 RotateL(parent); RotateR(granderfather); granderfather->_col = RED; cur->_col = BLACK; } break; } } else //父亲是祖父的右子树 { Node* uncle = granderfather->_left; if (uncle && uncle->_col == RED) //叔叔不空并且为红 { parent->_col = uncle->_col = BLACK; granderfather->_col = RED; //当前可能为部分子树，需要继续上调 cur = granderfather; parent = cur->_parent; } else //叔叔为空或为黑色 { if (cur == parent->_right) //当前为父亲的右 { // g // u p // c //左旋 RotateL(granderfather); parent->_col = BLACK; granderfather->_col = RED; } else //当前为父亲的左 { // g // u p // c //右左双旋 RotateR(parent); RotateL(granderfather); cur->_col = BLACK; granderfather->_col = RED; } break; } } } _root->_col = BLACK; //保持根部为黑色 return true; } /// // /// / /// 测试代码 void InOrder() //中序遍历，验证是否为二叉搜索树 { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } // 根节点->当前节点这条路径的黑色节点的数量 bool Check(Node* root, int blacknum, const int refVal) { if (root == nullptr) //到根部看看当前路径黑色节点和标准值是否一致 { //cout << balcknum << endl; if (blacknum != refVal) { cout << "存在黑色节点数量不相等的路径" << endl; return false; } return true; } /检查子比较复杂，可以反过来去检查红节点父是否为黑色 if (root->_col == RED && root->_parent->_col == RED) { cout << "有连续的红色节点" << endl; return false; } if (root->_col == BLACK) { ++blacknum; //为黑节点加一 } return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal); } bool IsBalance() { if (_root == nullptr) return true; if (_root->_col == RED) return false; //参考值，即先算出一条路径的黑色节点数 int refVal = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refVal; } cur = cur->_left; } int blacknum = 0; return Check(_root, blacknum, refVal); } int Height() { return _Height(_root); } int _Height(Node* root) //求高度的 { if (root == nullptr) return 0; int leftHeight = _Height(root->_left); int rightHeight = _Height(root->_right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } Node* Find(K key) { return _Find(key, _root); } Node* _Find(K key, Node* root) { if (root == nullptr) return nullptr; if (key > root->_kv.first) //在右子树 { return _Find(key, root->_right); } else if (key < root->_kv.first) //在左子树 { return _Find(key, root->_left); } else //找到了 { return root; } } private: Node* _root = nullptr; void RotateL(Node* parent) //左单旋,rotate->旋转 { Node* SubR = parent->_right; Node* SubRL = SubR->_left; //这个有可能为空 Node* ppnode = parent->_parent; //原来父亲的父亲 parent->_right = SubRL; if (SubRL) SubRL->_parent = parent; SubR->_left = parent; parent->_parent = SubR; if (ppnode == nullptr) //旋转的是整颗树 { _root = SubR; SubR->_parent = nullptr; } else //旋转的是部分 { if (ppnode->_left == parent) //是左子树 { ppnode->_left = SubR; } else //是右子树 { ppnode->_right = SubR; } SubR->_parent = ppnode; } } void RotateR(Node* parent) //右单旋细节处理和左单旋差不多 { Node* SubL = parent->_left; Node* SubLR = SubL->_right; //这个有可能为空 Node* ppnode = parent->_parent; parent->_left = SubLR; if (SubLR) SubLR->_parent = parent; SubL->_right = parent; parent->_parent = SubL; if (ppnode == nullptr) //旋转的是整颗树 { _root = SubL; SubL->_parent = nullptr; } else //旋转部分 { if (ppnode->_left == parent) //是左子树 { ppnode->_left = SubL; } else //右子树 { ppnode->_right = SubL; } SubL->_parent = ppnode; } } }; - 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
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
-
相关阅读:
温故而知新——vue常用语法(五)路由&storage
【Spring】Ioc容器
17、负载均衡
springcloud：1.Eureka详细讲解
scrcpy-win64-v1.24使用
数据结构——红黑树
【mcuclub】数据存储AT24C02
【VMware vSphere】搭建属于自己的 vSphere 实验环境（3）——Windows 系统安装与服务部署
分类预测 | Matlab实现PSO-BiLSTM粒子群算法优化双向长短期记忆神经网络的数据多输入分类预测
vue详细安装教程
- 原文地址：https://blog.csdn.net/2301_76269963/article/details/134450719
