【C++：红黑树】4 条规则深度理解红黑树：从原理、变色、旋转到完整实现代码

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录前言一. 红黑树核心概念4 条规则定平衡1、红黑树的核心规则1.1 结合图例理解红黑树的路径数量问题NIL2、关键问题思考4 条规则如何保证最长路径 ≤ 2×最短路径3、理解红黑树的效率二、红黑树结构设计节点与类定义三、红黑树插入分场景维护平衡1、插入前的关键约定2、平衡修复场景分析2.1 场景 1叔叔u存在且为红色 -- 仅变色场景1的代码展示(附注释)2.2 场景 2叔叔u不存在或为黑色2.2.1 情况1、单旋 变色场景2的情况1代码展示(附注释)2.2.2 情况2、双旋 变色场景2的情况2代码展示(附注释)3、插入(insert)完整代码实现(附详细注释)四、红黑树的旋转1、右单旋(RotateR)2、左单旋(RotateL)五、红黑树查找与平衡验证1、查找复用二叉搜索树逻辑2、平衡验证检查 4 条规则测试代码结束语前言红黑树用4 条颜色规则实现 “近似平衡”虽然在平衡上没有前面学习的 AVL树 那么平衡但红黑树既避免了 AVL 树的频繁旋转也可以将效率稳定在 O (logN)成为 STL、内核等场景的 “首选树结构”。但规则背后的平衡逻辑、插入时的变色与旋转之间的不同组合常让人困惑。本篇文章就将帮助大家彻底理清红黑树中变色旋转的所有情况。一. 红黑树核心概念4 条规则定平衡1、红黑树的核心规则红黑树本质是带颜色标记的二叉搜索树每个节点只有 “红” 或 “黑” 两种颜色通过以下 4 条规则确保近似平衡每个结点不是红色就是黑色根结点是黑色的如果一个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点。我们观察几张红黑树的图大家就能有更进一步的体会了1.1 结合图例理解红黑树的路径数量问题NIL我们以上面这张图为例上面的红黑树里面有几条路径肯定会有人会认为是4条路径其实并不是实际上是6条路径有人会问这个NIL是什么其实就是我们平常看到的空结点(nullptr)这个叫叶子节点但是这个和我们二叉树里面的叶子结点不是同一个东西这个叶子结点指的是空节点比如上面的红色节点15不是真正的叶子结点它下面还有两个空节点所以上面的黑色节点10、30还有个左孩子的NIL。说明《算法导论》等书籍上补充了一条每个叶子结点NIL都是黑色的规则。它这里所指的叶子结点不是传统的意义上的叶子结点而是我们说的空结点有些书籍上也把NIL叫做外部结点。NIL是为了方便准确的标识出所有路径《算法导论》在后续讲解实现的细节中也忽略了NIL结点所以我们知道—下这个概念即可。2、关键问题思考4 条规则如何保证最长路径 ≤ 2×最短路径由规则 4 可知所有路径的黑色节点数量相同黑色结点个数记为hb因此极端场景下最短路径是全黑节点路径长度 hb由规则 2 和 3 可知路径中无连续红色节点因此最长路径是“黑 - 红” 交替路径长度 2×bh综上任意路径长度满足bh ≤ 路径长度 ≤ 2×bh即最长路径不超过最短路径的 2 倍。3、理解红黑树的效率结合二叉搜索树的特性可推出红黑树节点数 N 与最短路径 bh 的关系2^bh -1 ≤ N 2^(2bh) -1进一步可得bh ≈ logN也就是意味着红黑色增删查改最坏也就是走最长路径因此红黑树的最坏时间复杂度仍为O (logN)。红黑树的表达相对AVL树要抽象一些AVL树通过高度差直观的控制了平衡红黑树通过4条规则的颜色约束间接实现了近似平衡他们效率都是同一档次但是相对而言插入相同数量的结点红黑树的旋转次数是更少的因为他对平衡的控制没那么严格而ALVL树的旋转次数相对更多但能对平衡进行非常严格的控制。这也就说明了 红黑树 和 AVL树 两者的插入操作既有利也有弊。二、红黑树结构设计节点与类定义红黑树的节点需存储键值对、左右子指针、父指针用于回溯平衡和颜色标记而颜色标记我们是通过利用枚举值来获取类定义如下#include iostream using namespace std; // 枚举结点颜色 enum Color { BLACK, // 黑色结点 RED // 红色结点 }; // 红黑树结点结构 templateclass K, class V struct RBTreeNode { pairK, V _kv; // 存储键值对Key-Value RBTreeNodeK, V* _father; // 父节点指针回溯平衡需用到 RBTreeNodeK, V* _left; // 左子节点指针 RBTreeNodeK, V* _right; // 右子节点指针 Color _col; // 节点颜色 RBTreeNode(const pairK, V kv) :_kv(kv) ,_left(nullptr) ,_right(nullptr) ,_father(nullptr) ,_col(RED) //将初始化的结点颜色为红色满足插入要求(不能插入黑色结点) { } }; // 红黑树类 templateclass K, class V class RBTree { public: typedef RBTreeNodeK, V Node; // 核心接口插入、查找、平衡验证、中序遍历 bool Insert(const pairK, V kv); Node* Find(const K key); bool IsBalance(); void Print(); private: // 辅助接口旋转与AVL树逻辑一致无需更新平衡因子 void RotateR(Node* parent); // 右单旋 void RotateL(Node* parent); // 左单旋 // 平衡验证的递归辅助函数 bool Check(Node* root, int blackNum, const int refNum); // 中序遍历的递归辅助函数 void _Print(const Node* root); private: Node* _root nullptr; };三、红黑树插入分场景维护平衡红黑树的插入流程分为两步按二叉搜索树规则插入节点 → 根据颜色规则修复平衡。其中平衡修复是核心需根据 “父亲节点颜色” 和 “叔叔节点颜色” 分场景处理。1、插入前的关键约定插入一个值按二叉搜索树规则进行插入 插入后我们只需要观察是否符合红黑树的4条规则。如果是空树插入新增结点是黑色结点。如果是非空树插入新增结点必须是红色结点因为非空树插入新增黑色结点是一定会破坏了规则4规则4是很难维护的。非空树插入后新增结点必须是红色结点如果其父亲结点是黑色的则没违反任何规则插入结束。非空树插入后新增结点必须是红色结点如果其父亲结点是红色的则违反规则。进一步分析c是红色p为红g必为黑这三个颜色固定了关键的变化看 u 的情况需要根据 u 分为下面3种不同场景分别处理。说明下面所有的讲解和图中我们都把新增结点标识为 c(cur)c的父亲标识为 p(parent)p的父亲标识为 g(grandparent)p的兄弟标识为 u(uncle)。2、平衡修复场景分析2.1 场景 1叔叔u存在且为红色 -- 仅变色条件c当前节点红、p父红、g祖父黑、u叔叔红分析因为p和u都是红色g是黑色把p和u变黑左边子树路径各增加一个黑色结点g再变红相当于保持g所在的子树的黑色结点数量不变同时解决了c和p连续红色结点的问题需要继续往上更新是因为g是红色如果g的父亲还是红色那么就还需要继续处理如果g的父亲是黑色则处理结束了如果g就是整树的根再把g变回黑色。处理逻辑将p 和 u 设为黑色解决连续红色问题将g 设为红色保持黑色节点数量不变符合规则 4将g 作为新的 c更新 c 的 p继续向上回溯若 g 的父亲也是红色需重复处理核心原理通过变色维持 “黑色节点数量守恒”同时消除连续红色节点。注意场景1只变色不旋转。所以无论是c在p的左还是右p是g的左还是右都是上面的变色处理方式。跟AVL树类似上图向我们展示了一种具体情况但是实际中需要这样处理的有很多种情况。下图将以上类似的处理进行了抽象表达d / e / f 代表每条路径拥有 hb 个黑色结点的子树a / b 代表每条路径拥有 hb - 1 个黑色结点的根为红的子树hb 0。下图则分别展示了hb 0 / hb 1 / hb 2的具体情况组合分析hb 0hb 1hb 2场景1的代码展示(附注释)2.2 场景 2叔叔u不存在或为黑色之所以叔叔结点(u) 的不存在和为黑色可以放在一起讨论而不是分开讨论是因为两者旋转后的变色处理是一致的不同的就是前面的旋转情况。为什么变色处理是一样的呢我们以下面单旋 变色的情况为例进行讲解则双旋 变色的情况是一样的解释2.2.1 情况1、单旋 变色条件c红、p红、g黑、u不存在/黑且c与p在同一侧p是g的左孩子c是p的左孩子或p是g的右孩子c是p的右孩子分析p必须变黑才能解决连续红色结点的问题u不存在或者是黑色的这里单纯的变色无法解决需要旋转 变色因为父亲结点(p)在叔叔结点(u)右侧的情况和左侧是基本类似的这里就以左侧为例子进行讲解处理逻辑以p是g的左孩子为例以 g 为旋转点进行右单旋将 p 设为黑色新的子树根避免连续红色将 g 设为红色核心原理通过旋转调整节点位置再通过变色消除连续红色且无需继续向上回溯p变黑后与g的父亲不会违规。场景2的情况1代码展示(附注释)2.2.2 情况2、双旋 变色条件c红、p红、g黑、u不存在/黑且c与p在异侧p是g的左孩子c是p的右孩子或p是g的右孩子c是p的左孩子分析p必须变黑才能解决连续红色结点的问题u不存在或者是黑色的这里单纯的变色无法解决问题需要旋转变色因为父亲结点(p)在叔叔结点(u)右侧的情况和左侧是基本类似的这里就以左侧为例子进行讲解处理逻辑以p是g的左孩子为例以p为旋转点进行左单旋将c转到p的位置变为场景 2 的形态以g为旋转点进行右单旋将c设为黑色新的子树根将g设为红色核心原理先通过一次旋转将“异侧” 转为 “同侧”再按场景 2 处理最终消除违规。场景2的情况2代码展示(附注释)3、插入(insert)完整代码实现(附详细注释)public: bool insert(const pairK, V kv) { //前面的步骤和二叉搜索树(BST)的插入一样 //树为空直接创建根节点 if (_root nullptr) { _root new Node(kv); _root-_col BLACK; return true; } //树非空遍历找插入位置 Node* cur _root; Node* father nullptr; while (cur) { if (cur-_kv.first kv.first) { father cur; cur cur-_right; } else if (cur-_kv.first kv.first) { father cur; cur cur-_left; } else { return false; } }//循环结束则找到了插入位置 cur new Node(kv); //还需要判断插入位置在father的左边还是右边 if (father-_kv.first kv.first) { father-_right cur; } else { father-_left cur; } cur-_father father; //首先father为红插入红色结点才会出现问题进行修改 //如果father本身就是黑色则插入结点后仍然满足红黑树条件直接返回 while (father father-_col RED) { Node* grandfather father-_father; //进入循环说明father一定为红色所以father一定有父亲结点(如果没有说明为根节点而根节点一定是黑色) if (grandfather-_left father) { // g // p u Node* uncle grandfather-_right; if (uncle uncle-_col RED) { // 情况一uncle存在且为红色 // 变色继续向上处理 father-_col uncle-_col BLACK; grandfather-_col RED; cur grandfather; father cur-_father; //若此时grandfather为根节点则father为空需要结束判断则可以在循环条件中加上father判空 } else { //情况二uncle不存在 / uncle存在且为黑色 //uncle为空说明此时的cur一定是新增节点的位置 //因为如果不是新增结点而father为红则说明father一定有孩子且一定为黑则插入前就已经不符合红黑树条件了 //uncle不为空且为黑色说明此时的cur一定不是新增结点的位置 //因为如果是新增结点则在插入前grandfather的左右两边黑色结点数就已经不同违反条件了 //但不管是哪种情况旋转之后变色的操作是一致的 //只是需要判断cur是在father左边还是右边因为左边和右边旋转的情况是不同的 if (father-_left cur) // 单旋变色 { // g // p u // c //cur在father左边则进行右单旋 RotateR(grandfather); father-_col BLACK; grandfather-_col RED; } else // 双旋变色 { // g // p u // c //cur在father右边则进行左右双旋 RotateL(father); RotateR(grandfather); cur-_col BLACK; grandfather-_col RED; } //由于情况二的两种场景旋转后新的头节点都为黑色 //则头节点的上一个结点不管是黑还是红都符合红黑树条件不需要再向上继续判断 break; } } else { //uncle结点在father左侧的核心操作和上面基本一致 // g // u p Node* uncle grandfather-_left; if (uncle uncle-_col RED) { uncle-_col father-_col BLACK; grandfather-_col RED; cur grandfather; father cur-_father; } else { if (father-_right cur) // 单旋变色 { // g // u p // c //cur在father右边则进行左单旋 RotateL(grandfather); father-_col BLACK; grandfather-_col RED; } else // 双旋变色 { // g // u p // c //cur在father左边则进行右左单旋 RotateR(father); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } //最终再让根节点变成黑色 //这样就能保证如果上面的循环判断变色一直执行到根节点 //并且最后为情况一则根节点也会变成红色还需要额外处理变成黑色 //所以在循环结束后统一让根节点变成黑色就不需要在循环内单独判断了 _root-_col BLACK; return true; }四、红黑树的旋转因为红黑树的旋转逻辑和前面学习的 AVL树 的旋转逻辑是完全一样的并且减去了平衡因子的更新所以这里就只展现代码实现了如果对旋转还不够理解的可以看我的上篇文章【CAVL树】平衡核心、旋转策略从原理到完整代码实现1、右单旋(RotateR)private: //右单旋 void RotateR(Node* father) { Node* subL father-_left; Node* subLR subL-_right; Node* prev_father father-_father; subL-_right father; father-_father subL; father-_left subLR; if (subLR) { subLR-_father father; } if (prev_father nullptr) { _root subL; _root-_father nullptr; } else { if (prev_father-_left father) { prev_father-_left subL; subL-_father prev_father; } else { prev_father-_right subL; subL-_father prev_father; } } }2、左单旋(RotateL)private: //左单旋 void RotateL(Node* father) { Node* subR father-_right; Node* subRL subR-_left; Node* prev_father father-_father; subR-_left father; father-_father subR; father-_right subRL; if (subRL) { subRL-_father father; } if (prev_father nullptr) { _root subR; _root-_father nullptr; } else { if (prev_father-_left father) { prev_father-_left subR; subR-_father prev_father; } else { prev_father-_right subR; subR-_father prev_father; } } }五、红黑树查找与平衡验证1、查找复用二叉搜索树逻辑红黑树的查找与普通二叉搜索树一致时间复杂度 O (logN)public: //红黑树的查找Find Node* Find(const K key) { Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_right; } else if (cur-_kv.first key) { cur cur-_left; } else { return cur; // 找到返回节点指针 } } return nullptr; // 未找到 }2、平衡验证检查 4 条规则验证红黑树是否合法需逐一检查 4 条规则核心是确保 “无连续红色节点” 和 “黑色节点数量一致”规则1枚举颜色类型天然实现保证了颜色不是黑色就是红色。规则2直接检查根即可规则3前序遍历遇到红色结点查孩子不方便因为孩子有两个且不一定存在反过来检查父亲的颜色就方便多了。规则4前序遍历遍历过程中用形参记录根当前结点的blackNum(黑色结点数量)前序遍历遇到黑色结点就blackNum走到空就计算出了一条路径的黑色结点数量再通过提前计算任意一条路径黑色结点数量作为参考值依次比较即可。public: //红黑树的平衡验证 bool IsBalanceTree() { if (_root _root-_col RED) { return false; } // 最左路径黑色节点的数量做参考值refNum去比较其它路径 int refNum 0; Node* cur _root; while (cur) { if (cur-_col BLACK) { refNum; } cur cur-_left; } return _Checkcolour(_root, 0, refNum); } private: // blackNum 表示根到当前节点路径上黑色节点的数量 // 前序递归 bool _Checkcolour(const Node* root, int blackNum, int refNum) { if (root nullptr) { // 检查每条路径的黑色节点数量 if (blackNum ! refNum) { cout 黑色节点的数量不相等,不是红黑树 endl; return false; } return true; } // 检查连续的红色节点 if (root-_col RED root-_father root-_father-_col RED) { return false; } //当前结点为黑则当前路径黑色结点数blackNum if (root-_col BLACK) { blackNum; } return _Checkcolour(root-_left, blackNum, refNum) _Checkcolour(root-_right, blackNum, refNum); }测试代码#include RBTree.h void TestBRTree1() { RBTreeint, int tree; //常规测试用例 int arr1[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; //双旋场景的测试用例 int arr2[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : arr1) { tree.insert({ e, e }); cout Insert: e -; cout tree.IsBalanceTree() endl; } tree.Print(); cout tree.IsBalanceTree() endl; } #includevector #includetime.h // 插入一堆随机值测试平衡顺便测试一下高度和性能等 void TestRBTree2() { const int N 1000000; vectorint v; v.reserve(N); srand(time(0)); for (size_t i 0; i N; i) { v.push_back(rand() i); } size_t begin2 clock(); RBTreeint, int t; for (auto e : v) { t.insert({e, e}); } size_t end2 clock(); cout Insert: end2 - begin2 endl; cout t.IsBalanceTree() endl; cout Height: t.height() endl; cout Size: t.size() endl; size_t begin1 clock(); // 随机值 for (size_t i 0; i N; i) { t.Find((rand() i)); } size_t end1 clock(); cout Find: end1 - begin1 endl; } int main() { cout 测试1 endl; TestBRTree1(); cout endl; cout 测试2 endl; TestRBTree2(); return 0; }结束语到此C 红黑树的实现就讲解完了。红黑树的精髓在于用 “颜色标记” 替代 “严格高度控制”4 条规则看似简单却通过 “变色减少旋转”“旋转修复关键失衡”在平衡与开销间找到最优解。希望对大家学习C能有所收获C参考文档https://legacy.cplusplus.com/reference/https://zh.cppreference.com/w/cpphttps://en.cppreference.com/w/