红黑树详解从四大规则到插入、旋转与验证实现文章目录红黑树详解从四大规则到插入、旋转与验证实现一、红黑树的基本概念二、红黑树的四条核心规则1 每个结点不是红色就是黑色2 根结点必须是黑色3 红色结点不能连续出现4 从任意结点到 NULL 的所有路径都包含相同数量的黑色结点三、为什么红黑树能够保持接近平衡四、红黑树的时间复杂度五、红黑树的结点结构六、为什么红黑树需要 parent 指针七、红黑树插入的基本思路第一步第二步第三步八、插入之后需要关注什么情况一父亲是黑色九、情况二父亲是红色十、情况一叔叔为红 —— 变色十一、为什么叔叔为红时只需要变色十二、为什么最终需要把根变成黑色十三、情况二叔叔不存在或者为黑色十四、单旋 变色1 左左情况2 右右情况十五、双旋 变色左右情况十六、右左情况十七、四种插入调整情况十八、红黑树插入代码的核心框架十九、插入调整的核心代码逻辑二十、红黑树的查找二十一、红黑树为什么需要验证二十二、红黑树规则验证1 颜色是否合法2 检查根是否为黑色3 检查是否存在连续红色结点二十三、检查每条路径的黑色结点数量二十四、如何得到参考黑色结点数量二十五、Check 函数的核心思想二十六、IsBalance 的实现二十七、红黑树插入的整体流程二十八、红黑树与 AVL 树的核心区别AVL 树红黑树二十九、红黑树删除红黑树是一种特殊的二叉搜索树它通过给每个结点增加一个颜色属性并利用颜色规则约束树的结构从而让整棵树保持接近平衡的状态相比 AVL 树红黑树对于平衡的控制没有那么严格因此在插入和删除过程中通常需要更少的旋转操作一、红黑树的基本概念红黑树本质上是一棵二叉搜索树它和普通二叉搜索树最大的区别就是每个结点除了保存key/value、左右孩子、父亲指针等信息之外还需要保存一个颜色颜色只有两种RED BLACK通过对从根结点到 NULL 结点的路径进行颜色约束红黑树能够保证最长路径不会超过最短路径的两倍因此整棵树不会退化得过于严重红黑树的核心并不是严格追求左右子树高度相等而是通过颜色规则限制树的高度二、红黑树的四条核心规则红黑树最重要的就是下面四条规则1 每个结点不是红色就是黑色每个结点只能拥有两种颜色之一RED BLACK通常可以使用枚举表示enumColour{RED,BLACK};2 根结点必须是黑色红黑树的根结点必须为黑色黑 / \ 红 黑因此在插入结束之后一般还需要保证_root-_colBLACK;3 红色结点不能连续出现如果一个结点是红色那么它的两个孩子必须是黑色也就是说红色结点的父亲不能是红色例如下面这种情况是不允许的黑 \ 红 \ 红因为出现了连续的红色结点而下面这种情况是允许的黑 \ 红 \ 黑这个规则非常重要因为它限制了红色结点连续出现从而限制了树的高度4 从任意结点到 NULL 的所有路径都包含相同数量的黑色结点假设从某个结点出发root / \ A B / \ / \ NULL NULL NULL NULL那么从root到所有 NULL 结点的路径中黑色结点的数量必须相同这个数量可以理解为黑高度black height例如黑 / \ 红 黑 / \ / \ 黑 黑 黑 红只要从同一个结点出发到所有 NULL 结点的路径中黑色结点数量一致就满足这条规则三、为什么红黑树能够保持接近平衡红黑树的平衡主要依赖两条规则第一条关键限制来自黑色结点数量相同根据规则 4从根到 NULL 的所有路径都必须拥有相同数量的黑色结点因此如果最短路径主要由黑色结点组成那么它的长度可以记作bh其中bh表示黑高度第二条关键限制来自不能出现连续红色结点因为红色结点不能连续出现所以一条最长路径最多只能形成这样的结构黑 红 黑 红 黑 红 ...因此最长路径的长度最多是2 * bh于是可以得到bh h 2 * bh其中h 表示某条路径的长度 bh 表示黑高度所以红黑树虽然不能保证像完全平衡树一样严格平衡但能够保证最长路径不会超过最短路径的两倍这就是红黑树能够保持较好性能的根本原因四、红黑树的时间复杂度假设红黑树中有N个结点由于红黑树的高度满足对数级别关系因此h O(logN)而二叉搜索树的查找、插入等操作都主要依赖树的高度所以红黑树中的查找 插入 删除在最坏情况下都能够保持O(logN)需要注意的是红黑树和 AVL 树的时间复杂度都属于O(logN)级别区别主要在于平衡策略AVL 树对平衡要求更加严格红黑树对平衡要求相对宽松因此在插入相同数量结点的情况下红黑树通常需要更少的旋转操作五、红黑树的结点结构红黑树结点除了保存键值和左右孩子之外还需要保存父亲指针以及颜色一种典型的结构如下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),_col(RED){}};这里有几个关键成员_kv保存键值对_left指向左孩子_right指向右孩子_parent指向父结点_col保存当前结点颜色六、为什么红黑树需要 parent 指针红黑树在调整过程中经常需要判断当前结点 c 父亲结点 p 祖父结点 g 叔叔结点 u其中最重要的关系是g / \ p u / c插入之后需要不断向上判断父亲和祖父的颜色如果没有_parent从当前结点向上寻找父亲和祖父会比较麻烦因此红黑树实现通常会保存父亲指针七、红黑树插入的基本思路红黑树插入本质上仍然按照二叉搜索树的规则进行基本过程可以分成几个步骤第一步按照二叉搜索树的规则找到新结点应该插入的位置第二步如果是空树新结点直接成为根结点并设置为黑色_rootnewNode(kv);_root-_colBLACK;第三步如果不是空树新插入的结点设置为红色cur-_colRED;为什么新结点默认设置为红色因为如果新插入结点直接设置成黑色那么从根到 NULL 的某些路径黑色结点数量会增加从而直接破坏规则 4而插入红色结点不会增加路径上的黑色结点数量因此红色更加容易维护红黑树的平衡规则八、插入之后需要关注什么新结点插入之后首先观察它的父亲颜色假设c 当前结点 p parent g grandfather u uncle情况一父亲是黑色例如黑 / 红新插入结点是红色父亲是黑色不存在连续红色结点同时没有增加路径上的黑色结点数量因此不需要调整插入结束九、情况二父亲是红色例如g 黑 / p 红 / c 红此时出现了红 红连续红色结点违反规则 3这时候需要进一步查看叔叔结点u根据叔叔结点的颜色可以分成两大类叔叔为红或者叔叔不存在 / 叔叔为黑十、情况一叔叔为红 —— 变色结构可以抽象为g 黑 / \ p 红 u 红 / c 红此时处理方式非常简单将p - 黑 u - 黑 g - 红也就是parent-_colBLACK;uncle-_colBLACK;grandfather-_colRED;然后把g当成新的当前结点继续向上处理curgrandfather;parentcur-_parent;十一、为什么叔叔为红时只需要变色原来的结构g 黑 / \ p 红 u 红 / c 红将p和u变成黑色g 红 / \ p 黑 u 黑 / c 红这样就解决了c和p连续为红色的问题同时由于左右两边都增加了一个黑色结点所以黑色结点数量仍然能够保持一致但是g被变成红色之后如果g的父亲也是红色那么又会产生新的连续红色问题所以需要继续向上处理十二、为什么最终需要把根变成黑色假设不断向上变色g / ...可能最终把根变成红色但是红黑树要求根必须是黑色因此插入结束后统一执行_root-_colBLACK;这样可以保证规则 2十三、情况二叔叔不存在或者为黑色此时单纯依靠变色无法解决连续红色的问题例如g 黑 / p 红 / c 红如果只把p变黑虽然连续红色问题解决了但是整体结构还需要调整才能保持黑色数量关系因此需要旋转 变色根据p和c的位置关系又可以分为单旋 变色 双旋 变色十四、单旋 变色单旋情况主要对应左左或者右右1 左左情况结构g / p / c其中g 黑 p 红 c 红处理方法以 g 为旋转点进行右旋旋转之后p / \ c g然后变色p - 黑 g - 红最终p 黑 / \ c 红 g 红对应代码RotateR(grandfather);parent-_colBLACK;grandfather-_colRED;处理结束不需要继续向上更新2 右右情况结构g \ p \ c这种情况与左左完全对称需要以 g 为旋转点进行左旋得到p / \ g c然后p - 黑 g - 红代码RotateL(grandfather);parent-_colBLACK;grandfather-_colRED;十五、双旋 变色双旋主要对应左右和右左左右情况结构g / p \ c这种情况下不能直接对g进行一次旋转解决需要进行两次旋转第一步以 p 为旋转点进行左旋得到g / c / p第二步以 g 为旋转点进行右旋最终c / \ p g然后c - 黑 g - 红对应代码RotateL(parent);RotateR(grandfather);cur-_colBLACK;grandfather-_colRED;十六、右左情况结构g \ p / c处理过程与左右情况对称第一步以 p 为旋转点进行右旋第二步以 g 为旋转点进行左旋最终c / \ g p然后c - 黑 g - 红对应代码RotateR(parent);RotateL(grandfather);cur-_colBLACK;grandfather-_colRED;十七、四种插入调整情况红黑树插入最核心的就是这四种情况情况结构处理叔叔为红p 红u 红变色并继续向上左左p 是 g 左孩子c 是 p 左孩子右旋 变色右右p 是 g 右孩子c 是 p 右孩子左旋 变色左右p 是 g 左孩子c 是 p 右孩子左旋 右旋 变色右左p 是 g 右孩子c 是 p 左孩子右旋 左旋 变色实际代码中通常只需要实现左边一套逻辑然后对右边情况进行镜像处理十八、红黑树插入代码的核心框架红黑树插入首先按照普通二叉搜索树进行查找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);cur-_colRED;cur-_parentparent;然后根据大小关系连接到父结点if(parent-_kv.firstkv.first){parent-_rightcur;}else{parent-_leftcur;}接下来进入红黑树调整阶段十九、插入调整的核心代码逻辑当父亲为红色时才需要处理while(parentparent-_colRED){Node*grandfatherparent-_parent;然后判断父亲是祖父的左孩子还是右孩子if(parentgrandfather-_left){Node*unclegrandfather-_right;// 叔叔为红if(uncleuncle-_colRED){parent-_coluncle-_colBLACK;grandfather-_colRED;curgrandfather;parentcur-_parent;}else{// 旋转 变色}}如果父亲是祖父的右孩子则进行镜像处理二十、红黑树的查找红黑树本质上还是二叉搜索树所以查找过程与普通二叉搜索树基本一致Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}判断逻辑非常简单如果当前 key 目标 key就向右走如果当前 key 目标 key就向左走如果相等returncur;如果最终走到 NULL说明没有找到由于红黑树高度是O(logN)所以查找复杂度为O(logN)二十一、红黑树为什么需要验证红黑树代码比较复杂尤其是插入过程涉及变色 左旋 右旋 双旋 父结点 祖父结点 叔叔结点因此实现完成之后需要验证红黑树是否仍然满足规则不能简单地只检查最长路径 最短路径 × 2因为即使满足这个条件也不代表红黑树的四条规则全部满足例如某棵树虽然高度看起来合理但可能存在红 红连续红色结点或者不同路径上的黑色结点数量不同这种树仍然不是合法的红黑树因此验证时应该直接检查红黑树的四条规则二十二、红黑树规则验证1 颜色是否合法由于颜色使用枚举定义enumColour{RED,BLACK};正常情况下结点颜色只能是这两种因此这一点由数据类型本身保证2 检查根是否为黑色直接判断if(_root-_colRED){returnfalse;}如果根是红色说明违反规则 23 检查是否存在连续红色结点一种比较方便的方式不是检查当前结点的两个孩子而是反过来检查当前结点和父亲if(root-_colREDroot-_parent-_colRED){returnfalse;}这样只需要判断当前结点 父亲结点就可以发现连续红色问题二十三、检查每条路径的黑色结点数量这是验证红黑树最关键的一步遍历过程中维护一个变量blackNum表示从根走到当前结点时遇到的黑色结点数量遇到黑色结点if(root-_colBLACK){blackNum;}当递归走到 NULL 时说明一条路径已经结束此时将当前路径的黑色结点数量与参考值进行比较if(refNum!blackNum){returnfalse;}只要存在一条路径的黑色结点数量不同就说明违反了规则 4二十四、如何得到参考黑色结点数量可以从根结点出发沿着左边一路走统计这条路径上的黑色结点数量intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}得到一个参考值refNum然后遍历整棵树要求所有路径最终统计出来的黑色结点数量都必须等于这个参考值二十五、Check 函数的核心思想boolCheck(Node*root,intblackNum,constintrefNum){if(rootnullptr){if(refNum!blackNum){cout存在黑色结点的数量不相等的路径endl;returnfalse;}returntrue;}if(root-_colREDroot-_parent-_colRED){coutroot-_kv.first存在连续的红色结点endl;returnfalse;}if(root-_colBLACK){blackNum;}returnCheck(root-_left,blackNum,refNum)Check(root-_right,blackNum,refNum);}这个函数主要完成两件事第一件事检查有没有连续红色结点第二件事检查所有路径上的黑色结点数量是否一致最终通过递归遍历整棵树完成验证二十六、IsBalance 的实现最终可以通过一个统一的接口检查红黑树boolIsBalance(){if(_rootnullptr)returntrue;if(_root-_colRED)returnfalse;intrefNum0;Node*cur_root;while(cur){if(cur-_colBLACK){refNum;}curcur-_left;}returnCheck(_root,0,refNum);}整个过程可以理解为检查空树 ↓ 检查根是否为黑 ↓ 计算参考黑色结点数量 ↓ 递归遍历整棵树 ↓ 检查连续红色 ↓ 检查每条路径黑色数量 ↓ 得到红黑树是否合法二十七、红黑树插入的整体流程完整的插入过程可以理解成下面这条主线按照二叉搜索树规则寻找插入位置 ↓ 创建新结点 ↓ 新结点设置为红色 ↓ 父亲是否为红色 ↙ ↘ 否 是 ↓ ↓ 结束 查看叔叔 ↓ ┌───────┴───────┐ ↓ ↓ 叔叔为红 叔叔黑/不存在 ↓ ↓ 变色 旋转 变色 ↓ ↓ 继续向上处理 结束 ↓ 最终保证根为黑色其中最重要的判断就是父亲颜色 ↓ 叔叔颜色 ↓ p、c 相对于 g 的位置二十八、红黑树与 AVL 树的核心区别两者都可以保证查找效率达到O(logN)但是平衡思想不同AVL 树AVL 树通过左右子树高度差控制平衡要求更加严格因此树更加接近严格平衡红黑树红黑树通过颜色规则间接控制平衡并不要求左右子树高度完全接近只要求满足四条红黑规则因此红黑树的平衡程度相对宽松对应的优点是插入过程中旋转次数通常更少可以简单理解为AVL 严格控制高度 红黑树 通过颜色间接控制高度二十九、红黑树删除当前内容中没有展开红黑树删除算法的具体实现红黑树删除比插入更加复杂相关内容可以参考《算法导论》 《STL源码剖析》因此当前实现重点放在红黑树规则 红黑树结构 红黑树插入 旋转与变色 红黑树查找 红黑树合法性验证