“红黑树”，我一脸懵逼......

谁借莪１个温暖的怀抱￠ 2022-11-21 01:18 169阅读 0赞

51CTO   2020-04-01

红黑树(Red Black Tree)是一种自平衡的二叉搜索树(Self-balancing Binary Search Tree)。以前也叫做平衡二叉 B 树(Symmetric Binary B-tree)。

![面试被问“红黑树”，我一脸懵逼......][......]

图片来自 Pexels

**预备知识**

树的知识框架结构如下图所示：

![面试被问“红黑树”，我一脸懵逼......][...... 1]

**平衡二叉搜索树**

平衡二叉搜索树(Balanced Binary Search Tree)，英文简称 BBST。经典常见的平衡二叉搜索树是 AVL 树和红黑树。

**①二叉搜索树**

二叉搜索树(Binary Search Tree)是二叉树的一种，英文简称 BST。又称为二叉查找树、二叉排序树。

它的特点是任何一个结点的值都大于其左子树的所有结点的值，任何一个结点的值都小于其右子树的所有结点的值。

**②平衡**

平衡(Balance)：就是当结点数量固定时，左右子树的高度越接近，这棵二叉树越平衡(高度越低)。而最理想的平衡就是完全二叉树/满二叉树，高度最小的二叉树。

![面试被问“红黑树”，我一脸懵逼......][...... 2]

一棵二叉搜索树平均时间复杂度可以认为是树的高度 O(h)。像左边这棵，结点的左右子树的高度接近，属于一棵平衡二叉搜索树，O(h) = O(logn);而右边这棵，高度达到了最大，已经退化成了链表，O(h)=O(n)。

**③改进二叉搜索树**

当二叉树退化成链表时，性能是很低的，所以我们需要在结点的插入、删除操作之后，想办法让二叉搜索树恢复平衡(减小树的高度)。

但是如果为了追求最理想的平衡，而增加了时间复杂度也不是很有必要，因此比较合理的方案就是：用尽量少的调整次数达到适度平衡。

由此引申出 AVL 树的概念。

**AVL 树**

AVL 树是最早发明的自平衡二叉搜索树之一，它取名自两位发明家的名字：G.M.Adelson-Velsky 和 E.M.Landis。

平衡因子(Balance Factor)：某结点的左右子树的高度差。

每个叶子结点的平衡因子都是 0。看这棵二叉搜索树，红色数字标注了每个结点对应的平衡因子。

![面试被问“红黑树”，我一脸懵逼......][...... 3]

举例：8 的左子树高度为 2，右子树高度为 1，因此它的平衡因子为 1;5 的左子树高度为 0，右子树高度为 3，因此它的平衡因子为 -3;4 的左子树高度为 2，右子树高度为 4，因此它的平衡因子为 -2;

再看这棵 AVL 树和它每个结点对应的平衡因子：

![面试被问“红黑树”，我一脸懵逼......][...... 4]

可以看到 AVL 树具有以下特点：

*  每个结点的平衡因子只可能是 -1、0、1(如果绝对值超过 1，则认为是失衡)
 *  每个结点的左右子树高度差不超过 1
 *  搜索、插入、删除的时间复杂度是 O(logn)

**B 树**

B 树(Balanced Tree)是一种平衡的多路搜索树，多用于文件系统、数据库的实现。

这是一个简单的 3 阶 B 树：

![面试被问“红黑树”，我一脸懵逼......][...... 5]

特点如下：

*  1 个结点可以存储超过 2 个元素，可以拥有超过 2 个子结点
 *  拥有二叉搜索树的一些性质
 *  平衡，每个结点的所有子树高度一致
 *  比较矮

**①m 阶 B 树的性质(m ≥ 2)**

m 阶 B 树指的是一个结点最多拥有 m 个子结点。假设一个结点存储的元素个数为 x，那么如果这个结点是：

*  根结点：1 ≤ x ≤ m - 1
 *  非根结点：┌ m / 2 ┐ - 1 ≤ x ≤ m - 1

如果有子结点，子结点个数为 y = x + 1，那么如果这个结点是：

*  根结点：2 ≤ y ≤ m
 *  非根结点：┌ m / 2 ┐ ≤ y ≤ m

向上取整(Ceiling)，指的是取比自己大的最小整数，用数学符号 ┌ ┐ 表示;向下取整(Floor)，指的是取比自己小的最大整数，用数学符号 └ ┘ 表示。

比如 m=3，子结点个数 2≤y≤3，这个 B 树可以称为(2，3)树、2-3 树。

比如 m=4，子结点个数 2≤y≤4，这个 B 树可以称为(2，4)树、2-3-4 树。

比如 m=5，子结点个数 3≤y≤4，这个 B 树可以称为(3，5)树、3-4-5 树。

以此类推。

**②B 树 VS 二叉搜索树**

![面试被问“红黑树”，我一脸懵逼......][...... 6]

这是一棵二叉搜索树，通过某些父子结点合并，恰好能与上面的 B 树对应。

我们可以得到结论：

*  B 树和二叉搜索树，在逻辑上是等价的
 *  多代结点合并，可以获得一个超级结点，且 n 代合并的超级结点，最多拥有 (2^n) 个子结点 (至少是 (2^n) 阶 B 树)

**红黑树定义和性质**

**红黑树是一种含有红黑结点并能自平衡的二叉搜索树。**

为了保证平衡，红黑树必须满足以下性质：

*  **每个结点是要么是红色或黑色**
 *  **根结点必须是黑色**
 *  **叶结点(外部结点、空结点)是黑色**
 *  **红色结点不能连续(也就是，红色结点的孩子和父亲都是黑色)**
 *  **对于每个结点，从该点至 nil**(树尾端，Java 中为 null 的结点)**的任何路径包含黑色结点的个数都相同**

**红黑树与 B 树的等价变换**

![面试被问“红黑树”，我一脸懵逼......][...... 7]

根据上面的性质，可以画出这样一棵红黑树。接下来对红黑树做等价变换，即将所有的红色结点上升一层与它的父结点放在同一行，这就很像一棵 4 阶 B 树，转换效果如下图所示。

![面试被问“红黑树”，我一脸懵逼......][...... 8]

可以得出结论：

*  红黑树与 4 阶 B 树(2-3-4树)具有等价性
 *  黑色结点与红色子结点融合在一起，形成 1 个 B 树结点
 *  红黑树的黑色结点个数与 4 阶 B 树的结点总个数相等

**红黑树的基本操作**

当我们对一棵平衡二叉搜索树进行插入、删除的时候，很可能会让这棵树变得失衡(最坏可能导致所有祖先结点失衡，但是父结点和非祖先结点都不可能失衡)。

为了达到平衡，需要对树进行旋转。而**红黑树能够达到自平衡，靠的也就是左旋、右旋和变色。**

旋转操作是局部的。当一侧子树的结点少了，向另一侧“借”一些结点;当一侧子树的结点多了，则“租”一些结点给另一侧。

![面试被问“红黑树”，我一脸懵逼......][...... 9]

为了更清楚地讲解这部分内容，先声明几个概念：

*  N-node：当前结点
 *  P-parent：父结点
 *  S-sibling：兄弟结点
 *  U-uncle：叔父结点(P 的兄弟结点)
 *  G-grand：祖父结点(P 的父结点)

**左旋**

左旋指的是以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

![面试被问“红黑树”，我一脸懵逼......][...... 10]

不考虑结点颜色，可以看到左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树移动。

**右旋**

右旋指的是以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

![面试被问“红黑树”，我一脸懵逼......][...... 11]

不考虑结点颜色，可以看到右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树移动。

**变色**

变色指的是结点的颜色由红变黑或由黑变红。

**变换规则**

将左旋、右旋和变色结合起来，得到一套变换规则。

变色：如果当前结点的父结点和叔父结点是红色，那么：

*  把父结点和叔父结点变为黑色
 *  把祖父结点变为红色
 *  把指针定义到祖父结点

左旋：当前结点是右子树，且父结点是红色，叔父结点是黑色，对它的父结点左旋。

右旋：当前结点是左子树，且父结点是红色，叔父结点是黑色，那么：

*  把父结点变为黑色
 *  把祖父结点变为红色
 *  对祖父结点右旋

**红黑树搜索**

由于红黑树本来就是平衡二叉搜索树，并且搜索也不会破坏树的平衡，所以搜索算法也与平衡二叉搜索树一致：

![面试被问“红黑树”，我一脸懵逼......][...... 12]

具体步骤如下：

*  从根结点开始检索，把根结点设置为当前结点。
 *  若当前结点为空，返回 nil。
 *  若当前结点不为空，比较当前结点 key 与搜索 key 的大小。
 *  若当前结点 key 等于搜索 key，那么该 key 就是搜索目标，返回当前结点。
 *  若当前结点 key 大于搜索 key，把当前结点的左子结点设置为当前结点，重复步骤 2。
 *  若当前结点 key 小于搜索 key，把当前结点的右子结点设置为当前结点，重复步骤 2。

**红黑树插入**

红黑树插入操作分为下面两步：

**定位插入的位置**

![面试被问“红黑树”，我一脸懵逼......][...... 13]

具体步骤如下：

*  从根结点开始检索。
 *  若根结点为空，那么插入结点设为根结点，结束。
 *  若根结点不为空，那么把根结点设为当前结点。
 *  若当前结点为 nil，返回当前结点的父结点，结束。
 *  若当前结点 key 等于搜索 key，那么该 key 所在结点就是插入结点，更新结点的值，结束。
 *  若当前结点 key 大于搜索 key，把当前结点的左子结点设置为当前结点，重复步骤 4。
 *  若当前结点 key 小于搜索 key，把当前结点的右子结点设置为当前结点，重复步骤 4。

**插入后实现自平衡**

建议新添加的结点默认为红色，因此这样能够让红黑树的性质尽快满足。不过如果添加的结点是根结点，设为黑色即可。

总结一下红黑树插入可能出现的所有场景：

![面试被问“红黑树”，我一脸懵逼......][...... 14]

**①场景 1：红黑树为空树**

红黑树的性质 2：根结点必须是黑色。

处理：直接把插入结点设成黑色并作为根结点。

**②场景 2：插入结点的 key 已存在**

二叉搜索树中不能插入相同元素，既然结点的 key 已经存在，红黑树也已平衡，无需重复插入。

处理：

*  将插入结点设为将要替换结点的颜色
 *  更新当前结点的值为插入结点的值

**③场景 3：插入结点的父结点为黑色**

插入的结点默认是红色的，当它的父结点是黑色时，并不会破坏平衡。

处理：直接插入。

**④场景 4：插入结点的父结点为红色**

如果插入结点的父结点为红色，那么父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，后续的旋转操作需要祖父结点的参与。

**场景 4.1：存在叔父结点，且为红色**

由红黑树性质 4 可知：红色结点不能连续。那么此时该插入子树的红黑层数的情况是：黑-红-红。显然最简单的处理方式就是将其改为：红-黑-红。

![面试被问“红黑树”，我一脸懵逼......][...... 15]

处理：

*  将父结点和叔父结点变为黑色
 *  将祖父结点变为红色
 *  将祖父结点设置为当前插入结点

**场景 4.2：叔父结点不存在或为黑色，插入结点的父结点是祖父结点的左子结点**

这种场景下，叔父结点所在的子树的黑色结点就比父结点所在子树的多，不满足红黑树的性质 5。

**场景 4.2.1：插入结点是左子树**

![面试被问“红黑树”，我一脸懵逼......][...... 16]

处理：

*  将父结点变为黑色
 *  将祖父结点变为红色
 *  将祖父结点右旋

**场景 4.2.2：插入结点是左子树**

这种场景显然可以转换为 4.2.1。

![面试被问“红黑树”，我一脸懵逼......][...... 17]

处理：

*  将父结点进行左旋
 *  将父结点设为插入结点，得到场景 4.2.1
 *  进行场景 4.2.1 的处理

**场景 4.3：叔父结点不存在或为黑色，插入结点的父结点是祖父结点的右子结点**

相当于场景 4.2 的方向反转，直接看图。

**场景 4.3.1：插入结点是左子树**

![面试被问“红黑树”，我一脸懵逼......][...... 18]

处理：

*  将父结点变为黑色
 *  将祖父结点变为红色
 *  对祖父结点进行左旋

**场景 4.3.2：插入结点是右子树**

![面试被问“红黑树”，我一脸懵逼......][...... 19]

处理：

*  将父结点进行右旋
 *  将父结点设置为插入结点，得到场景 4.3.1
 *  进行场景 4.3.1 的处理

下面举个例子，往一棵红黑树中插入元素，整棵树的变换如下图所示：

![面试被问“红黑树”，我一脸懵逼......][...... 20]

**红黑树删除**

红黑树删除操作也分为两步：

**定位删除的位置**

定位删除位置可以复用红黑树搜索的操作。

如果不存在目标结点，忽略本次操作;如果找到目标结点，删除后进行自平衡处理。

**删除后实现自平衡**

二叉搜索树删除的时候可能出现三种场景：

*  若删除结点无子结点，直接删除即可。
 *  若删除结点只有一个子结点，用子结点替换删除结点。
 *  若删除结点有两个子结点，用\*\*后继结点(大于删除结点的最小结点)\*\*替换删除结点。

具体应用，可以借助这张图理解：

![面试被问“红黑树”，我一脸懵逼......][...... 21]

我们可以发现，另外两种二叉树的删除场景都可以通过相互转换变为场景一。

**在场景二情况下**：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为场景三，一直自顶向下转换，总是能转换为场景一。

**在场景三情况下**：删除结点用后继结点，如果后继结点有右子结点，那么相当于转换为场景二，否则转为场景一。

![面试被问“红黑树”，我一脸懵逼......][...... 22]

综上所述，删除的结点可以看作删除替换结点，且替换结点最后总是在树末。

下面总结一下红黑树删除可能出现的所有场景：

![面试被问“红黑树”，我一脸懵逼......][...... 23]

为了方面理解，我们先约定一下结点的叫法：

*  R：替换结点
 *  P：替换结点的父结点
 *  S：替换结点的兄弟结点
 *  SL：兄弟结点的左子结点
 *  SR：兄弟结点的右子结点
 *  灰色：结点颜色可能是红色，也可能是黑色

![面试被问“红黑树”，我一脸懵逼......][...... 24]

注意：R 是即将被替换到删除结点的位置的替换结点，在删除前，它还在原来所在位置参与树的子平衡，平衡后再替换到删除结点的位置，才算删除完成。

**①场景 1：替换结点为红色**

我们把替换结点换到了删除结点的位置时，由于替换结点为红色，删除也了不会影响红黑树的平衡，只要把替换结点的颜色变为删除的结点的颜色即可重新平衡。

处理：替换结点颜色变为删除结点的颜色。

**②场景 2：替换结点为黑色**

当替换结点是黑色时，就必须进行自平衡处理了，我们可以通过区分替换结点是其父结点的左子结点还是右子结点，来做不同的旋转，使树重新平衡。

**场景 2.1：替换结点是左子树**

**场景 2.1.1：替换结点的兄弟结点为红色**

若兄弟结点是红结点，那么根据红黑树性质 4，兄弟结点的父结点和子结点肯定为黑色，按照下图方式处理，得到删除场景 2.1.2.3。

![面试被问“红黑树”，我一脸懵逼......][...... 25]

处理：

*  将兄弟结点变为黑色
 *  将父结点变为红色
 *  对父结点进行左旋，得到场景 2.1.2.3
 *  进行场景 2.1.2.3 的处理

**场景 2.1.2：替换结点的兄弟结点为黑色**

当兄弟结点为黑时，其父结点和子结点的具体颜色也无法确定，此时又得考虑多种子场景。

**场景 2.1.2.1：替换结点的兄弟结点的右子结点为红色，左子结点任意颜色**

即将删除的左子树的一个黑色结点，显然左子树的黑色结点少 1 了，然而右子结点又是红色，那么我们直接向右子树“借”个红结点来补充黑结点，并进行旋转处理。

如图所示：

![面试被问“红黑树”，我一脸懵逼......][...... 26]

处理：

*  将兄弟结点的颜色变为父结点的颜色
 *  将父结点变为黑色
 *  将兄弟结点的右子结点变为黑色
 *  对父结点进行左旋

**场景 2.1.2.2：替换结点的兄弟结点的右子结点为黑色，左子结点为红色**

兄弟结点所在的子树有红结点，又可以向兄弟子树“借”个红结点过来，这就转换回了场景 2.1.2.1。

如图所示：

![面试被问“红黑树”，我一脸懵逼......][...... 27]

处理：

*  将兄弟结点变为红色
 *  将兄弟结点的左子结点变为黑色
 *  对兄弟结点进行右旋，得到场景 2.1.2.1
 *  进行场景 2.1.2.1 的处理

**场景 2.1.2.3：替换结点的兄弟结点的子结点都为黑色**

兄弟子树没有红结点可以“借”了，再向父结点“借”。如果父结点是黑色，为了让父结点在所在的子树中保证平衡(替换结点即将删除，少了一个黑色结点，子树也需要少一个)先把兄弟结点变为红色，再让父结点成为新的替换结点。

![面试被问“红黑树”，我一脸懵逼......][...... 28]

处理：

*  如果父结点为黑色：将兄弟结点变为红色;将父结点作为新的替换结点;重新进行删除结点的场景处理。
 *  如果父结点为红色：替换结点的父结点和替换结点的兄弟结点颜色交换;删除结点和替换结点的值交换后，删除替换结点。

**场景 2.2：替换结点是右子树**

实际上是场景 2.1 的镜像操作。

**场景 2.2.1：替换结点的兄弟结点为红色**

![面试被问“红黑树”，我一脸懵逼......][...... 29]

处理：

*  将兄弟结点变为黑色
 *  将父结点变为红色
 *  对父结点进行右旋，得到场景 2.2.2.3
 *  进行场景 2.2.2.3 的处理

**场景 2.2.2：替换结点的兄弟结点为黑色**

**场景 2.2.2.1：替换结点的兄弟结点的左子结点为红色，右子结点任意颜色**

![面试被问“红黑树”，我一脸懵逼......][...... 30]

处理：

*  将兄弟结点的颜色变为父结点的颜色
 *  将父结点变为黑色
 *  将兄弟结点的左子结点变为黑色
 *  对父结点进行右旋

**场景 2.2.2.2：替换结点的兄弟结点的左子结点为黑色，右子结点为红色**

![面试被问“红黑树”，我一脸懵逼......][...... 31]

处理：

*  将兄弟结点变为红色
 *  将兄弟结点的右子结点设为黑色
 *  对兄弟结点进行左旋，得到场景 2.2.2.1
 *  进行场景 2.2.2.1 的处理

**场景 2.2.2.3：替换结点的兄弟结点的子结点都为黑色**

![面试被问“红黑树”，我一脸懵逼......][...... 32]

处理：

*  **如果父结点为黑色**：将兄弟结点变为红色;将父结点作为新的替换结点;重新进行删除结点的场景处理。
 *  **如果父结点为红色**：替换结点的父结点和替换结点的兄弟结点颜色交换;删除结点和替换结点的值交换后，删除替换结点。

作者：fiteen

来源：掘金

[......]: /images/20221120/6f62f59e34d24ba798c1a20d293392f8.png
[...... 1]: /images/20221120/4d00e1b08de34f9d856ecc32da4e5126.png
[...... 2]: /images/20221120/1ebcff71f500490ba7ef38219f1ad1b2.png
[...... 3]: https://img-blog.csdnimg.cn/img_convert/b4af622c8f3ba1e0f3b41744c5a29ab3.png
[...... 4]: https://img-blog.csdnimg.cn/img_convert/9cb546cc51f6a725236101e3991edbd0.png
[...... 5]: https://img-blog.csdnimg.cn/img_convert/1b71a54e71f0a403e8f91821d37cbd54.png
[...... 6]: https://img-blog.csdnimg.cn/img_convert/d6a52257fe0198e12cce00233da0acb2.png
[...... 7]: https://img-blog.csdnimg.cn/img_convert/a9bbb13954b9158c75426093e012e2d1.png
[...... 8]: https://img-blog.csdnimg.cn/img_convert/2e98e760adaf5dbbe9ac2c497118b274.png
[...... 9]: https://img-blog.csdnimg.cn/img_convert/6246eb7903b165fe7aeeb7d2e5a4eb79.png
[...... 10]: https://img-blog.csdnimg.cn/img_convert/edc6d5ffb6cd25e8958cc687775b494a.png
[...... 11]: https://img-blog.csdnimg.cn/img_convert/dc631b688eb176c67934e561ce2fd49a.png
[...... 12]: https://img-blog.csdnimg.cn/img_convert/e900eaf78a4bb5979787858fa8ba4dda.png
[...... 13]: https://img-blog.csdnimg.cn/img_convert/64d9df022741f393c189886046eb949c.png
[...... 14]: https://img-blog.csdnimg.cn/img_convert/53e114dafbaa64e55951ad4889cc1980.png
[...... 15]: https://img-blog.csdnimg.cn/img_convert/7ab48dc1b61066b0deeb8f7c568bd6a9.png
[...... 16]: https://img-blog.csdnimg.cn/img_convert/2c780c89f3411df068a1a6f5c0100f79.png
[...... 17]: https://img-blog.csdnimg.cn/img_convert/3a6b58fea8b896e894e5083a4ecaea55.png
[...... 18]: https://img-blog.csdnimg.cn/img_convert/0fad9a2edc6bfd96a33b3955fd752cda.png
[...... 19]: https://img-blog.csdnimg.cn/img_convert/3b8dce088a08aa42be12185467e26d0a.png
[...... 20]: https://img-blog.csdnimg.cn/img_convert/247b843908a538890c0d77fc57296d88.png
[...... 21]: https://img-blog.csdnimg.cn/img_convert/9ee43f1020d356b8032bbb053de9969b.png
[...... 22]: https://img-blog.csdnimg.cn/img_convert/d4ce87d0e568ece29c6b39dd91337a5f.png
[...... 23]: https://img-blog.csdnimg.cn/img_convert/8af60ae63786435cd271fa182bcfc5e0.png
[...... 24]: https://img-blog.csdnimg.cn/img_convert/852a62f72e1c8df8c7841d0e144fbba8.png
[...... 25]: https://img-blog.csdnimg.cn/img_convert/31ccf390beca56c5de3ab456b83feb12.png
[...... 26]: https://img-blog.csdnimg.cn/img_convert/59220b293d189397cb900125b42a7c6e.png
[...... 27]: https://img-blog.csdnimg.cn/img_convert/6444d25516f75ee8073c3432b396e98f.png
[...... 28]: https://img-blog.csdnimg.cn/img_convert/32c4d0dd055d8f0bb0c04e683e6d4a11.png
[...... 29]: https://img-blog.csdnimg.cn/img_convert/4bf7d3e7dde7c903369d5bb889036304.png
[...... 30]: https://img-blog.csdnimg.cn/img_convert/35d0e03ec141c28689ccc314489e05e9.png
[...... 31]: https://img-blog.csdnimg.cn/img_convert/b258eb36c6676e72c4da35e3574456b3.png
[...... 32]: https://img-blog.csdnimg.cn/img_convert/3aabef3bd98698d5d26b06a7c47e846e.png