企业官网建设流程全解析

摘要：本文系统讲解红黑树插入操作中的调整方法，围绕节点命名、黑色高度（bh）等基础概念，重点分析插入后可能出现的六种情况。文章以叔叔节点（u）的存在性与颜色、以及相对位置（同侧异侧）为分类依据，逐一说明每种情况下的调整原则、旋转与变色方式，并总结出只有u为红时需要向上更新、只有u为红时需要检查特殊点等关键结论，帮助读者快速掌握红黑树插入调整的核心思路。

已有基础的同学可以先看总结部分，说不定会收获新的视角。

一、基础知识

1、命名

我们把插入的那个节点叫做孩子（child），其父节点就叫父亲（parent），父节点的兄弟节点叫做叔叔（uncle），父节点的父节点叫做祖父（grandparent）。此后，以上节点依次按英文缩写简称为：c、p、u、gp。以下图为例。

（填充黑色斜线的即为黑色节点，无填充的即为红色节点）

2、黑色高度（bh）

我们把某一条路径里的黑色节点数称为黑色高度（black height）。为了方便，简称为bh。注意区分：“高度”指的是该子树的最长路径节点数，此概念与黑色高度不相同。

3、调整

我们把插入新节点后，为了符合红黑树的四条定义而进行的，该树结构上的调整，简称成为调整。

4、*三个固定颜色

c一定为红（普适），p一定为红（需要调整时），gp一定为黑（普适）。理由如下：

1）c一定为红

由红黑树的定义可知，每条路径的黑节点数相同。对于一棵合法的红黑树，从根开始计算，每条路径的bh相同。易知，一个叶节点对应唯一一条路径。故当插入的节点为黑色时，对应的那一条路径的bh就会加一，这违反了“每条路径的bh相同“的定义。在插入黑节点的情况下，若想补救，只能在其他的所有路径上插入一个黑节点，才能保持每条路径的bh相同，不过这样显然不合理。

综上，不能插入黑节点，故c一定为红（普适：c只有为红的情况，不可能为黑）。

2）p一定为红

若p为黑，则在p上插入红节点和黑节点都合法，无需调整。所以需要调整时，p一定为红。

3）gp一定为黑

由于p一定为红，故若gp为红，则违反了“红色节点不能相邻出现”的定义。故gp一定为黑（普适：gp只有为黑的情况，不可能为红）。

二、插入的六种情况

1、*分类依据1——uncle

每一次调整都涉及四个节点——c、p、u、gp。而需要调整时，c、u、gp一定存在且颜色都已确定，所以只有u的存在及颜色不确定。

1）为什么u的存在不确定？

我们设插入的节点为c，而c一定有父节点（称作p），p一定有父节点（称作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）三个调整原则（重点切入口）

1. 解决红红冲突（需要进行调整的直接原因）。
2. 调整前后子树的bh不变（调整时的重点原则一）。由于插入前该树就是一棵合法的红黑树，所以，“调整后的树还是合法的红黑树”等价于“调整前后子树bh不变”。
3. 调整时，局部子树的左右子树高度差越小越好（调整时的重点原则二）。类似AVL树，若左右子树的高度差越大，则平衡性越差，越难达到合法。

2)特殊点（易错）

根一定为红，容易忽略，需要特殊讨论、特殊处理。

3）调整方式

旋转（单旋、双旋）、变色。

注：若要温故“旋转”知识点，建议复习AVL树。

4、分类

首先，根据“u的状态”，可以分为三大类：u为红、u为黑、u不存在。其次，再根据相对位置差异，每个大类又能分为两类：同侧异侧，综上，一共可以分为六类。

1）u为红

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为红就好。

2）u不存在

1>同侧

问题：c和p均为红，发生红红冲突，需要调整。（与前一情况相同）

目标：在保证该子树bh不变的情况下，解决红红冲突。（与前一情况相同）

*核心思路：单旋 + 变色 ---> 以gp为旋转轴心进行右单旋，再将p变黑，gp变红。

解析：若直接进行与前一情况相同的操作，最终会发现gp左右子树的bh不同，这是因为gp左右子树的高度差过大（类比AVL树），不利于“平衡”状态的产生，因此，我们进行与AVL树中相同的旋转操作。该例子中，左子树较高，故向右旋转。旋转过后，再进行与前一情况相同的变色操作，即可。（目前我们可以发现，右旋后的子树更加平衡，类似“u为红”的情况，只要通过变色就可以完成调整）

2>异侧

问题：c和p均为红，发生红红冲突，需要调整。（与前一情况相同）

目标：在保证该子树bh不变的情况下，解决红红冲突。（与前一情况相同）

*核心思路：双旋 + 变色 ---> 先以p为轴心进行左单旋，后以gp为轴心进行右单旋，再将p变黑，gp变红。

解析：异侧，相对位置不同，此时以p为轴心进行左旋，旋转结束就变成了“同侧”的情况，之后复现“同侧”情况的操作即可。（将陌生的情况向熟悉的情况靠拢，将未知变成已知）

3）u为黑

注意！u为黑的情况下，p和u一定不是原叶子节点，即p原本就有子树，而此时的c不是插入到叶子上的节点，而是通过“向上更新”更新出来的子节点。

为什么呢？因为u为黑但p为红，假设以u为根的子树的bh为h，则以p为根的子树bh一定为h+1（由“所有路径bh相同”可得），又因为c为红，所以c一定有左右子树且左右子树的bh都为h+1，同时p一定有右子树且bh为h+1。如下图：

那前两大类的情况下，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变红。

解析：左子树的高度为h+3，右子树的高度为h+1，左边较高，为了更接近“平衡”，以gp为轴进行右旋，减小左右子树高度差。接着，为了方便理解，可以把u节点与其子树归并，形成一个bh为h+1的子树。然后我们就会发现，只需要进行一次变色，就可以完成调整。

2>异侧

问题：c和p均为红，发生红红冲突，需要调整。（与前一情况相同）

目标：在保证该子树bh不变的情况下，解决红红冲突。（与前一情况相同）

*核心思路：双旋 + 变色 ---> 先以p为轴心进行左单旋，后以gp为轴心进行右单旋，再将p变黑，gp变红。

解析：对于异侧，此时以p为轴心进行左旋，即可把“异侧情况”转化成“同侧情况”，之后的思路与“同侧”一样。（依旧是将陌生的情况向熟悉的情况靠拢，将未知变成已知。所以实际上同侧和异侧的调整思路基本相同，只是差了一个转化的步骤）

5、总结

1）u的状态是分类依据。以“需要调整”为前提时，c、p、gp状态都确定，只需要注意u的存在性与颜色。

2）实际上六种情况的问题和目标都相同。问题都是“红红冲突”，目标都是“在保证子树bh不变的情况下，解决红红冲突”。

3）调整时，异侧只是比同侧多了一次单旋，除此之外，二者的调整方法完全一样。一次单旋，把”异侧”变为”同侧“，将复杂情况转化成简单情况。所以不要觉得有六种情况很复杂，实际上只有三种调整思路（调整方法上，异侧可以看成同侧，毕竟只需要一个单旋就能把异侧变成同侧）。

4）只有u为黑时，p原本一定是非叶节点，其他情况下p原本可能为叶节点、也可能不是。

5）只有u为红时需要向上更新。

6）只有u为红时需要检查新的局部根节点是不是特殊点，若是，则强行转黑。