摘要本文系统讲解红黑树插入操作中的调整方法围绕节点命名、黑色高度bh等基础概念重点分析插入后可能出现的六种情况。文章以叔叔节点u的存在性与颜色、以及相对位置同侧异侧为分类依据逐一说明每种情况下的调整原则、旋转与变色方式并总结出只有u为红时需要向上更新、只有u为红时需要检查特殊点等关键结论帮助读者快速掌握红黑树插入调整的核心思路。已有基础的同学可以先看总结部分说不定会收获新的视角。一、基础知识1、命名我们把插入的那个节点叫做孩子child其父节点就叫父亲parent父节点的兄弟节点叫做叔叔uncle父节点的父节点叫做祖父grandparent。此后以上节点依次按英文缩写简称为c、p、u、gp。以下图为例。填充黑色斜线的即为黑色节点无填充的即为红色节点2、黑色高度bh我们把某一条路径里的黑色节点数称为黑色高度black height。为了方便简称为bh。注意区分“高度”指的是该子树的最长路径节点数此概念与黑色高度不相同。3、调整我们把插入新节点后为了符合红黑树的四条定义而进行的该树结构上的调整简称成为调整。4、*三个固定颜色c一定为红普适p一定为红需要调整时gp一定为黑普适。理由如下1c一定为红由红黑树的定义可知每条路径的黑节点数相同。对于一棵合法的红黑树从根开始计算每条路径的bh相同。易知一个叶节点对应唯一一条路径。故当插入的节点为黑色时对应的那一条路径的bh就会加一这违反了“每条路径的bh相同“的定义。在插入黑节点的情况下若想补救只能在其他的所有路径上插入一个黑节点才能保持每条路径的bh相同不过这样显然不合理。综上不能插入黑节点故c一定为红普适c只有为红的情况不可能为黑。2p一定为红若p为黑则在p上插入红节点和黑节点都合法无需调整。所以需要调整时p一定为红。3gp一定为黑由于p一定为红故若gp为红则违反了“红色节点不能相邻出现”的定义。故gp一定为黑普适gp只有为黑的情况不可能为红。二、插入的六种情况1、*分类依据1——uncle每一次调整都涉及四个节点——c、p、u、gp。而需要调整时c、u、gp一定存在且颜色都已确定所以只有u的存在及颜色不确定。1为什么u的存在不确定我们设插入的节点为c而c一定有父节点称作pp一定有父节点称作gp故这三个点一定存在。但由于gp一定为黑p一定为红需要调整时所以就算u不存在从gp算起每条路径的bh也相同红黑树合法故u可以不存在。2为什么u的颜色不确定插入节点后的第一次调整时我们的视角聚焦在树的叶子部分。插入的节点称作c被插入的叶节点变成p再由p找到gp和u。由于红黑树定义的约束在需要调整的情况下原来作为叶节点的p一定是红色而gp一定是黑色此时u可以不存在每条路径的bh依旧相同但若u存在则只能是红色u为黑会导致其所在的路径bh变大违法。但注意这只是第一次调整是视角聚焦在叶子部分的情况还未发生向上更新。在后面的分类讨论中我们会遇到一种现象——“向上更新”。向上更新之后我们的视角会逐渐上移由叶子部分移动向根部分此时p节点不再是原来的“叶节点”而是变成了原来的“非叶节点”在这种情况下u可以为黑色。此处了解即可学习完后面的知识再回来理解2、*分类依据2——相对位置同侧异侧1含义理解若p是gp的左孩子且c是p的左孩子则“p与gp的相对位置”和“c与gp的相对位置”相同即相对位置相同称为同侧。同理若p是gp的右孩子且c是p的右孩子亦为同侧。例见下图若p是gp的左孩子但c是p的右孩子则“p与gp的相对位置”和“c与gp的相对位置”相异即相对位置不同称为异侧。同理若p是gp的右孩子且c是p的左孩子亦为异侧。例见下图2同侧异侧的意义此处了解即可学习完后面的知识再回来理解在后面的调整中同侧异侧会影响调整的方式。多数情况下就算u的状态包含两个性质存在与否、颜色相同同侧和异侧的区别也会使调整方式不同。3、*调整原则、特殊点及方式1三个调整原则重点切入口解决红红冲突需要进行调整的直接原因。调整前后子树的bh不变调整时的重点原则一。由于插入前该树就是一棵合法的红黑树所以“调整后的树还是合法的红黑树”等价于“调整前后子树bh不变”。调整时局部子树的左右子树高度差越小越好调整时的重点原则二。类似AVL树若左右子树的高度差越大则平衡性越差越难达到合法。2)特殊点易错根一定为红容易忽略需要特殊讨论、特殊处理。3调整方式旋转单旋、双旋、变色。注若要温故“旋转”知识点建议复习AVL树。4、分类首先根据“u的状态”可以分为三大类u为红、u为黑、u不存在。其次再根据相对位置差异每个大类又能分为两类同侧异侧综上一共可以分为六类。1u为红1同侧问题c和p均为红发生红红冲突需要调整。目标在保证该子树bh不变的情况下解决红红冲突。*核心思路变色--- 让gp变为红色p与u均变为黑色解析 要解决c和p的红红冲突因c不可以变成黑色会导致c所在路径bh加一bh发生变化故p一定得变黑色。而因p变黑导致p所在路径bh加一若要使调整后子树bh不变则必须让u也变黑同时gp变红。2异侧u为红的情况下异侧与同侧的问题、目标、解决思路相同。此处读者可模仿同侧的情况进行一次调整的推演。向上更新u为红的情况调整后新的局部根节点即调整后该子树的根节点此处称为nr为红。但旧的局部根节点gp为黑所以gp的父节点此处称为ggp可能是红也可能是黑。综上由于nr为红ggp可为红或黑所以二者可能产生新的“红红冲突”故需要把nr当成新的子节点c把ggp当成新的父节点p再次进行调整操作我们把这个更新的操作称为“向上更新”。若ggp为红则继续调整若ggp为黑则停止调整注意u为红时每次调整结束需要检查一下新的局部根节点是否是整棵树的根节点特殊点若是则要把该节点变黑红黑树定义之一根一定为黑。其他情况则不用检查因为其他情况调整结束后新的局部根节点为黑一定合法只有u为红时调整结束后新局部根节点为红可能违法。而其他情况调整后新的局部根节点均为黑色所以ggp不管是黑还是红都合法无需向上更新。只要记住需要向上更新的情况只有u为红就好。2u不存在1同侧问题c和p均为红发生红红冲突需要调整。与前一情况相同目标在保证该子树bh不变的情况下解决红红冲突。与前一情况相同*核心思路单旋 变色 --- 以gp为旋转轴心进行右单旋再将p变黑gp变红。解析若直接进行与前一情况相同的操作最终会发现gp左右子树的bh不同这是因为gp左右子树的高度差过大类比AVL树不利于“平衡”状态的产生因此我们进行与AVL树中相同的旋转操作。该例子中左子树较高故向右旋转。旋转过后再进行与前一情况相同的变色操作即可。目前我们可以发现右旋后的子树更加平衡类似“u为红”的情况只要通过变色就可以完成调整2异侧问题c和p均为红发生红红冲突需要调整。与前一情况相同目标在保证该子树bh不变的情况下解决红红冲突。与前一情况相同*核心思路双旋 变色 --- 先以p为轴心进行左单旋后以gp为轴心进行右单旋再将p变黑gp变红。解析异侧相对位置不同此时以p为轴心进行左旋旋转结束就变成了“同侧”的情况之后复现“同侧”情况的操作即可。将陌生的情况向熟悉的情况靠拢将未知变成已知3u为黑注意u为黑的情况下p和u一定不是原叶子节点即p原本就有子树而此时的c不是插入到叶子上的节点而是通过“向上更新”更新出来的子节点。为什么呢因为u为黑但p为红假设以u为根的子树的bh为h则以p为根的子树bh一定为h1由“所有路径bh相同”可得又因为c为红所以c一定有左右子树且左右子树的bh都为h1同时p一定有右子树且bh为h1。如下图那前两大类的情况下p和u一定是原来的叶节点吗不一定u为红的情况下可能是叶节点也可能不是而u不存在时一定是叶节点。理由如下u为红时由于p和u都为红所以p和u的子节点可以不存在也可以存在且为黑色。子节点不存在时p和u即为叶节点。子节点存在且为黑时以子节点为根可以形成子树此时p和u就是非叶节点。综上p和u可能是叶节点也可能不是。u不存在时p一定是叶节点。因为u不存在所以以u为根的右子树bh为0故以p为根的子树bh也为0即子树里不能有黑节点。同时p为红导致p的孩子不能为红否则引发红红冲突所以怕只能没有孩子进而导致p没有子树一定是叶子。综上p没有子节点p一定是叶节点。1同侧问题c和p均为红发生红红冲突需要调整。与前一情况相同目标在保证该子树bh不变的情况下解决红红冲突。与前一情况相同*核心思路单旋 变色 --- 以gp为轴心进行右单旋再将p变黑gp变红。解析左子树的高度为h3右子树的高度为h1左边较高为了更接近“平衡”以gp为轴进行右旋减小左右子树高度差。接着为了方便理解可以把u节点与其子树归并形成一个bh为h1的子树。然后我们就会发现只需要进行一次变色就可以完成调整。2异侧问题c和p均为红发生红红冲突需要调整。与前一情况相同目标在保证该子树bh不变的情况下解决红红冲突。与前一情况相同*核心思路双旋 变色 --- 先以p为轴心进行左单旋后以gp为轴心进行右单旋再将p变黑gp变红。解析对于异侧此时以p为轴心进行左旋即可把“异侧情况”转化成“同侧情况”之后的思路与“同侧”一样。依旧是将陌生的情况向熟悉的情况靠拢将未知变成已知。所以实际上同侧和异侧的调整思路基本相同只是差了一个转化的步骤5、总结1u的状态是分类依据。以“需要调整”为前提时c、p、gp状态都确定只需要注意u的存在性与颜色。2实际上六种情况的问题和目标都相同。问题都是“红红冲突”目标都是“在保证子树bh不变的情况下解决红红冲突”。3调整时异侧只是比同侧多了一次单旋除此之外二者的调整方法完全一样。一次单旋把”异侧”变为”同侧“将复杂情况转化成简单情况。所以不要觉得有六种情况很复杂实际上只有三种调整思路调整方法上异侧可以看成同侧毕竟只需要一个单旋就能把异侧变成同侧。4只有u为黑时p原本一定是非叶节点其他情况下p原本可能为叶节点、也可能不是。5只有u为红时需要向上更新。6只有u为红时需要检查新的局部根节点是不是特殊点若是则强行转黑。