云深麋鹿专栏C | 用C语言学数据结构 | Java回顾上一篇我们结束了 AVLTree 的相关介绍接下来这篇文章让我们进入到 红黑树 的学习体会新的设计思路吧~放个目录前言一 红黑树的概念1.1 红黑树的规则1.2 红黑树如何确保最长路径不超过最短路径的2倍1.3 红黑树的效率二 红黑树的实现2.1 定义红黑树2.1.1 枚举类Colour2.1.2 定义结点结构体2.2 红黑树的插入2.2.1 特别处理1变色1简单举例2推广到所有情况①来个抽象图②情况1hb 01.介绍所处情况2.采取操作③情况2hb 11.介绍所处情况2.采取措施④情况3hb 21.介绍所处情况2.采取措施3代码实现2.2.2 特别处理2单旋变色1 u不存在①介绍所处情况②采取操作2u存在且为黑①介绍所处情况②采取措施3代码实现2.2.3 特别处理3双旋变色1u不存在①介绍所处情况②采取措施2u存在且为黑①介绍所处情况②采取措施3代码实现2.2.4 整体代码2.3 红黑树的验证2.4 红黑树的查找2.5 红黑树的删除2.5.1 删除指定节点2.5.2 析构2.6 测试前言摘要红黑树是一种自平衡的二叉搜索树通过为每个结点增加颜色属性并施加约束确保树的高度始终保持在 O(logN) 级别。本文首先介绍红黑树的基本概念与四条核心规则分析其如何保证最长路径不超过最短路径的 2 倍并推导其增删查改的时间复杂度为 O(logN)随后以 C 为例从定义结点结构开始逐步实现红黑树的插入变色、单旋变色、双旋变色三种特别处理、验证、查找、删除与析构并附上测试用例验证正确性。最后总结红黑树的核心要点为后续封装红黑树实现 mymap 与 myset 容器打下基础。一 红黑树的概念每个结点增加一个存储位来表示结点的颜色可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而是接近平衡的。1.1 红黑树的规则每个结点不是红色就是黑色。根结点是黑色的。如果⼀个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。但可以有连续的黑色节点对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点。下面来个动图演示一颗红黑树的形成上图网址https://www.cs.usfca.edu/~galles/visualization/RedBlack.html1.2 红黑树如何确保最长路径不超过最短路径的2倍从根到NULL结点的每条路径都有相同数量的黑色结点。极端场景下最短路径就就是全是黑色结点的路径长度设为bh(black height)。最长的路径就是⼀黑⼀红间隔组成长度设为2*bh。理论上的最短路径和最长路径并不是在每棵红黑树都存在的。假设任意⼀条从根到NULL结点路径的长度为h那么bh h 2*bh。1.3 红黑树的效率假设N是红黑树树中结点数量h最短路径的长度那么2^h - 1 N 2^(2*h) - 1由此推出h ≈ logN。关于N 2^(2*h) - 1为什么取不到等号存在最短路径最长路径的同时二叉树不可能是满二叉树。假设h 1最短路径为1最长路径为2。N 取不到2^(2*h) - 1即3。最多只能取到如图所示2个结点。也就是意味着红黑树增删查改最坏也就是走最长路径2*logN那么时间复杂度还是O(logN)。二 红黑树的实现2.1 定义红黑树2.1.1 枚举类ColourenumColour{RED,BLACK};没啥好说的红黑树就红色或者黑色两种结点。2.1.2 定义结点结构体templateclassK,classVstructRBTreeNode{pairK,V_kv;RBTreeNodeK,V*_left;RBTreeNodeK,V*_right;RBTreeNodeK,V*_parent;Colour _col;RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};跟AVL树类似只是多了个_col记录颜色。这里和AVL树一样记录了_parent方便后续旋转。2.2 红黑树的插入为了保证每条路径上的黑色结点数量相等没有特殊情况的话新插入结点都为红。红黑树为空插入结点为黑。插入结点的parent为黑插入结点为红。插入结点的parent为红插入结点为红不符合规则特别处理。假设插入结点为cur插入结点的父母为parentparent的父母为grandparentparent的兄弟为uncle后面都以首字母简称。部分代码boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;while(parentparent-_colRED){Node*gparentparent-_parent;Node*unclenullptr;// change colour ...}}这部分逻辑跟AVLTree是一样的除了处理_col的部分处理红黑树_root为空的情况。用cur找到新结点应当插入位置parent记录cur的_parent.最后构造新结点把新结点赋值给cur让其根据情况成为parent的左孩子或右孩子。其次若parent为红需要特殊处理进入循环。先定义gparent和uncle。注由于parent为红而_root一定为黑所以gparent一定存在。极端情况为gparent恰好就是_root。2.2.1 特别处理1变色u存在且为红只变色。1简单举例画个栗图插入cur后存在连续的红色结点。则要实现的效果变色后cur更新为g向上检查变色。2推广到所有情况①来个抽象图上图的c可能不是新增结点而是从g变到c的设a、b是每条路径拥有hb-1个黑色结点的根为红色结点的子树。设d、e、f是每条路径拥有hb个黑色结点的子树。②情况1hb 01.介绍所处情况a、b、d、e、f都是空子树。如图c还可以是下面白色结点位置之一c就是新插入结点上面的1简单举例就属于这种情况。2.采取操作直接变色到③情况2hb 11.介绍所处情况c是由g变上来的Ⅰ则a、b是根结点为红色的hb 0的子树这样。Ⅱ新增结点新增结点可能出现在4个位置即4个白色结点之一Ⅲd、e、f是根结点为黑色的hb 1的子树四种情况。Ⅳ总结一共444*4 256种情况都是只需要变色就行。2.采取措施取其中一种情况分析明显有连续的红色结点不符合规则3需变色。最终效果再往上检查④情况3hb 21.介绍所处情况Ⅰ则a、b是根结点为红色的hb 1的子树如图4个位置的红色结点可能存在或不存在。C(4,4) C(3,4) … C(0,4) 16所以子树共有16种可能形态。Ⅱ新增结点16种形态一种形态下可新增结点的位置也很多是否会触发变色也不一定。拿一个极端例子分析直接新增不触发变色Ⅲd、e、f是根结点为黑色的hb 2的子树子树可以是3层或4层。3层C(4,4) C(3,4) … C(0,4) 164层C(8,8) C(7,8) … C(0,8) 256所以一共16256 272 种可能形态。Ⅲ总结总共可能的情况数有百亿往上。2.采取措施取其中一种情况分析变色c向上更新g变到c再继续向上更新。3代码实现//省略给uncle赋值部分代码if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{//特别处理2}2.2.2 特别处理2单旋变色有两种情况u不存在 或 存在且为黑。采取操作单旋下面举例为需要右单旋的情况左单旋本质上也是一样的变色。1 u不存在①介绍所处情况u不存在则c一定是新增结点。因为如果c更新上来的c原来就得是黑的。c是黑的下图中g的左子树和右子树黑色结点数量就不相同了。不符合规则4因此c不可能是更新上来的。②采取操作先以g为旋转点右单旋再变色2u存在且为黑①介绍所处情况u存在且为黑则c一定是更新上来的。同样反推如果c是新增节点a b子树肯定为空。我们看新增前的树p的右子树为空d子树也肯定为空子树。先不论 e f 子树是什么形态g的右子树已经比左子树多了u这个黑色结点不符合规则4。因此c不可能是新增节点。在此基础上我们先来看新增前的情况为保证规则4a b e f 四棵子树黑色结点为hb-1个d子树为hb个。a b是两棵根结点为红色的子树。再来看新增后从新增结点更新上去a b子树的根结点就变成了黑色上图 a b d 子树黑色结点为hb个e f子树为hb-1个。②采取措施同样先以g为旋转点右单旋再变色3代码实现//同样省略给uncle赋值部分代码if(uncleuncle-_colRED){//特别处理1}else{if(gparent-_leftparentparent-_leftcur){_RotateR(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_rightparentparent-_rightcur){_RotateL(gparent);parent-_colBLACK;gparent-_colRED;}else{//特别处理3}}2.2.3 特别处理3双旋变色也是两种情况u不存在 或 存在且为黑。采取操作双旋这里同样只举例先左单旋再右单旋另一种情况本质上一样变色。1u不存在①介绍所处情况c一定是新增结点这个推论跟单旋的情况一样。②采取措施先以p为旋转点左单旋变色再以g为旋转点右单旋2u存在且为黑①介绍所处情况c同样一定是更新上来的。新增结点前的树为保证规则4d子树黑色结点数量为hb a b e f 子树为hb-1a b 子树根结点为红色。新增后假设新增结点在a子树。更新上去到c变为红色a b子树变为根节点为黑色的子树。则现在 a b d 子树黑色结点为hb个e f不变还是hb-1个。②采取措施先以p为旋转点左单旋变色再以g为旋转点右单旋最后的树显然符合规则4搞定。3代码实现if(uncleuncle-_colRED){//特别处理1}else{if(gparent-_leftparentparent-_leftcur){//特别处理2}elseif(gparent-_rightparentparent-_rightcur){//特别处理2}elseif(gparent-_leftparentparent-_rightcur){_RotateL(parent);cur-_colBLACK;gparent-_colRED;_RotateR(gparent);}else{_RotateR(parent);cur-_colBLACK;gparent-_colRED;_RotateL(gparent);}}2.2.4 整体代码boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;// change colourwhile(parentparent-_colRED){Node*gparentparent-_parent;Node*unclenullptr;//给uncle赋值if(gparent-_leftparent){unclegparent-_right;}else{unclegparent-_left;}//分情况特殊处理if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{if(gparent-_leftparentparent-_leftcur){_RotateR(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_rightparentparent-_rightcur){_RotateL(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_leftparentparent-_rightcur){_RotateL(parent);cur-_colBLACK;gparent-_colRED;_RotateR(gparent);}else{_RotateR(parent);cur-_colBLACK;gparent-_colRED;_RotateL(gparent);}}//循环继续的要点cur跟parent需要更新curgparent;parentcur-_parent;}_root-_colBLACK;returntrue;}为了保证_root是黑的最后可以直接不管三七二十一给它赋值一下。2.3 红黑树的验证分别检查4条规则。boolIsRBTree(){if(_rootnullptr){returntrue;}if(_root-_col!BLACK){returnfalse;}intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}return_check(_root,refNum,0);}先处理树为空_root为空的情况。规则①检查_root是否为黑。用refNum记录一条路径从_root到空结点的黑色结点备用。进入_check函数。bool_check(Node*root,constintrefNum,intblackNum){if(rootnullptr){if(blackNum!refNum){coutrefNum:refNum; blackNum:blackNumendl;returnfalse;}returntrue;}if(root-_colBLACK){blackNum;}elseif(root-_colRED){if(root-_parent-_colRED){coutred node has red parentendl;returnfalse;}}else{coutillegal colourendl;returnfalse;}return_check(root-_left,refNum,blackNum)_check(root-_right,refNum,blackNum);}进入函数先检查root是否为空。规则④若为空则结束一条路径需要检查这条路径的黑色结点数量blackNum是否与参考数量refNum相等。若不相等则违反规则④返回false相等则返回true。root不为空则判断当前root是否为黑。root为黑则blackNum。规则③root为红则判断其parent是否为红为红违反规则③返回false。规则②若root既不为黑也不为红违反规则②返回false。再递归检查root-_left跟root-_right。2.4 红黑树的查找跟AVL树一样。Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}直接照搬过来。2.5 红黑树的删除2.5.1 删除指定节点不细究比较复杂可以放一份思路步骤操作说明找真正删除节点 y若 z 有两个孩子用中序后继替换也可用前驱最终 y 一定只有 0 或 1 个孩子。替换用 y 的孩子x可能为空顶替 y 的位置并记录 y 在父节点中的左右方向isLeft。关键判断只有删除的节点y是黑色时才需要调用deleteFixup因为删除红节点不影响黑色路径。修复循环核心是处理“双黑”节点即替代上来的节点 x。1.兄弟为红→ 旋转父节点转为兄弟为黑的情况。2.兄弟为黑且其两个子节点均为黑→ 兄弟变红将双黑往上移。3.兄弟为黑且远端侄子为黑近端为红→ 旋转兄弟转为情况4。4.兄弟为黑且远端侄子为红→ 旋转父节点并着色直接结束。收尾循环结束后将当前节点x涂黑若 x 为空则忽略彻底消去双黑。2.5.2 析构加一个析构函数防止内存泄漏public://...~RBTree(){_Destroy(_root);_rootnullptr;}private:void_Destroy(Node*root){if(rootnullptr){return;}_Destroy(root-_left);_Destroy(root-_right);deleteroot;}//...辅助函数_Destroy写在private区域以便递归销毁。2.6 测试voidTestRBTree01(void){wyzy::RBTreeint,intt;//1测试用例不涉及双旋//int a[] { 18, 10, 6, 15, 30, 25, 40 };//2测试用例涉及双旋inta[]{18,10,6,15,30,25,40,27};for(autoe:a){t.Insert({e,e});}t.inOrder();t.preOrder();coutt.IsRBTree()endl;}测试代码仅供参考。这里我写了inOrder跟preOrder方便打印观察。颜色打印出来0代表红1代表黑。最终测试结果符合预期。红黑树的学习就到这里下一篇我们要 封装红黑树 实现容器mymap跟myset 很快会更出来~ C++ | 红黑树实现
云深麋鹿专栏C | 用C语言学数据结构 | Java回顾上一篇我们结束了 AVLTree 的相关介绍接下来这篇文章让我们进入到 红黑树 的学习体会新的设计思路吧~放个目录前言一 红黑树的概念1.1 红黑树的规则1.2 红黑树如何确保最长路径不超过最短路径的2倍1.3 红黑树的效率二 红黑树的实现2.1 定义红黑树2.1.1 枚举类Colour2.1.2 定义结点结构体2.2 红黑树的插入2.2.1 特别处理1变色1简单举例2推广到所有情况①来个抽象图②情况1hb 01.介绍所处情况2.采取操作③情况2hb 11.介绍所处情况2.采取措施④情况3hb 21.介绍所处情况2.采取措施3代码实现2.2.2 特别处理2单旋变色1 u不存在①介绍所处情况②采取操作2u存在且为黑①介绍所处情况②采取措施3代码实现2.2.3 特别处理3双旋变色1u不存在①介绍所处情况②采取措施2u存在且为黑①介绍所处情况②采取措施3代码实现2.2.4 整体代码2.3 红黑树的验证2.4 红黑树的查找2.5 红黑树的删除2.5.1 删除指定节点2.5.2 析构2.6 测试前言摘要红黑树是一种自平衡的二叉搜索树通过为每个结点增加颜色属性并施加约束确保树的高度始终保持在 O(logN) 级别。本文首先介绍红黑树的基本概念与四条核心规则分析其如何保证最长路径不超过最短路径的 2 倍并推导其增删查改的时间复杂度为 O(logN)随后以 C 为例从定义结点结构开始逐步实现红黑树的插入变色、单旋变色、双旋变色三种特别处理、验证、查找、删除与析构并附上测试用例验证正确性。最后总结红黑树的核心要点为后续封装红黑树实现 mymap 与 myset 容器打下基础。一 红黑树的概念每个结点增加一个存储位来表示结点的颜色可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束红黑树确保没有一条路径会比其他路径长出2倍因而是接近平衡的。1.1 红黑树的规则每个结点不是红色就是黑色。根结点是黑色的。如果⼀个结点是红色的则它的两个孩子结点必须是黑色的也就是说任意一条路径不会有连续的红色结点。但可以有连续的黑色节点对于任意一个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的黑色结点。下面来个动图演示一颗红黑树的形成上图网址https://www.cs.usfca.edu/~galles/visualization/RedBlack.html1.2 红黑树如何确保最长路径不超过最短路径的2倍从根到NULL结点的每条路径都有相同数量的黑色结点。极端场景下最短路径就就是全是黑色结点的路径长度设为bh(black height)。最长的路径就是⼀黑⼀红间隔组成长度设为2*bh。理论上的最短路径和最长路径并不是在每棵红黑树都存在的。假设任意⼀条从根到NULL结点路径的长度为h那么bh h 2*bh。1.3 红黑树的效率假设N是红黑树树中结点数量h最短路径的长度那么2^h - 1 N 2^(2*h) - 1由此推出h ≈ logN。关于N 2^(2*h) - 1为什么取不到等号存在最短路径最长路径的同时二叉树不可能是满二叉树。假设h 1最短路径为1最长路径为2。N 取不到2^(2*h) - 1即3。最多只能取到如图所示2个结点。也就是意味着红黑树增删查改最坏也就是走最长路径2*logN那么时间复杂度还是O(logN)。二 红黑树的实现2.1 定义红黑树2.1.1 枚举类ColourenumColour{RED,BLACK};没啥好说的红黑树就红色或者黑色两种结点。2.1.2 定义结点结构体templateclassK,classVstructRBTreeNode{pairK,V_kv;RBTreeNodeK,V*_left;RBTreeNodeK,V*_right;RBTreeNodeK,V*_parent;Colour _col;RBTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}};跟AVL树类似只是多了个_col记录颜色。这里和AVL树一样记录了_parent方便后续旋转。2.2 红黑树的插入为了保证每条路径上的黑色结点数量相等没有特殊情况的话新插入结点都为红。红黑树为空插入结点为黑。插入结点的parent为黑插入结点为红。插入结点的parent为红插入结点为红不符合规则特别处理。假设插入结点为cur插入结点的父母为parentparent的父母为grandparentparent的兄弟为uncle后面都以首字母简称。部分代码boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;while(parentparent-_colRED){Node*gparentparent-_parent;Node*unclenullptr;// change colour ...}}这部分逻辑跟AVLTree是一样的除了处理_col的部分处理红黑树_root为空的情况。用cur找到新结点应当插入位置parent记录cur的_parent.最后构造新结点把新结点赋值给cur让其根据情况成为parent的左孩子或右孩子。其次若parent为红需要特殊处理进入循环。先定义gparent和uncle。注由于parent为红而_root一定为黑所以gparent一定存在。极端情况为gparent恰好就是_root。2.2.1 特别处理1变色u存在且为红只变色。1简单举例画个栗图插入cur后存在连续的红色结点。则要实现的效果变色后cur更新为g向上检查变色。2推广到所有情况①来个抽象图上图的c可能不是新增结点而是从g变到c的设a、b是每条路径拥有hb-1个黑色结点的根为红色结点的子树。设d、e、f是每条路径拥有hb个黑色结点的子树。②情况1hb 01.介绍所处情况a、b、d、e、f都是空子树。如图c还可以是下面白色结点位置之一c就是新插入结点上面的1简单举例就属于这种情况。2.采取操作直接变色到③情况2hb 11.介绍所处情况c是由g变上来的Ⅰ则a、b是根结点为红色的hb 0的子树这样。Ⅱ新增结点新增结点可能出现在4个位置即4个白色结点之一Ⅲd、e、f是根结点为黑色的hb 1的子树四种情况。Ⅳ总结一共444*4 256种情况都是只需要变色就行。2.采取措施取其中一种情况分析明显有连续的红色结点不符合规则3需变色。最终效果再往上检查④情况3hb 21.介绍所处情况Ⅰ则a、b是根结点为红色的hb 1的子树如图4个位置的红色结点可能存在或不存在。C(4,4) C(3,4) … C(0,4) 16所以子树共有16种可能形态。Ⅱ新增结点16种形态一种形态下可新增结点的位置也很多是否会触发变色也不一定。拿一个极端例子分析直接新增不触发变色Ⅲd、e、f是根结点为黑色的hb 2的子树子树可以是3层或4层。3层C(4,4) C(3,4) … C(0,4) 164层C(8,8) C(7,8) … C(0,8) 256所以一共16256 272 种可能形态。Ⅲ总结总共可能的情况数有百亿往上。2.采取措施取其中一种情况分析变色c向上更新g变到c再继续向上更新。3代码实现//省略给uncle赋值部分代码if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{//特别处理2}2.2.2 特别处理2单旋变色有两种情况u不存在 或 存在且为黑。采取操作单旋下面举例为需要右单旋的情况左单旋本质上也是一样的变色。1 u不存在①介绍所处情况u不存在则c一定是新增结点。因为如果c更新上来的c原来就得是黑的。c是黑的下图中g的左子树和右子树黑色结点数量就不相同了。不符合规则4因此c不可能是更新上来的。②采取操作先以g为旋转点右单旋再变色2u存在且为黑①介绍所处情况u存在且为黑则c一定是更新上来的。同样反推如果c是新增节点a b子树肯定为空。我们看新增前的树p的右子树为空d子树也肯定为空子树。先不论 e f 子树是什么形态g的右子树已经比左子树多了u这个黑色结点不符合规则4。因此c不可能是新增节点。在此基础上我们先来看新增前的情况为保证规则4a b e f 四棵子树黑色结点为hb-1个d子树为hb个。a b是两棵根结点为红色的子树。再来看新增后从新增结点更新上去a b子树的根结点就变成了黑色上图 a b d 子树黑色结点为hb个e f子树为hb-1个。②采取措施同样先以g为旋转点右单旋再变色3代码实现//同样省略给uncle赋值部分代码if(uncleuncle-_colRED){//特别处理1}else{if(gparent-_leftparentparent-_leftcur){_RotateR(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_rightparentparent-_rightcur){_RotateL(gparent);parent-_colBLACK;gparent-_colRED;}else{//特别处理3}}2.2.3 特别处理3双旋变色也是两种情况u不存在 或 存在且为黑。采取操作双旋这里同样只举例先左单旋再右单旋另一种情况本质上一样变色。1u不存在①介绍所处情况c一定是新增结点这个推论跟单旋的情况一样。②采取措施先以p为旋转点左单旋变色再以g为旋转点右单旋2u存在且为黑①介绍所处情况c同样一定是更新上来的。新增结点前的树为保证规则4d子树黑色结点数量为hb a b e f 子树为hb-1a b 子树根结点为红色。新增后假设新增结点在a子树。更新上去到c变为红色a b子树变为根节点为黑色的子树。则现在 a b d 子树黑色结点为hb个e f不变还是hb-1个。②采取措施先以p为旋转点左单旋变色再以g为旋转点右单旋最后的树显然符合规则4搞定。3代码实现if(uncleuncle-_colRED){//特别处理1}else{if(gparent-_leftparentparent-_leftcur){//特别处理2}elseif(gparent-_rightparentparent-_rightcur){//特别处理2}elseif(gparent-_leftparentparent-_rightcur){_RotateL(parent);cur-_colBLACK;gparent-_colRED;_RotateR(gparent);}else{_RotateR(parent);cur-_colBLACK;gparent-_colRED;_RotateL(gparent);}}2.2.4 整体代码boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);_root-_colBLACK;returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_leftcur;}else{parent-_rightcur;}cur-_parentparent;// change colourwhile(parentparent-_colRED){Node*gparentparent-_parent;Node*unclenullptr;//给uncle赋值if(gparent-_leftparent){unclegparent-_right;}else{unclegparent-_left;}//分情况特殊处理if(uncleuncle-_colRED){parent-_colBLACK;uncle-_colBLACK;gparent-_colRED;}else{if(gparent-_leftparentparent-_leftcur){_RotateR(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_rightparentparent-_rightcur){_RotateL(gparent);parent-_colBLACK;gparent-_colRED;}elseif(gparent-_leftparentparent-_rightcur){_RotateL(parent);cur-_colBLACK;gparent-_colRED;_RotateR(gparent);}else{_RotateR(parent);cur-_colBLACK;gparent-_colRED;_RotateL(gparent);}}//循环继续的要点cur跟parent需要更新curgparent;parentcur-_parent;}_root-_colBLACK;returntrue;}为了保证_root是黑的最后可以直接不管三七二十一给它赋值一下。2.3 红黑树的验证分别检查4条规则。boolIsRBTree(){if(_rootnullptr){returntrue;}if(_root-_col!BLACK){returnfalse;}intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}return_check(_root,refNum,0);}先处理树为空_root为空的情况。规则①检查_root是否为黑。用refNum记录一条路径从_root到空结点的黑色结点备用。进入_check函数。bool_check(Node*root,constintrefNum,intblackNum){if(rootnullptr){if(blackNum!refNum){coutrefNum:refNum; blackNum:blackNumendl;returnfalse;}returntrue;}if(root-_colBLACK){blackNum;}elseif(root-_colRED){if(root-_parent-_colRED){coutred node has red parentendl;returnfalse;}}else{coutillegal colourendl;returnfalse;}return_check(root-_left,refNum,blackNum)_check(root-_right,refNum,blackNum);}进入函数先检查root是否为空。规则④若为空则结束一条路径需要检查这条路径的黑色结点数量blackNum是否与参考数量refNum相等。若不相等则违反规则④返回false相等则返回true。root不为空则判断当前root是否为黑。root为黑则blackNum。规则③root为红则判断其parent是否为红为红违反规则③返回false。规则②若root既不为黑也不为红违反规则②返回false。再递归检查root-_left跟root-_right。2.4 红黑树的查找跟AVL树一样。Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}直接照搬过来。2.5 红黑树的删除2.5.1 删除指定节点不细究比较复杂可以放一份思路步骤操作说明找真正删除节点 y若 z 有两个孩子用中序后继替换也可用前驱最终 y 一定只有 0 或 1 个孩子。替换用 y 的孩子x可能为空顶替 y 的位置并记录 y 在父节点中的左右方向isLeft。关键判断只有删除的节点y是黑色时才需要调用deleteFixup因为删除红节点不影响黑色路径。修复循环核心是处理“双黑”节点即替代上来的节点 x。1.兄弟为红→ 旋转父节点转为兄弟为黑的情况。2.兄弟为黑且其两个子节点均为黑→ 兄弟变红将双黑往上移。3.兄弟为黑且远端侄子为黑近端为红→ 旋转兄弟转为情况4。4.兄弟为黑且远端侄子为红→ 旋转父节点并着色直接结束。收尾循环结束后将当前节点x涂黑若 x 为空则忽略彻底消去双黑。2.5.2 析构加一个析构函数防止内存泄漏public://...~RBTree(){_Destroy(_root);_rootnullptr;}private:void_Destroy(Node*root){if(rootnullptr){return;}_Destroy(root-_left);_Destroy(root-_right);deleteroot;}//...辅助函数_Destroy写在private区域以便递归销毁。2.6 测试voidTestRBTree01(void){wyzy::RBTreeint,intt;//1测试用例不涉及双旋//int a[] { 18, 10, 6, 15, 30, 25, 40 };//2测试用例涉及双旋inta[]{18,10,6,15,30,25,40,27};for(autoe:a){t.Insert({e,e});}t.inOrder();t.preOrder();coutt.IsRBTree()endl;}测试代码仅供参考。这里我写了inOrder跟preOrder方便打印观察。颜色打印出来0代表红1代表黑。最终测试结果符合预期。红黑树的学习就到这里下一篇我们要 封装红黑树 实现容器mymap跟myset 很快会更出来~