【C++】红黑树（上）https://developer.aliyun.com/article/1515242?spm=a2c6h.13148508.setting.27.11104f0e63xoTy
首先记录 cur 的父亲 p 和祖父 g 的位置，然后判断父亲 p 的位置：
（1）如果父亲 p 是祖父 g 的左孩子
说明叔叔 u 是祖父 g 的右孩子，先判断叔叔的状态：
- 如果叔叔 u 存在且为红，说明是情况 1，直接先变色处理，然后再往上调整。
1、先调整颜色：父亲 p 和叔叔 u 变黑，祖父 g 变红。
2、再往上调整：原先祖父 g 当成新的 cur，判断新 cur 的父亲 p：
- 若父亲 p 不存在，说明调整到头了，停止调整，然后将根节点变黑。
- 若父亲 p 存在且为黑，没有破坏性质，停止调整。
- 若父亲 p 存在且为红，继续调整，并判断是否出现了情况 2 / 3，要一直调整到根节点或者父亲 p 存在且为黑时，才停止调整。
- 如果叔叔 u 不存在 / 叔叔 u 存在且为黑，说明是情况 2 / 3，先判断 cur 的位置：
1、如果 cur 是父亲 p 的左孩子（此时 cur、p、g 是一条直线，说明是情况 2）
- 进行右单旋 + 变色处理（父亲 p 变黑，祖父 g 变红）
2、如果 cur 是父亲 p 的右孩子（此时 cur、p、g 是一条折线，说明是情况 3）
- 进行左右双旋 + 变色处理（cur 变黑，祖父 g 变红）
3、上述情况 2 / 3 处理完成后，当前子树的根节点为黑 (p / cur)，没有连续红节点了，则停止调整。
（2）如果父亲 p 是祖父 g 的右孩子
说明叔叔 u 是祖父 g 的左孩子，先判断叔叔的状态：
- 如果叔叔 u 存在且为红，说明是情况 1，先变色处理（p 和 u 变黑，g 变红），然后再往上调整。
去判断新的父亲 p 的状态，检测新的子树是否平衡，情况 1 处理方式类似于上面，此处不再详细介绍。
- 如果叔叔 u 不存在或者叔叔 u 存在且为黑，说明是情况 2 / 3，先判断 cur 的位置：
1、如果 cur 是父亲 p 的右孩子（此时 cur、p、g是一条直线，说明是情况二）
- 进行左单旋 + 变色处理（父亲 p 变黑，祖父 g 变红）
2、如果 cur 是父亲 p 的左孩子（此时 cur、p、g是一条折线，说明是情况三）
- 进行右左单旋 + 变色处理（cur 变黑，祖父 g 变红）
3、上述情况 2 / 3 处理完成后，当前子树的根节点为黑 (p / cur)，没有连续红节点了，则停止调整。
注意：上面几个停止调整，是循环的出口，否则就要一直调整到根节点或者父亲 p 存在且为黑时。
// 插入节点 bool Insert(const pair<K, V>& kv) { // 1、查找到适合插入的空位置 // 判断树是否为空 if (_root == nullptr) { _root = new Node(kv); // 插入新节点 _root->_col = BLACK; // 根节点为黑色 return true; } // 记录当前节点和它的父节点 Node* parent = nullptr; Node* cur = _root; while (cur) // 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; // 不允许数据冗余，返回false } } // 插入新节点，颜色为红色（可能会破坏性质3，产生两个连续红色节点） cur = new Node(kv); cur->_col = RED; if (parent->_kv.first < kv.first) // 判断新节点是其父亲的左孩子还是右孩子 { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent; // 更新cur的双亲指针 // 2、检测红黑树性质有没有被破坏，并控制树的平衡 // 如果cur的父亲p存在且为红，则树不平衡，就需要一直往上调整 while (parent && parent->_col == RED) { Node* grandfater = parent->_parent; // 记录cur的祖父grandfather assert(grandfater); assert(grandfater->_col == BLACK); // 关键看叔叔 // 1、如果parent是grandfather的左孩子 if (parent == grandfater->_left) { Node* uncle = grandfather->_right; // uncle是grandfather的右孩子 // 情况(1)：uncle存在且为红，变色+继续往上处理 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; // parent和uncle变黑 grandfather->_col = RED; // grandfather变红 // 继续往上处理 cur = grandfater; parent = cur->_parent; } // 情况(2)+(3)：uncle不存在+存在且为黑 else { // 情况(2)：右单旋+变色 // g // p u // c if (cur == parent->_left) // 如果cur是parent的左孩子，说明是情况2 { // 单旋 + 调整颜色 RotateR(grandfater); // 右单旋 parent->_col = BLACK; // parent变黑 grandfater->_col = RED; // grandfather变红 } else { // 情况3：左右单旋+变色 // g // p u // c // 双旋 + 调整颜色 RotateL(parent); // 左单旋 RotateR(grandfater); // 右单旋 cur->_col = BLACK; // cur变黑 grandfater->_col = RED; // grandfather变红 } break; // 情况2或3处理完成后，当前子树的根节点为黑，没有连续红节点了，则停止调整 } } // 2、如果parent是grandfather的右孩子 else // (parent == grandfater->_right) { Node* uncle = grandfater->_left; // uncle是grandfather的左孩子 // (1) uncle存在且为红，说明是情况1 if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; // parent和uncle变黑 grandfater->_col = RED; // grandfather变红 // 继续往上处理 cur = grandfater; parent = cur->_parent; } // (2) uncle不存在/存在且为黑，说明是情况2或3 else { // 情况2：左单旋+变色 // g // u p // c // 如果cur是parent的右孩子，说明是情况2 if (cur == parent->_right) { // 单旋 + 调整颜色 RotateL(grandfater); // 左单旋 parent->_col = BLACK; // parent变黑 grandfater->_col = RED; // grandfather变红 } // 如果cur是parent的左孩子，说明是情况3 else { // 情况3：右左单旋+变色 // g // u p // c // 双旋 + 调整颜色 RotateR(parent); // 右单旋 RotateL(grandfater); // 左单旋 cur->_col = BLACK; // cur变黑 grandfater->_col = RED; // grandfather变红 } break; // 情况2或3处理完成后，当前子树的根节点为黑，没有连续红节点了，则停止调整 } } } _root->_col = BLACK; // 根节点变黑 return true; } // 左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; // 记录parent的右孩子 Node* subRL = subR->_left; // 记录parent右孩子的左孩子 parent->_right = subRL; if (subRL) { subRL->_parent = parent; } Node* ppNode = parent->_parent; // 先记录下parent的父节点 subR->_left = parent; parent->_parent = subR; // root为空，说明parent原先是根节点 if (_root == parent) { _root = subR; // subR为新的根节点 subR->_parent = nullptr; // subR的双亲指针指向空 } // root不为空，说明parent原先是一个普通子树 else { // 判断parent原先是父亲ppNode的左孩子还是右孩子 if (ppNode->_left == parent) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; // subR的双亲指针指向ppNode } } // 右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; // 记录parent的左孩子 Node* subLR = subL->_right; // 记录parent左孩子的右孩子 parent->_left = subLR; if (subLR) { subLR->_parent = parent; } Node* ppNode = parent->_parent; // 先记录下parent的父节点 subL->_right = parent; parent->_parent = subL; // root为空，说明parent原先是根节点 if (_root == parent) { _root = subL; // subL为新的根节点 subL->_parent = nullptr; // subL的双亲指向指向空 } // root不为空，说明parent原先是一个普通子树 else { // 判断parent原先是ppNode的左孩子还是右孩子 if (ppNode->_left == parent) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; // subL的双亲指针指向ppNode } }
动态效果演示：
- 以升序插入构建红黑树。
- 以降序插入构建红黑树。
- 随机插入构建红黑树
6、红黑树的验证
红黑树的检测分为两步：
- 检测其是否满足二叉搜索树（中序遍历是否为有序序列）。
- 检测其是否满足红黑树的性质。
- 根节点是否为黑色。
- 是否存在连续红节点。
- 统计每条路径上的黑节点数是否相等。
（1）检测是否存在连续红节点
// 检测红黑树是否有连续红节点 bool CheckRedRed(Node* root) { if (root == nullptr) return true; // 思路1：如果当前节点为红色，检测它的孩子是否为红色，但孩子可能为空，每次还得判断孩子是否为空，太麻烦了 // 思路2：如果当前节点为红色，我们去检测它的父亲是否为红色。因为根节点没有父亲，且根节点为黑色，是不会被判断的 if (root->_col == RED && root->_parent->_col == RED) { cout << "存在连续的红色节点" << endl; return false; } // 继续判断当前节点的左右孩子 return CheckRedRed(root->_left) && CheckRedRed(root->_right); }
（2）检测每条路径上的黑节点数是否相等
首先计算出红黑树其中一条路径的黑节点数，作为一个 baseValue 基准值(参考值)，然后再求出红黑树每条路径的黑节点数，与基准值比较，如果不相等，说明违反性质了。
- blackNum：表示从根节点到当前节点的黑节点数。
- benchmark：基准值（最左侧路径的黑节点数）。
// 计算红黑树最左侧这条路径的黑色节点数量基准值(参考值) int CountBaseValue() { int benchmark = 0; Node* cur = _root; while (cur) // 遇到NIL时，统计结束 { if (cur->_col == BLACK) benchmark++; cur = cur->_left; } return benchmark; } bool PrevCheck(Node* root, int blackNum, int& benchmark) { // 当前节点为空，说明遇到了NIL，判断该路径的黑节点数是否等于基准值 if (root == nullptr) { if (benchmark == 0) { benchmark = blackNum; return true; } if (blackNum != benchmark) { cout << "某条黑色节点的数量不相等" << endl; return false; } else { return true; } } // 当前节点为黑色，则从根节点到当前节点的黑节点数加1 if (root->_col == BLACK) { blackNum++; } if (root->_col == RED && root->_parent->_col == RED) { cout << "存在连续的红色节点" << endl; return false; } return PrevCheck(root->_left, blackNum, benchmark) && PrevCheck(root->_right, blackNum, benchmark); }
【注意】
这里计算每条路径的黑节点数 blackNum 时，使用的是传值，因为这样就可以在递归的过程中计算到每条路径的黑节点数，因为每个函数栈帧中的 blackNum 变量都是独立存在的。
下一层的 blackNum 是上一层的拷贝，下一层中++，不会影响上一层。
比如在黑节点 1 中对 blackNum++，变成 2，但红节点 8 中的 blackNum 值还是1，所以就不会影响到计算右孩子即黑节点 11 所在路径的黑节点数。
补：求一棵树的叶子节点数和总的节点数，就可以用引用。
// 检测红黑树是否平衡 bool IsBalance() { if (_root == nullptr) return true; // 1、检测红黑树的根节点是否为红色 if (_root->_col == RED) { cout << "根节点不是黑色" << endl; return false; } // 2、CheckRedRed：检测红黑树是否有连续红节点 // 3、CheckBlackNums：检测红黑树每条路径黑节点数是否相等 return CheckRedRed(_root) && PrevCheck(_root, 0, CountBaseValue()); }
7、红黑树的删除
红黑树的删除这里不做讲解，感兴趣可以参考：《算法导论》或者《STL源码剖析》。
8、 红黑树与AVL树的比较
红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
9、红黑树的应用
- C++ STL库 —— map/set、mutil_map/mutil_set。
- Java 库。
- linux内核。
- 其他一些库。
