-
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" #includeint 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#include 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
-
相关阅读:
React报错之You provided a `checked` prop to a form field
电脑技巧：低配置的旧电脑也可以使用Win11系统了
el-tree业务
VMware ESXi 8.0U2c macOS Unlocker & OEM BIOS ConnectX-3 网卡定制版 (集成驱动版)
sqlalchemy_No2_创建数据库引擎
扫描电子显微镜（SEM）低真空技术改造以提升观测能力的解决方案
java根据经纬度转地址或者根据地址转经纬度
设计模式——装饰器模式（Decorator Pattern）+ Spring相关源码
使用Spring进行文件的上传和下载
巧用 VScode 网页版 IDE 搭建个人笔记知识库!
- 原文地址：https://blog.csdn.net/qq_51492202/article/details/126179804
