【C++第二十章】红黑树
红黑树介绍🧐
红黑树是一种自平衡的二叉搜索树，通过颜色标记和特定规则保持树的平衡性，从而在动态插入、删除等操作中维持较高的效率。它的最长路径不会超过最短路径的两倍，它的查找效率比AVL树更慢(对于CPU来说可以忽略不计)，但是它不会像AVL树那样花费更大的代价去实现严格平衡(旋转)。
1.红黑树与AVL树🔎
特性 红黑树 AVL树 平衡标准 通过颜色规则约束，允许一定不平衡 严格平衡（左右子树高度差≤1） 插入/删除效率 旋转次数少，调整频率低 可能需要多次旋转，调整频率高 查询效率 平均稍慢（高度≤2log(n+1)） 更快（高度严格为O(log n)） 适用场景 频繁插入/删除（如内存数据库、STL Map） 查询密集（如字典、静态数据集） 实现复杂度 较复杂（需处理颜色标记和多种情况） 相对简单（仅维护平衡因子） 2.设计思想🔎
- 平衡与效率的折衷：
红黑树通过放宽平衡条件（允许局部不平衡），减少插入/删除时的调整次数，适合写多读少的场景。AVL树追求绝对平衡，适合读多写少的场景。- 模拟B树结构：
红黑树可视为一种“二叉化”的B树（如2-3-4树），每个节点隐含多个键值，通过颜色标记合并逻辑，减少树的高度。- 工业界应用：
- 红黑树：Java的
TreeMap、C++的std::map、Linux内核调度器。- AVL树：Windows内核对象管理、需要快速查找的静态数据库。
所以，若需要高频插入/删除，我们可以选择红黑树，若需要快速查询，不怎么变动数据，选择AVL树。
3.红黑树的性质🔎
- 每个节点不是红色就是黑色。
- 根节点一定是黑色的。
- 如果一个节点是红色的，则它的两个孩子节点是黑色的。(不能出现连续的红色节点)。
- 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。(每条路径黑色节点数量相同)。
- 每个叶子节点都是黑色的(这里的叶子节点指的是空指针节点，也称NIL节点)
其中，路径的条数是从根节点到NIL节点来计算的，并且NIL节点的黑色也要统计到每条路径的黑色节点数量中。红黑树的最长和最短路径不一定存在。
红黑树插入实现🧐
红黑树的平衡方式为：直接变色、旋转变色，所以我们还是要用到AVL树中的旋转代码。
1.红黑树的节点定义🔎
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; //这里使用的是KV模型 Color _col; //颜色 RBTreeNode(const pair<K, V>& kv) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _col(RED) //默认设置为红色，如果默认为黑色，则每次插入必定违反性质4 {} };2.左单旋、右单旋🔎
与AVL树中一摸一样的方法。
//左单旋 void RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; subR->_left = parent; Node* parentParent = parent->_parent; //记录传来结点的父节点，后面判断是否为整个树的根 parent->_parent = subR; if (subRL) //subRL不为空才处理 subRL->_parent = parent; if (_root == parent) //当parent就是整个树的根，直接改变 { _root = subR; subR->_parent = nullptr; } else { //如果不是，结点在父左边就将左边置为subR，否则右边 if (parentParent->_left == parent) { parentParent->_left = subR; } else { parentParent->_right = subR; } subR->_parent = parentParent; //父节点也要改变 } } //右单旋 void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) //subLR不为空才处理 subLR->_parent = parent; //放在subL下面，不然parentParent可能为空 Node* parentParent = parent->_parent; //记录传来结点的父节点，后面判断是否为整个树的根 subL->_right = parent; parent->_parent = subL; if (_root == parent) //当parent就是整个树的根，直接改变 { _root = subL; subL->_parent = nullptr; } else { //如果不是，结点在父左边就将左边置为subL，否则右边 if (parentParent->_left == parent) { parentParent->_left = subL; } else { parentParent->_right = subL; } subL->_parent = parentParent; //subL父节点也要改变 } }3.插入🔎
我们在节点定义时就将默认颜色设置为红色，是因为将默认颜色设置为黑色的话，那么一个正常的红黑树突然插入一个黑色必定违反性质4，则每次都需要调整。
而插入红色时我们进行分析得：
1.当插入节点的父亲节点为黑色时，没有违反任何性质，不需要处理。
2.当插入节点的父亲节点为红色时，违反性质3，需要处理。
由此再次对红黑树分情况讨论：
我们首先约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点
情况一：cur为红，p为红，g为黑，u存在且为红
解决方法：
将p，u改为黑，g改为红，如果g是根节点，那么再改为黑，如果不是根节点且违反性质4，那么将g看为cur，再次进行调整。
情况二：cur为红，p为红，g为黑，u不存在或者u存在且为黑
解决方法：
如果p是g的左孩子，cur为p的左孩子，则进行右单旋；如果p是g的右孩子，cur为p的右孩子，则进行左单旋。然后进行p、g变色，p变黑，g变红。
情况三：cur为红，p为红，g为黑，u不存在或者存在且为黑。
解决方法：
如果p是g的左孩子，cur为p的右孩子，则进行左单旋；如果p是g的右孩子，cur为p的左孩子，则进行右单旋。然后转换为情况二处理。
bool Insert(const 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)、 { // g // p u // c //变色 parent->_col = uncle->_col = BLACK; // 父叔变黑 grandfather->_col = RED; // 祖父变红 //继续往上处理 cur = grandfather; parent = cur->_parent; } // 叔节点不存在或为黑（需要旋转） else { // 当前节点是父的左孩子 if (cur == parent->_left) { // g // p // c RotateR(grandfather); parent->_col = BLACK; // 原父节点变黑 grandfather->_col = RED; //祖父变红 } // 当前节点是父的右孩子 else { // g // p // c RotateL(parent); // 先左旋父节点转换为情况二 RotateR(grandfather); cur->_col = BLACK; //当前节点变黑 grandfather->_col = RED; //祖父变红 } break; // 旋转后子树平衡，退出循环 } } // 父节点是祖父的右孩子 else { // g // u p // c 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) { // g // p // c RotateL(grandfather); // 左旋祖父节点 parent->_col = BLACK; grandfather->_col = RED; } // 当前节点是父的左孩子 else { // g // p // c RotateR(parent); // 先右旋父节点转换为情况二 RotateL(grandfather); // 再左旋祖父节点 grandfather->_col = RED; cur->_col = BLACK; } break; } } } _root->_col = BLACK; //直接根变黑，不在需要考虑根的颜色问题 return true; }4.平衡检测🔎
//根节点到当前结点的黑色数量 bool Check(Node* root, int blacknum, const int refVal) { if (root == nullptr) { if (blacknum != refVal) { cout << "存在黑色结点数量不相等的路径!" << endl; return false; } return true; } if (root->_col == RED && root->_parent->_col == RED) { //当两个结点都为红，就出问题了 cout << "有连续的红色" << endl; return false; } if (root->_col == BLACK) { ++blacknum; } return Check(root->_left, blacknum, refVal) && Check(root->_right, blacknum, refVal); } bool IsBalance() { if (_root == nullptr) return true; if (_root->_col == RED) return false; int refVal = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) { ++refVal; } cur = cur->_left; } int blacknum = 0; return Check(_root, blacknum, refVal); }
结尾👍
以上便是红黑树的介绍和插入分析，如果有疑问或者建议都可以私信笔者交流，大家互相学习，互相进步！🌹
