al_06 红黑树

阅读数: 次 2020-06-25

如需转载，请根据 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议许可，附上本文作者及链接。
本文作者： 执笔成念
作者昵称： zbcn
本文链接： https://1363653611.github.io/zbcn.github.io/2020/06/25/al_06%E7%BA%A2%E9%BB%91%E6%A0%91/

概述

树

平衡二叉搜索树

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

二叉搜索树

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

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

平衡

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

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

改进二叉搜索树

当二叉树退化成链表时，性能是很低的，所以我们需要在结点的插入、删除操作之后，想办法让二叉搜索树恢复平衡（减小树的高度）。但是如果为了追求最理想的平衡，而增加了时间复杂度也不是很有必要，因此比较合理的方案就是：用尽量少的调整次数达到适度平衡。

由此引申出 AVL 树的概念。

AVL 树

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

平衡因子

平衡因子（Balance Factor）：某结点的左右子树的高度差。
每个叶子结点的平衡因子都是 0。看这棵二叉搜索树，红色数字标注了每个结点对应的平衡因子。

举例：

8 的左子树高度为 2，右子树高度为 1，因此它的平衡因子为 1；
5 的左子树高度为 0，右子树高度为 3,因此它的平衡因子为 -3
4 的左子树高度为 2，右子树高度为 4，因此它的平衡因子为 -2；

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

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

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

B 树

B 树（Balanced Tree）是一种平衡的多路搜索树，多用于文件系统、数据库的实现。这是一个简单的 3 阶 B 树：

特点

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 二叉搜索树

这是一棵二叉搜索树，通过某些父子结点合并，恰好能与上面的 B 树对应。我们可以得到结论：

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

红黑树

红黑树，本质上是一颗二叉查找树，但他在二叉查找树的基础上增加了着色和相关的性质，使得红黑树相对平衡，从而保证了红黑树的查找，插入，删除的复杂度最坏为O(log n).

如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢？这就引出了红黑树的5条性质.

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

红黑树的五条性质

每个节点要么是红的要么是黑的
根节点是黑色的
每个页节点（叶结点即指树尾端NIL指针或NULL结点）是黑色的
如果一个节点是红色的，则他们的儿子节点都是黑色的(红色结点不能连续（也就是，红色结点的孩子和父亲都是黑色）)
对任意以节点而言，其到叶节点树尾端NIL指针的每条路径都包含相同数量的黑节点

上文中我们所说的 “叶结点” 或”NULL结点”，它不包含数据而只充当树在此结束的指示，这些结点以及它们的父结点，在绘图中都会经常被省略。

红黑树与B树的等价变换

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

可以得出结论：

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

红黑树的基本操作

当我们对一棵平衡二叉搜索树进行插入、删除的时候，很可能会让这棵树变得失衡（最坏可能导致所有祖先结点失衡，但是父结点和非祖先结点都不可能失衡），为了达到平衡，需要对树进行旋转。而红黑树能够达到自平衡，靠的也就是左旋、右旋和变色。

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

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

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

左旋

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

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

右旋

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

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

总结

左旋和右旋知识详见 al_05_平衡二叉树的 @ 二叉树的修正机制章节;

变色

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

变换规则

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

变色：

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

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

左旋

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

右旋

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

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

红黑树搜索

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

具体步骤：

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

红黑树插入

具体步骤：

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

插入后实现自平衡

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

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

场景 1：红黑树为空树

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

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

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

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

处理：

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

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

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

处理：直接插入。

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

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

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

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

处理：

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

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

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

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

处理：

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

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

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

处理：

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

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

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

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

处理：

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

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

处理：

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

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

红黑树自平衡2

红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。

下来，将分析插入红色节点后红黑树的情况。这里假设要插入的节点为 N，N 的父节点为 P，祖父节点为 G，叔叔节点为 U。插入红色节点后，会出现5种情况，分别如下：

情况一

插入的新节点 N 是红黑树的根节点，这种情况下，我们把节点 N 的颜色由红色变为黑色，性质2（根是黑色）被满足。同时 N 被染成黑色后，红黑树所有路径上的黑色节点数量增加一个，性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍然被满足。

情况二

N 的父节点是黑色，这种情况下，性质4（每个红色节点必须有两个黑色的子节点）和性质5没有受到影响，不需要调整。

情况三

N 的父节点是红色（节点 P 为红色，其父节点必然为黑色），叔叔节点 U 也是红色。由于 P 和 N 均为红色，所有性质4被打破，此时需要进行调整。这种情况下，先将 P 和 U 的颜色染成黑色，再将 G 的颜色染成红色。此时经过 G 的路径上的黑色节点数量不变，性质5仍然满足。但需要注意的是 G 被染成红色后，可能会和它的父节点形成连续的红色节点，此时需要递归向上调整。

情况四

N 的父节点为红色，叔叔节点为黑色。节点 N 是 P 的右孩子，且节点 P 是 G 的左孩子。此时先对节点 P 进行左旋，调整 N 与 P 的位置。接下来按照情况五进行处理，以恢复性质4。

情况五

N 的父节点为红色，叔叔节点为黑色。N 是 P 的左孩子，且节点 P 是 G 的左孩子。此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色。经过这样的调整后，性质4被恢复，同时也未破坏性质5。

插入总结

上面五种情况中，情况一和情况二比较简单，情况三、四、五稍复杂。但如果细心观察，会发现这三种情况的区别在于叔叔节点的颜色，如果叔叔节点为红色，直接变色即可。如果叔叔节点为黑色，则需要选选择，再交换颜色。当把这三种情况的图画在一起就区别就比较容易观察了，如下图：

红黑树删除

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

定位删除的位置

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

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

删除后实现自平衡

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

场景一：若删除结点无子结点，直接删除即可；
场景二：若删除结点只有一个子结点，用子结点替换删除结点；
场景三：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点。

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

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

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

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

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

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

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

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

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

场景 1：替换结点为红色

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

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

场景 2：替换结点为黑色

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

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

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

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

处理：

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

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

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

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

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

处理：

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

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

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

处理：

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

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

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

处理：

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

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

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

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

处理：

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

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

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

处理

处理：

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

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

处理：

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

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

处理：

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

删除后自平衡2

相较于插入操作，红黑树的删除操作则要更为复杂一些。删除操作首先要确定待删除节点有几个孩子，如果有两个孩子，不能直接删除该节点。而是要先找到该节点的前驱（该节点左子树中最大的节点）或者后继（该节点右子树中最小的节点），然后将前驱或者后继的值复制到要删除的节点中，最后再将前驱或后继删除。由于前驱和后继至多只有一个孩子节点，这样我们就把原来要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题，问题被简化了一些。我们并不关心最终被删除的节点是否是我们开始想要删除的那个节点，只要节点里的值最终被删除就行了，至于树结构如何变化，这个并不重要。

红黑树删除操作的复杂度在于删除节点的颜色，当删除的节点是红色时，直接拿其孩子节点补空位即可。因为删除红色节点，性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点）仍能够被满足。

当删除的节点是黑色时，那么所有经过该节点的路径上的黑节点数量少了一个，破坏了性质5。如果该节点的孩子为红色，直接拿孩子节点替换被删除的节点，并将孩子节点染成黑色，即可恢复性质5。但如果孩子节点为黑色，处理起来就要复杂的多。分为6种情况，下面会展开说明。

在展开说明之前，我们先做一些假设，方便说明。这里假设最终被删除的节点为X（至多只有一个孩子节点），孩子节点为N，X的兄弟节点为S，S的左节点为 SL，右节点为 SR，接下来讨论是建立在节点 X 被删除，节点 N 替换X的基础上进行的。这里说明把被删除的节点X特地拎出来说一下的原因是防止大家误以为节点N会被删除，不然可能看不明白。

在上面的基础上，接下来就可以展开讨论了。红黑树删除有6种情况，分别是：

情况一

N 是新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。

上面是维基百科中关于红黑树删除的情况一说明，由于没有配图，看的有点晕。经过思考，我觉得可能会是下面这种情形：

要删除的节点 X 是根节点，且左右孩子节点均为空节点，此时将节点 X 用空节点替换完成删除操作。

情况二

S 为红色，其他节点为黑色。这种情况下可以对 N 的父节点进行左旋操作，然后互换 P 与 S 颜色。但这并未结束，经过节点 P 和 N 的路径删除前有3个黑色节点（P -> X -> N），现在只剩两个了（P -> N）。比未经过 N 的路径少一个黑色节点，性质5仍不满足，还需要继续调整。不过此时可以按照情况四、五、六进行调整。

情况三

N 的父节点，兄弟节点 S 和 S 的孩子节点均为黑色。这种情况下可以简单的把 S 染成红色，所有经过 S 的路径比之前少了一个黑色节点，这样经过 N 的路径和经过 S 的路径黑色节点数量一致了。但经过 P 的路径比不经过 P 的路径少一个黑色节点，此时需要从情况一开始对 P 进行平衡处理。

情况四

这里需要特别说明一下，上图中的节点 N 并非是新插入的节点。当 P 为红色时，P 有两个孩子节点，且孩子节点均为黑色，这样从 G 出发到各叶子节点路径上的黑色节点数量才能保持一致。既然 P 已经有两个孩子了，所以 N 不是新插入的节点。情况四是由以 N 为根节点的子树中插入了新节点，经过调整后，导致 N 被变为红色，进而导致了情况四的出现。考虑下面这种情况（PR 节点就是上图的 N 节点）：

如上图，插入节点 N 并按情况三处理。此时 PR 被染成了红色，与 P 节点形成了连续的红色节点，这个时候就需按情况四再次进行调整。

情况五

S 为黑色，S 的左孩子为红色，右孩子为黑色。N 的父节点颜色可红可黑，且 N 是 P 左孩子。这种情况下对 S 进行右旋操作，并互换 S 和 SL 的颜色。此时，所有路径上的黑色数量仍然相等，N 兄弟节点的由 S 变为了 SL，而 SL 的右孩子变为红色。接下来我们到情况六继续分析。

情况六

S 为黑色，S 的右孩子为红色。N 的父节点颜色可红可黑，且 N 是其父节点左孩子。这种情况下，我们对 P 进行左旋操作，并互换 P 和 S 的颜色，并将 SR 变为黑色。因为 P 变为黑色，所以经过 N 的路径多了一个黑色节点，经过 N 的路径上的黑色节点与删除前的数量一致。对于不经过 N 的路径，则有以下两种情况：

该路径经过 N 新的兄弟节点 SL ，那它之前必然经过 S 和 P。而 S 和 P 现在只是交换颜色，对于经过 SL 的路径不影响。
该路径经过 N 新的叔叔节点 SR，那它之前必然经过 P、 S 和 SR，而现在它只经过 S 和 SR。在对 P 进行左旋，并与 S 换色后，经过 SR 的路径少了一个黑色节点，性质5被打破。另外，由于 S 的颜色可红可黑，如果 S 是红色的话，会与 SR 形成连续的红色节点，打破性质4（每个红色节点必须有两个黑色的子节点）。此时仅需将 SR 由红色变为黑色即可同时恢复性质4和性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。）。

删除总结

红黑树删除的情况比较多，大家刚开始看的时候可能会比较晕。可能会产生这样的疑问，为啥红黑树会有这种删除情况，为啥又会有另一种情况，它们之间有什么联系和区别？和大家一样，我刚开始看的时候也有这样的困惑，直到我把所有情况对应的图形画在一起时，拨云见日，一切都明了了。此时天空中出现了4个字，原来如此、原来如此、原来如此。所以，请看图吧：

总结

红黑树是一种重要的二叉树，应用广泛，但在很多数据结构相关的书本中出现的次数并不多。很多书中要么不说，要么就一笔带过，并不会进行详细的分析，这可能是因为红黑树比较复杂的缘故。我在学习红黑树的时候也找了很多资料，但总体感觉讲的都不太好。尤其是在我学习删除操作的时候，很多资料是实在人看不下去，看的我很痛苦。直到我看到维基百科上关于红黑树的分析时，很是欣喜。这篇文章分析的很有条理，言简意赅，比很多资料好了太多。本文对红黑树的分析也主要参考了维基百科中的红黑树分析，并对维基百科中容易让人产生疑问和误解的地方进行了说明。同时维基百科中文版红黑树文中的图片较为模糊，这里我重新进行了绘制。需要说明的是，维基百科中文版无法打开了，文中关于维基百科的链接都是英文版的。另外在给大家推荐一个数据结构可视化的网站，里面包含常见数据结构可视化过程，地址为：t.cn/RZFgryr。

另外，由于红黑树本身比较复杂，实现也较为复杂。在写这篇文章之前，我曾尝试过用 Java 语言实现红黑树的增删操作，最终只写出了新增节点操作，删除没做出来。而且自己写的新增逻辑实在太繁琐，写的不好看，没法拿出来 show。所以最后把 Java 中的 TreeMap 增删相关源码拷出来，按照自己的需求把源码修改了一下，也勉强算是实现了红黑树吧。代码放到了 github 上，传送门 -> RBTree.java。

最后，如果你也在学习红黑树，希望这篇文章能够帮助到你。另外，由于红黑树本身比较复杂，加之本人水平有限，难免会出一些错误。如果有错，还望大家指出来，我们共同讨论。