热门标签
热门文章
当前位置: article > 正文
【数据结构】深入理解红黑树：平衡性与高效性的完美结合
作者：菜鸟追梦旅行 | 2024-03-23 13:35:13
赞
踩
【数据结构】深入理解红黑树：平衡性与高效性的完美结合
什么是红黑树？
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
1. 红黑树的性质
- 每个节点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子节点必须是黑色的（没有连续的红色节点）
- 对于每个节点，从该节点到其所有后代叶子节点简单路径上，均包含相同数目的黑色节点（每条路径都包含相同数量的黑色节点）
2. 红黑树节点的定义
enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { public: pair<K, V> _kv; Colour _col; RBTreeNode<K, V>* _pLeft; RBTreeNode<K, V>* _pRight; RBTreeNode<K, V>* _pParent; RBTreeNode(const pair<K, V>& kv) // 构造新增节点 :_pLeft(nullptr) , _pRight(nullptr) , _pParent(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. 红黑树结构
为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：
4. 红黑树的插入操作
在代码实现中，红黑树的插入操作主要包括以下步骤：
- 首先按照二叉查找树的规则将新节点插入到适当的位置，并将其颜色设为红色。
- 根据红黑树的性质，通过旋转和变色操作来维持平衡性。
- 在插入过程中，根据父节点、祖父节点和叔叔节点的颜色情况，进行不同的–旋转和变色操作，确保红黑树的性质得以保持。
// 在RB树中插入值为kv的节点 bool Insert(const pair<K, V>& kv) { // 插入节点 if (_pRoot == nullptr) { _pRoot = new Node(kv); _pRoot->_col = BLACK; return true; } Node* pParent = nullptr; Node* pCur = _pRoot; while (pCur) { pParent = pCur; if (kv.first < pCur->_kv.first) pCur = pCur->_pLeft; // 往左子树查找 else if (kv.first > pCur->_kv.first) pCur = pCur->_pRight; // 往右子树查找 else return false; // 重复值不插入 } // 创建新节点 pCur = new Node(kv); // 红色的 if (kv.first < pParent->_kv.first) pParent->_pLeft = pCur; else pParent->_pRight = pCur; pCur->_pParent = pParent; // 插入节点后，更新 while (pParent && pParent->_col == RED) { Node* pGrandfather = pParent->_pParent; if (pGrandfather == nullptr) break; // 处理根节点 // 找叔叔 if (pParent == pGrandfather->_pLeft) { Node* pUncle = pGrandfather->_pRight; // case1: 叔叔存在且为RED if (pUncle && pUncle->_col == RED) { // 变色 pParent->_col = pUncle->_col = BLACK; pGrandfather->_col = RED; // 继续往上处理 pCur = pGrandfather; pParent = pCur->_pParent; } else { // case2: 叔叔不存在或者存在且为黑 (旋转+变色) if (pCur == pParent->_pLeft) { // g // p u // c RotateR(pGrandfather); pParent->_col = BLACK; pGrandfather->_col = RED; } else { // g // p u // c RotateL(pParent); RotateR(pGrandfather); pCur->_col = BLACK; pGrandfather->_col = RED; } break; } } else { Node* pUncle = pGrandfather->_pLeft; // case1：叔叔存在且为红 if (pUncle && pUncle->_col == RED) { // 变色 pParent->_col = pUncle->_col = BLACK; pGrandfather->_col = RED; // 继续往上处理 pCur = pGrandfather; pParent = pCur->_pParent; } else { // 情况二：叔叔不存在或者存在且为黑 // 旋转+变色 // g // u p // c if (pCur == pParent->_pRight) { RotateL(pGrandfather); pParent->_col = BLACK; pGrandfather->_col = RED; } else { // g // u p // c RotateR(pParent); RotateL(pGrandfather); pCur->_col = BLACK; pGrandfather->_col = RED; } break; } } } _pRoot->_col = BLACK; // 根始终为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
- 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
5. 红黑树的平衡性检查
在插入节点后，需要对红黑树进行平衡性检查，主要包括以下步骤：
- 检查是否存在连续的红色节点，这违反了红黑树的性质。
- 统计从根节点到叶子节点的黑色节点数量，确保每条路径上的黑色节点数相等。
bool Check(Node* pCur, int blackNum, int refBlackNum) { if (pCur == nullptr) { if (refBlackNum != blackNum) { cout << "黑色节点的数量不相等" << endl; return false; } //cout << blackNum << endl; return true; } if (pCur->_col == RED && pCur->_pParent->_col == RED) { cout << pCur->_kv.first << "存在连续的红色节点" << endl; return false; } if (pCur->_col == BLACK) ++blackNum; return Check(pCur->_pLeft, blackNum, refBlackNum) && Check(pCur->_pRight, blackNum, refBlackNum); } bool IsBalance() { if (_pRoot && _pRoot->_col == RED) return false; int refBlackNum = 0; Node* pCur = _pRoot; while (pCur) { if (pCur->_col == BLACK) refBlackNum++; pCur = pCur->_pLeft; } return Check(_pRoot, 0, refBlackNum); }
- 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
6.代码实现和测试
通过代码示例，我们可以清晰地看到红黑树的插入操作以及平衡性检查的实现过程。在测试代码中，我们可以通过输出结果验证红黑树的平衡性。
#include <iostream> using namespace std; enum Colour { RED, BLACK }; template<class K, class V> struct RBTreeNode { public: pair<K, V> _kv; Colour _col; RBTreeNode<K, V>* _pLeft; RBTreeNode<K, V>* _pRight; RBTreeNode<K, V>* _pParent; RBTreeNode(const pair<K, V>& kv) // 构造新增节点 :_pLeft(nullptr) , _pRight(nullptr) , _pParent(nullptr) , _kv(kv) , _col(RED) // 默认为红色 {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: RBTree() : _pRoot(nullptr) {} // 在RB树中插入值为kv的节点 bool Insert(const pair<K, V>& kv) { // 插入节点 if (_pRoot == nullptr) { _pRoot = new Node(kv); _pRoot->_col = BLACK; return true; } Node* pParent = nullptr; Node* pCur = _pRoot; while (pCur) { pParent = pCur; if (kv.first < pCur->_kv.first) pCur = pCur->_pLeft; // 往左子树查找 else if (kv.first > pCur->_kv.first) pCur = pCur->_pRight; // 往右子树查找 else return false; // 重复值不插入 } // 创建新节点 pCur = new Node(kv); // 红色的 if (kv.first < pParent->_kv.first) pParent->_pLeft = pCur; else pParent->_pRight = pCur; pCur->_pParent = pParent; // 插入节点后，更新 while (pParent && pParent->_col == RED) { Node* pGrandfather = pParent->_pParent; if (pGrandfather == nullptr) break; // 处理根节点 // 找叔叔 if (pParent == pGrandfather->_pLeft) { Node* pUncle = pGrandfather->_pRight; // case1: 叔叔存在且为RED if (pUncle && pUncle->_col == RED) { // 变色 pParent->_col = pUncle->_col = BLACK; pGrandfather->_col = RED; // 继续往上处理 pCur = pGrandfather; pParent = pCur->_pParent; } else { // case2: 叔叔不存在或者存在且为黑 (旋转+变色) if (pCur == pParent->_pLeft) { // g // p u // c RotateR(pGrandfather); pParent->_col = BLACK; pGrandfather->_col = RED; } else { // g // p u // c RotateL(pParent); RotateR(pGrandfather); pCur->_col = BLACK; pGrandfather->_col = RED; } break; } } else { Node* pUncle = pGrandfather->_pLeft; // case1：叔叔存在且为红 if (pUncle && pUncle->_col == RED) { // 变色 pParent->_col = pUncle->_col = BLACK; pGrandfather->_col = RED; // 继续往上处理 pCur = pGrandfather; pParent = pCur->_pParent; } else { // 情况二：叔叔不存在或者存在且为黑 // 旋转+变色 // g // u p // c if (pCur == pParent->_pRight) { RotateL(pGrandfather); pParent->_col = BLACK; pGrandfather->_col = RED; } else { // g // u p // c RotateR(pParent); RotateL(pGrandfather); pCur->_col = BLACK; pGrandfather->_col = RED; } break; } } } _pRoot->_col = BLACK; // 根始终为BLACK return true; } void InOrder() { _InOrder(_pRoot); } bool Check(Node* pCur, int blackNum, int refBlackNum) { if (pCur == nullptr) { if (refBlackNum != blackNum) { cout << "黑色节点的数量不相等" << endl; return false; } //cout << blackNum << endl; return true; } if (pCur->_col == RED && pCur->_pParent->_col == RED) { cout << pCur->_kv.first << "存在连续的红色节点" << endl; return false; } if (pCur->_col == BLACK) ++blackNum; return Check(pCur->_pLeft, blackNum, refBlackNum) && Check(pCur->_pRight, blackNum, refBlackNum); } bool IsBalance() { if (_pRoot && _pRoot->_col == RED) return false; int refBlackNum = 0; Node* pCur = _pRoot; while (pCur) { if (pCur->_col == BLACK) refBlackNum++; pCur = pCur->_pLeft; } return Check(_pRoot, 0, refBlackNum); } private: void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_pLeft); cout << root->_kv.first << endl; _InOrder(root->_pRight); } // 右单旋 void RotateR(Node* pParent) { Node* pSubL = pParent->_pLeft; Node* pSubLR = pSubL->_pRight; // 右旋 pParent->_pLeft = pSubLR; if (pSubLR) pSubLR->_pParent = pParent; pSubL->_pRight = pParent; pSubL->_pParent = pParent->_pParent; pParent->_pParent = pSubL; if (pParent == _pRoot) _pRoot = pSubL; else { if (pSubL->_pParent->_pLeft == pParent) pSubL->_pParent->_pLeft = pSubL; else pSubL->_pParent->_pRight = pSubL; } } // 左单旋 void RotateL(Node* pParent) { Node* pSubR = pParent->_pRight; Node* pSubRL = pSubR->_pLeft; // 左旋 pParent->_pRight = pSubRL; if (pSubRL) pSubRL->_pParent = pParent; pSubR->_pLeft = pParent; pSubR->_pParent = pParent->_pParent; pParent->_pParent = pSubR; if (pParent == _pRoot) _pRoot = pSubR; else { if (pSubR->_pParent->_pLeft == pParent) pSubR->_pParent->_pLeft = pSubR; else pSubR->_pParent->_pRight = pSubR; } } Node* _pRoot; }; void TestRBTree1() { int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 23, 2, 0, 19, 234, 63, 1, 90}; RBTree<int, int> t; for (auto e : a) { t.Insert(make_pair(e, e)); // 1、先看是插入谁导致出现的问题 // 2、打条件断点，画出插入前的树 // 3、单步跟踪，对比图一一分析细节原因 cout << e << "->" << t.IsBalance() << endl; } t.InOrder(); cout << t.IsBalance() << endl; }
- 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
7. 红黑树与AVL树的对比
性质对比：
红黑树：
- 红黑树是一种非严格平衡的二叉查找树。
- 通过引入颜色属性和一系列约束条件来保持平衡性，确保最坏情况下的高效性能。
- 插入、删除操作可能会打破平衡，但通过旋转和变色操作能够快速恢复平衡。
AVL树：
- AVL树是一种严格平衡的二叉查找树。
- 通过维护每个节点的平衡因子（左子树高度减去右子树高度的值），保持树的严格平衡。
- 插入、删除操作可能会导致失衡，需要通过旋转操作来恢复平衡。
平衡性：
- 红黑树在平衡性和性能之间取得了一种折衷，相对于AVL树来说，牺牲了严格的平衡性，但在插入、删除等操作上更加高效。
- AVL树追求严格的平衡，因此在插入、删除操作时需要更频繁地进行旋转操作，可能会导致性能略低于红黑树。
应用场景：
- 红黑树适合在需要频繁执行插入、删除操作的场景，例如在数据库系统中作为索引结构。
- AVL树适合在对读操作要求较高、对写操作次数相对较少的场景，例如在文件系统中维护目录结构。
8.红黑树与AVL树的应用
红黑树应用场景：
- 数据库系统中的索引结构，如MySQL中的InnoDB存储引擎使用红黑树来维护索引。
- C++标准库中的map和set等容器也使用红黑树作为底层实现。
AVL树应用场景： - 文件系统中的目录结构，保持文件的有序性和快速查找。
- 高密度存储中的数据结构，如内存中或硬盘中需要快速读取和稳定查询性能的场景
总结
本文详细介绍了红黑树的定义、性质、节点结构、插入操作、平衡性检查等内容，并给出了红黑树的代码实现和测试示例。通过对红黑树的插入操作和平衡性检查的实现过程进行分析，展示了红黑树在维护平衡性和高效性方面的特点。此外，还对红黑树与AVL树进行了对比，说明了它们在平衡性、性能和应用场景上的差异。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/295493
推荐阅读
相关标签
