??博客代码已上传至gitee：https://gitee.com/byte-binxin/cpp-class-code
????概念和性质
红黑树的概念： 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。它是通过控制节点颜色的方式来控制这棵树的相对平衡，保证了没有一条路径会比其它路径长出两倍。
红黑树的性质：
- 结点是红色或黑色。
- 根结点是黑色。
- 所有叶子都是黑色。（叶子是空结点）
- 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
- 从任一节结点到其每个叶子的所有路径都包含相同数目的黑色结点
上面的五个性质还可以用更通俗的语言描述为三句话：
- 根节点是黑色的
- 没有连续的红节点
- 每条路径的黑节点数目相同（每条路径指的是从根节点到黑色的空节点）
思考： 为什么红黑树中最长路径的长度不会超过最短路径节点个数的两倍？
最长路径： 该条路径上节点分布是一红一黑
最短路径： 该条路径上节点分布是全黑
假设每条路径黑色节点数为N，则最长路径为2N，最短路径为N，所以这样就推出红黑树中最长路径的长度不会超过最短路径节点个数的两倍。
????红黑树的实现
????红黑树节点定义
这里也是一个三叉链，其中每个节点包含颜色的元素在里面：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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 _color;
RBTreeNode(const pair<K, V>& kv, Color color = RED) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _color(color) {} }; |
????红黑树结构定义
里面只包含一个根节点的成员变量，和前面两棵树的结构定义没有什么大的区别，区别在于节点的定义：
|
1 2 3 4 5 6 7 8 |
template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: private: Node* _root = nullptr; }; |
????红黑树的插入
????方法概述
第一步： 我们先按照二叉搜索树树插入节点的方式，插入节点
第二步： 为了不破坏红黑树的规则，我们插入节点后要对红黑树进行相应的调整
思考： 我们插入节点应该默认插入红色节点好还是黑色节点好呢？ 答案是红色节点。为什么呢？我们要考虑哪种方式对红黑树的破坏性更大一点。如果是黑色，此时黑导致该条路径比其它路径上黑色节点数都多一个，这样下来调整红黑树的步骤代价似乎会有点大；如果是红色，不会破坏规则5，只是破坏规则4，可能会出现连续的红色节点，这样我们只需要调整该节点及其附近节点的颜色即可，代价没有前一种方式大，所以我们选择第二种方式。
????调整节点颜色
第一种情况： 如果插入节点的父亲是黑色节点，那么可以直接结束，不需要继续调整了
第二种情况： 如果插入节点为的父亲为红色节点，就需要进行相应的调整 下面讨论父亲节点是祖父节点的左孩子的几种情形（是右孩子的情形和这个类型，大家可以自己推演一下，这里我们把父亲节点叫做p(parent)，祖父叫g(grandfather)，叔叔节点叫u(uncle)）：
情况1： p为红色（g肯定是存在的且为黑），u存在且为红
操作： 把p和u改成黑，g改成红，如果g为根节点就把g的颜色变成黑然后结束，如果g不为根节点，且g的父亲为黑色也节数，为红色就需要迭代向上调整，判断此时处于何种情况 具像图：
如果g的父亲为红，就迭代向上调整：cur = grandfather,grandfather = grandfather->parent
抽象图：抽象图中cur可能是新插入的节点，也可能是迭代调整上来的节点，这里g这棵子树每条路径黑色节点数是相同的，且调整后g这棵子树的每条路径黑色数相同且和之前一样。cur是parent的左孩子和右孩子是一样的，因为这里都是对颜色进行控制，和方向无关。
情况2： p为红色（g肯定是存在的且为黑），u不存在
操作： cur为parent的左孩子时，对g进行右单旋，然后将p的颜色改黑，g的颜色改红；cur为parent的右孩子时，先对p进行左单旋，然后对g进行右单旋，然后将cur的颜色改黑，g的颜色改红 具象图：此时cur一定为新增节点，因为g的右子树没有黑节点，所以cur的下面也不可能有黑节点 cur为parent的左孩子时 一条直线，此时进行右单旋
cur为parent的左孩子时 一条折线，此时进行左右双旋
上面的第二种情况可以先进行左单旋，然后交换cur和p，把折线变为直线，最后都执行直线的情况。
情况3： p为红色（g肯定是存在的且为黑），u存在且为黑
操作： 如果cur为parent的左孩子，对g进行右单旋，然后将p的颜色改为黑，g的颜色改为红；如果cur为parent的右孩子，先对p进行左单旋，对g进行右单旋，然后将cur的颜色改为黑，g的颜色改为红
解释： 假设此时a和b中黑色节点数为a，c的黑色节点数也一定为a，d和e的黑色节点数就是a-1，调整后cur和g的抽象图的黑色节点都是a，整体相等。 抽象图：此时cur一定为调整上来的节点，因为如果是新增节点的话，那么原来g这棵子树左右黑色节点数目不等，所以cur一定是调整上来的节点。 cur为parent的左孩子 一条直线，进行右单旋即可
cur为parent的右孩子 一条折线，此时进行左右双旋
和情况2一样，上面的第二种情况可以先进行左单旋，然后交换cur和p，把折线变为直线，最后都执行直线的情况。
总结： 上面就是p是g的左孩子的所有情形，为g的右孩子是与这个类似。还有注意的是根节点最后一定要改为黑色。
????插入代码实现
旋转代码如下： 这里就是上一篇博客的旋转代码，具体如下
|
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 |
// 左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left;
// parent的右指向subR的左 parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* ppNode = parent->_parent; parent->_parent = subR; subR->_left = parent;
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;
// parent的左指向subL的右 parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* ppNode = parent->_parent; parent->_parent = subL; subL->_right = parent;
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 |
pair<Node*, bool> Insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv, BLACK);// 根节点默认给黑 return make_pair(_root, true); }
Node* cur = _root; Node* parent = nullptr;
while (cur) { parent = cur; if (kv.first < cur->_kv.first) cur = cur->_left; else if (kv.first > cur->_kv.first) cur = cur->_right; else return make_pair(nullptr, false); } // 节点默认给红节点，带来的影响更小 // 给黑节点的话会影响 每条路径的黑节点相同这条规则 cur = new Node(kv); if (cur->_kv.first < parent->_kv.first) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; }
// 调整颜色 // 情况一：p是红，g是黑，u存在且为红 // 调整后的几种情况： // 1.如果g为根节点，把g的颜色改成黑，结束； // 2.如果g不为根节点， // a.g的父节点为黑，结束； // b.g的父节点为红，迭代向上调整,继续判断是哪种情况（一和三） // cur = grandfather; // father = cur->father; // 这里不管cur是在p的左边还是右边，都是一样的，关心的是颜色而不是位置 // 情况二：p是红，g是黑，u不存在/u为黑 cur p g 三个是一条直线 // 调整方法（左边为例）：1.右单旋 2.把p改成黑，g改成红 // a. u不存在时，cur必定是新增节点 // b. u存在时，cur必定是更新上来的节点 // 情况三：p是红，g是黑，u不存在/u为黑 cur p g 三个是一条折线 // 调整方法（左边为例）：1.p左单旋 2.g右单旋 3.把cur改成黑，g改成红 // a. u不存在时，cur必定是新增节点 // b. u存在时，cur必定是更新上来的节点
while (parent && parent->_color == RED) { Node* grandfather = parent->_parent; // 左边 if (grandfather->_left == parent) { // 红黑色的条件关键看叔叔 Node* uncle = grandfather->_right; // u存在且为红 if (uncle && uncle->_color == RED) { // 调整 p和u改成黑，g改成红 parent->_color = uncle->_color = BLACK; grandfather->_color = RED;
// 迭代 向上调整 cur = grandfather; parent = cur->_parent; } else// u存在为黑/u不存在 { // 折线用一个左单旋处理 1.p左单旋 2.g右单旋 3.把cur改成黑，g改成红 cur p g 三个是一条折线 if (cur == parent->_right) { RotateL(parent); swap(parent, cur); } // 直线 cur p g 把p改成黑，g改成红 // 右单旋 有可能是第三种情况 RotateR(grandfather);
parent->_color = BLACK; grandfather->_color = RED; } } // uncle在左边 else { Node* uncle = grandfather->_left; if (uncle && uncle->_color == RED) { parent->_color = uncle->_color = BLACK; grandfather->_color = RED;
// 迭代 向上调整 cur = grandfather; parent = cur->_parent; } else { // 折线用一个右单旋处理 g p cur g变红p边黑 if (cur == parent->_left) { RotateR(parent); swap(parent, cur); }
// 直线 g p cur 把p改成黑，g改成红 // 左单旋 有可能是第三种情况 RotateL(grandfather);
parent->_color = BLACK; grandfather->_color = RED; } } }
_root->_color = BLACK; return Find(kv.first); } |
????红黑树的删除
????方法概述
第一步： 先按照二叉搜索树删除节点的方式找到要删除节点（也可能是替代节点）
第二步： 然后为了不破坏红黑树的几条规则，要对节点的颜色进行相应地调整
????调整颜色
第一种情况： 删除节点（也可能是替代节点）（之后都叫delNode），如果该节点为红色，则直接删除退出即可，delNode没找到也可以直接退出
第二种情况： delNode为黑色（最多只有一个孩子且为红色，因为替代节点最多只有一个孩子），delNode有一个孩子时，删除delNode节点，然后把孩子节点的颜色改成黑色，也可直接结束
第三种情况： delNode为黑色，且没有孩子时，有下面几种情况（兄弟节点叫b(brother)，父亲节点叫p(parent)）（下面是cur是parent的左孩子的情形，右孩子的情形和它类似，不介绍）：
情况1： p为黑，b为红，两个孩子存在且一定为黑
操作： 对p进行左单旋，然后将p的颜色改成红，b的颜色改成黑
分析： 调整之前抽象三角形的黑色节点都是a，因为cur下面有一个节点要被删除，所以cur下面少了一个黑色节点，也就是p的左边少了一个黑色节点，调整后b两边的黑色节点数不变，cur下面黑色节点数还是少了一个，但是它的兄弟是黑色节点，后面可以通过对cur进行检索，使用其它情况解决这个问题。
抽象图：
情况2： p为红，b为黑，b的两个孩子存在且一定为黑
操作： 把p的颜色改成黑，b的颜色改成红
分析： 调整前，p左边少了一个黑色的节点，调整后，p的左边补上了一个黑色节点，且p的右边的黑色节点数不变，这里可以结束
抽象图：
情况3： p为黑色，且b为黑色，b的两个孩子为黑
操作： 把b的颜色改为红
分析： 调整之前，p左边是缺少一个黑色节点的，调整后，两边黑色节点数相同，但是此时p的右边也少了一个黑色节点，此时p的父亲g，g的右边是比左边多一个黑色节点的，所以需要迭代向上调整，把cur变成p，继续对cur进行检索
抽象图：
情况4： p为任意颜色，b的颜色为黑，b的右孩子为红色
操作： 对p进行左单旋，然后交换p和b的颜色，并把b的颜色改成黑
分析： 调整前，a和b的黑色节点数都是x，c,d,e的黑色节点个数为x+1，也就是p的左边少了一个黑色的节点，调整后，p两边的黑色节点都是x+1，b两边的黑色节点都是x+2，整体都调整好了，所以这里可以结束
抽象图：
情况5： p为任意颜色，b的颜色为黑，b的左孩子为红色
操作： 先对b进行右单旋，然后把b改红，bL改黑，然后对p进行左单旋，然后交换p和b的颜色，并把b的颜色改成黑（情况4）
分析： 和情况四其实是一样的，情况4的b和bR是直线，这里是折线，要通过右单旋变成直线，然后就转为情况4
抽象图：
总结： 删除就是以上几种情况，一般是左边少一个黑色节点，就靠右边补一个，结束，或者右边减少一个，然后两边整体少一个，对父亲节点进行检索。
????删除代码实现
代码实现如下：
|
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 |
bool Erase(const K& key) { // 如果树为空，删除失败 if (_root == nullptr) return false;
Node* parent = nullptr; Node* cur = _root; Node* delNode = nullptr; Node* delNodeParent = nullptr; while (cur) { // 小于往左边走 if (key < cur->_kv.first) { parent = cur; cur = cur->_left; } else if (key > cur->_kv.first) { parent = cur; cur = cur->_right; } else { // 找到了，开始删除 // 1.左右子树都为空 直接删除 可以归类为左为空 // 2.左右子树只有一边为空 左为空，父亲指向我的右，右为空，父亲指向我的左 // 3.左右子树都不为空 取左子树最大的节点或右子树最小的节点和要删除的节点交换，然后再删除
if (cur->_left == nullptr) { // 要删除节点为根节点时，直接把右子树的根节点赋值给——root // 根节点的话会导致parent为nullptr if (_root == cur) { _root = _root->_right; if (_root) { _root->_parent = nullptr; _root->_color = BLACK; } return true; } else { delNode = cur; delNodeParent = parent; } } else if (cur->_right == nullptr) { if (_root == cur) { _root = _root->_left; if (_root) { _root->_parent = nullptr; _root->_color = BLACK; } return true; } else { delNode = cur; delNodeParent = parent; } } else { // 找右子树中最小的节点 Node* rightMinParent = cur; Node* rightMin = cur->_right;// 去右子树找 while (rightMin->_left) { rightMinParent = rightMin; rightMin = rightMin->_left; } //swap(cur->_key, rightMin->_key); // 替代删除 cur->_kv = rightMin->_kv;
delNode = rightMin; delNodeParent = rightMinParent; } break; } } // 没找到 if (cur == nullptr) return false; // 1.替代节点为红，直接删除（看上面） // 2.替代节点为黑（只能有一个孩子或两个孩子） // i)替代节点有一个孩子不为空（该孩子一定为红）,把孩子的颜色改成黑 // ii)替代节点的两个孩子都为空 cur = delNode; parent = delNodeParent; if (cur->_color == BLACK) { if (cur->_left)// 左孩子不为空 { cur->_left->_color = BLACK; } else if (cur->_right) { cur->_right->_color = BLACK; } else// 替代节点的两个孩子都为空 { while (parent) { // cur是parent的左 if (cur == parent->_left) { Node* brother = parent->_right; // p为黑 if (parent->_color == BLACK) { Node* bL = brother->_left; Node* bR = brother->_right; // SL和SR一定存在且为黑 if (brother->_color == RED)// b为红，SL和SR都为黑 b的颜色改黑，p的颜色改红 情况a { RotateL(parent); brother->_color = BLACK; parent->_color = RED;
// 没有结束，还要对cur进行检索 } else if(bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b为黑，孩子存在 { // 且孩子也为黑 把brother改成红色，迭代 GP比GU小1 情况b brother->_color = RED; cur = parent; parent = parent->_parent; } // bL存在为红，bR不存在或bR为黑 情况e 右旋后变色转为情况d else if (bL && bL->_color == RED && (!bR || (bR && bR->_color == BLACK))) { RotateR(brother); bL->_color = BLACK; brother->_color = RED; } else if (bR && bR->_color == RED) // 右孩子为红，进行一个左旋，然后把右孩子的颜色改成黑色 情况d { RotateL(parent); swap(brother->_color, parent->_color); bR->_color = BLACK; break; } else { // cur p b 都是黑，且b无孩子，迭代更新 // parent是红就结束 brother->_color = RED; cur = parent; parent = parent->_parent; } } // p为红 b一定为黑 else { Node* bL = brother->_left; Node* bR = brother->_right; if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b的孩子全为黑 情况c p变黑，b变红 结束 { brother->_color = RED; parent->_color = BLACK; break; } // bL存在为红，bR不存在或bR为黑 情况e 右旋后变色转为情况d else if (bL && bL->_color == RED && (!bR || (bR && bR->_color == BLACK))) { RotateR(brother); bL->_color = BLACK; brother->_color = RED; } else if (bR && bR->_color == RED) // 右孩子为红，进行一个左旋，然后把右孩子的颜色改成黑色 情况d { RotateL(parent); //swap(brother->_color, parent->_color); brother->_color = parent->_color; parent->_color = BLACK; bR->_color = BLACK; break; } else// cur 为黑，p为红，b为黑 调整颜色，结束 { parent->_color = BLACK; brother->_color = RED; break; } } } else { Node* brother = parent->_left; // p为黑 if (parent->_color == BLACK) { Node* bL = brother->_left; Node* bR = brother->_right; // SL和SR一定存在且为黑 if (brother->_color == RED)// b为红，SL和SR都为黑 b的颜色改黑，p的颜色改红 情况a { RotateR(parent); brother->_color = BLACK; parent->_color = RED;
// 没有结束，还要对cur进行检索 } else if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b为黑，孩子存在 { // 且孩子也为黑 把brother改成红色，迭代 GP比GU小1 情况b brother->_color = RED; cur = parent; parent = parent->_parent; } // 右孩子存在且为红，但左孩子不存在或为黑 情况e 右旋后变色转为情况d else if (bR && bR->_color == RED && (!bL || (bL && bL->_color == BLACK))) { RotateL(brother); brother->_color = RED; bR->_color = BLACK; } else if (bL && bL->_color == RED) // 左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色 情况d { RotateR(parent); swap(brother->_color, parent->_color); bL->_color = BLACK; break; } else { // cur p b 都是黑，且b无孩子，迭代更新 // if (parent == _root) // p是根节点，把b变红 否则迭代 brother->_color = RED; cur = parent; parent = parent->_parent; } } // p为红 b一定为黑 else { Node* bL = brother->_left; Node* bR = brother->_right; if (bL && bR && bL->_color == BLACK && bR->_color == BLACK)// b的孩子全为黑 情况c p变黑，b变红 结束 { brother->_color = RED; parent->_color = BLACK; break; } // 右孩子存在且为红，但左孩子不存在或为黑 情况e 右旋后变色转为情况d else if (bR && bR->_color == RED && (!bL || (bL && bL->_color == BLACK))) { RotateL(brother); brother->_color = RED; bR->_color = BLACK; } else if (bL && bL->_color == RED) // 左孩子为红，进行一个右旋，然后把左孩子的颜色改成黑色 情况d { RotateR(parent); // swap(brother->_color, parent->_color); brother->_color = parent->_color; parent->_color = BLACK; bL->_color = BLACK; break; } else// cur 为黑，p为红，b为黑 调整颜色，结束 { parent->_color = BLACK; brother->_color = RED; break; } } } }
} } delNodeParent = delNode->_parent; // 删除 if (delNode->_left == nullptr) { if (delNodeParent->_left == delNode) delNodeParent->_left = delNode->_right; else delNodeParent->_right = delNode->_right; if (delNode->_right)// 右不为空，就让右节点的父指针指向delNodeParent delNode->_right->_parent = delNodeParent; } else { if (delNodeParent->_left == delNode) delNodeParent->_left = delNode->_left; else delNodeParent->_right = delNode->_left; if (delNode->_left)// 右不为空，就让右节点的父指针指向delNodeParent delNode->_left->_parent = delNodeParent; }
delete delNode; delNode = nullptr; 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 |
bool Find(const K& key) { if (_root == nullptr) return false;
Node* cur = _root; while (cur) { // 小于往左走 if (key < cur->_kv.first) { cur = cur->_left; } // 大于往右走 else if (key > cur->_kv.first) { cur = cur->_right; } else { // 找到了 return true; } }
return false; } |
????红黑树的验证
这里通过递归计算出每条路径的节点个数来进行比较，同时验证其他的性质是否符合，从而验证是否红黑树：
|
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 |
bool IsValidRBTree() { // 空树也是红黑树 if (_root == nullptr) return true; // 判断根节点的颜色是否为黑色 if (_root->_color != BLACK) { cout << "违反红黑树的根节点为黑色的规则" << endl; return false; }
// 计算出任意一条路径的黑色节点个数 size_t blackCount = 0; Node* cur = _root; while (cur) { if (cur->_color == BLACK) ++blackCount; cur = cur->_left; }
// 检测每条路径黑节点个数是否相同 第二个参数记录路径中黑节点的个数 return _IsValidRBTree(_root, 0, blackCount); } bool _IsValidRBTree(Node* root, size_t k, size_t blackCount) { // 走到空就判断该条路径的黑节点是否等于blackCount if (root == nullptr) { if (k != blackCount) { cout << "违反每条路径黑节点个数相同的规则" << endl; return false; } return true; }
if (root->_color == BLACK) ++k;
// 判断是否出现了连续两个红色节点 Node* parent = root->_parent; if (parent && root->_color == RED && parent->_color == RED) { cout << "违反了不能出现连续两个红色节点的规则" << endl; return false; }
return _IsValidRBTree(root->_left, k, blackCount) && _IsValidRBTree(root->_right, k, blackCount); } |
实例演示：
|
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 |
void TestRBTree() { //srand((size_t)time(nullptr)); RBTree<int, int> rbt; // int a[] = { 1,2,3,4,5,6,7,8,9,10,5,7,8,11,12,13 }; // int a[] = { 16,3,7,11,9,26,18,14,15 }; // int a[] = { 4,2,6,1,3,5,15,7,16,14 }; // int a[] = { 10,9,8,7,6,5,4,3,2,1 }; vector<int> a; for (size_t i = 0; i < 13; ++i) { // a.push_back(rand()); a.push_back(i); } //int a[] = { 4,2,6,7,3,5 }; /*vector<int> v; v.reserve(100000);
for (size_t i = 1; i <= v.capacity(); ++i) { v.push_back(i); }*/ for (auto e : a) { int begin = clock(); rbt.Insert(make_pair(e, e)); int end = clock(); cout << "插入数据 " << e << " 后：" << "树的高度：" << rbt.Height() << " 是否为红黑树：" << rbt.IsValidRBTree(); cout << " 用时：" << end - begin << "ms" << endl; } cout << "-------------------------------------------------------" << endl; for (auto e : a) { int begin = clock(); rbt.Erase(e); int end = clock(); cout << "删除数据 " << e << " 后：" << "树的高度：" << rbt.Height() << " 是否为红黑树：" << rbt.IsValidRBTree(); cout << " 用时：" << end - begin << "ms" << endl; } // cout << rbt.IsValidRBTree() << endl; // rbt.InOrder(); } |
代码运行结果如下：
????AVL树和红黑树的比较
| AVL树 | 红黑树 | |
|---|---|---|
| 如何控制平衡 | 通过条件平衡因子，子树左右高度差不超过1 | 用过颜色控制，使得最长路径不超出最短路径的长度的两倍 |
| 增删查改的时间复杂度 | 可以稳定在O(logN) | 基本是O(logN)，极端情况下是O(log2N) |
总结： AVL树是严格意义上的平衡，红黑树是相对的平衡，两者都很高效，但后者用的更多，因为它旋转更是，实现相对简单，付出的代价少一点。
????总结
二叉搜索树的内容就介绍到这，接下来我会给大家介绍map和set两个容器，它们的底层就是红黑树，我会用红黑树给大家模拟实现它们。喜欢的话，欢迎点赞支持和关注~
