一、认识红黑树
1.1 什么是红黑树？
红黑树是一种二叉搜索树，与普通搜索树不同的是，在每个节点上增加一个“颜色”变量 —— RED / BLACK 。
通过对各个节点颜色的限制，确保从 根 到
NIL，没有一条路径会比其他路径长出两倍。（NIL ：表示叶子节点的空指针，统一设置为 BLACK ）
1.2 红黑树的性质
- 根节点一定是黑色
- 不能出现两个连续的红色节点
- 对于同一高度而言，从根到该高度任一节点的简单路径上的黑色节点的数量相同
1.3 红黑树节点定义
二、红黑树
2.1 红黑树定义
template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; private: Node* _root; };
2.2 插入
红黑树的插入是我们学习红黑树过程最重要的知识之一，它主要分为两部分：平衡二叉树的插入 和 旋转 —— 调整树形结构。
插入部分与普通搜索树没有本质区别，这里不做过多介绍。
声明一下：代码中的 grandfather 和 图中的 grandparent 为同一东西，笔者在基本结束本篇时发现这里差异。
- 插入部分
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 (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else { return false; // 树中已经存在要插入的值，本次插入失败 } } cur = new Node(kv); if (cur == parent->_left) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; _root->_col = BLACK; // 强制设定根一定为黑色！ return true; }
- 旋转
2.2.1 什么时候要旋转？
我们新插入的节点默认是红色，当它的 parent 存在且为红色时，就出现了这种情况 —— 树存在两个连续的红色节点，此时我们需要对该部分子树进行旋转 —— 调整树的结构。(下图只展示了部分的子树)
判断条件：parent 存在且为红色
while (parent && parent->_col == RED) { }
2.2.2 几种旋转情况
情形一：uncle 存在，且为红色节点
Node* grandfather = parent->_parent; if (parent == grandfather->_left) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) // 叔叔存在且为红色 { grandfather->_col = RED; parent->_col = BLACK; uncle->_col = BLACK; cur = grandfather; // 向上调整 parent = cur->_parent; } } if (parent == grandfather->_right) { Node* uncle = grandfather->_left; // ... // 与上面代码一致 }
情形二：uncle 不存在 或 存在且为黑色
- parent 在 grandfather 左侧的两种情况
if (parent == grandfather->_left) // parent 在 grandfather 左侧的两种情况 { if (!uncle || uncle->_col == BLACK) { if (cur == parent->_left) // cur 在 parent 左侧 { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else // cur 在 parent 右侧 { RotateL(parent); RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } break; // 旋转结束后，一定要 break } }
旋转结束后，树的结构已经满足了红黑树的标准，如果不跳出循环、继续调整，会出现各种奇怪的问题。
- parent 在 grandfather 右侧
if (parent == grandfather->_right) // parent 在 grandfather 右侧 { if (!uncle || uncle->_col == BLACK) // uncle 不存在 或 uncle存在且为黑色节点 { if (cur == parent->_right) // cur 在 parent 右侧 { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else // cur 在 parent 左侧 { RotateR(parent); RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } break; } }
2.3 红黑树的验证
红黑树的验证，顾名思义，就是验证 你的“红黑树” 是否能满足红黑树的三条性质。
- 根节点一定是黑色
- 不能出现两个连续的红色节点
- 对于同一高度而言，从根到该高度任一节点的简单路径上的黑色节点的数量相同
bool IsBalance() { if (_root && _root->_col == RED) // 验证第一条性质 { cout << "根节点为红色" << endl; return false; } // 要判断是否每一条路径上的黑色节点数相同，首先要找一个标杆 —— 这里旋转树最左路径的黑色节点个数 Node* cur = _root; int RefBlackNum = 0; while (cur) { if (cur->_col == BLACK) ++RefBlackNum; cur = cur->_left; } return Check(_root, 0, RefBlackNum); }
bool Check(Node* cur, int BlackNum, int RefBlackNum) { if (cur == nullptr) // 走到 NIL 时，判断该路径黑色节点个数是否与标杆相同 { if (BlackNum != RefBlackNum) { cout << "路径黑色节点的个数不相同" << endl; // 验证第三条性质 return false; } return true; } if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED) { cout << "存在两个连续的红色节点" << endl; // 验证第二条性质 return false; } if (cur->_col == BLACK) ++BlackNum; return Check(cur->_left, BlackNum, RefBlackNum) // 递归判断当前节点的左右子树是否合法 && Check(cur->_right, BlackNum, RefBlackNum); }
