认识二叉查找树

首先，红黑树是一种特别的二叉查找树，那么什么是二叉查找树呢？

一棵空树，或者是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 左、右子树也分别为二叉排序树；
4. 没有键值相等的结点。

红黑树的定义

红黑树是每个结点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1. 结点是红色或黑色；
2. 根是黑色；
3. 所有叶子都是黑色（叶子是NIL结点）；
4. 每个红色结点的子结点必为黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）；
5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。

下面是一个具体的红黑树的图例：

如上图，13 结点为根结点，为黑色（条件 2）。各个叶子结点都是黑色（条件 3）。不存在两个相连的红色结点（条件 4）。对于条件 5，我们以从 13 出发走向 17 结点及以后的路来看，有 6 条简单路径，每条简单路径中都包含3个黑色结点 「13-15-nil(L), 13-15-nil(R), 13-25-22-nil(L),13-25-22-nil(R),13-17-25-27-nil(L),13-17-25-27-nil(R) 」，无论哪一条路径，黑色结点数量都一样（条件 5）。

树的旋转

在讲解红黑树插入操作前，我们需要先了解一个操作 —— 树的旋转。

这里我们以二叉查找树为例。如以下动图，我们以图为例进行说明（Left Rotation 字幕出现后才开始左旋动画，Right Rotation 字幕出现后开始右旋动画，下方也附有静态图）：

首先要说明，二叉搜索树的旋转并不会影响二叉搜索树的性质，它旋转过后还是一棵二叉搜索树。旋转过程中也始终受二叉搜索树的主要性质约束：

• 右子结点比父结点大

• 左子结点比父结点小

以上图为例，首先在旋转之前，这棵二叉搜索树一定满足α<A<β<B<γ。

以右旋为例，进行右旋转时

• 首先向右旋转，根结点的左孩子将成为新的根结点，其左子树跟随它成为新的根结点的左子树，即如图，A 旋转后成为新的根结点，α 跟随 A 成为新的根结点左子树。

• 此时原根结点，也就是图中的 B 结点，下降成为 A 的右子树，而原来的 A 的右子树 β 将会移动成为 B 的左子树。此时仍旧满足α<A<β<B<γ.

而在这一过程中，整棵树一直遵守着前面提到的几个约束。相反的左旋转操作亦然。

同理我们再看看左旋，过程简单如下：

• A 下降成为左孩子，B 上升成为新的根结点，其右子树 γ 跟随其成为新根结点右子树，原先 B 的左子树 β 现在成为了 A 的右子树，变化前后均遵循α<A<β<B<γ.

附一张静态图方便理解：

红黑树的插入

以上完成了对二叉查找树以及树的旋转，下面我们正式进入红黑树操作的步骤。

插入的步骤主要为如下两大点：

1. 插入结点 Z 到合适位置并将其置为红色

2. 重新着色并旋转结点来解决违规问题

我们可以想到，插入结点必将打破平衡，而修复这些平衡并不是什么太困难的事情。

对于第二步，再插入结点 Z 后，可能有4种情况发生：

case1. 插入 Z 为根结点

case2. Z 的叔叔结点为红色

case3. Z 的叔叔结点为黑色，triangle 型

case4. Z 的叔叔结点为黑色，line 型

---

对于4种情况各自的处理方式

case1：我们仅仅需要做的操作就是将 Z 置为黑色

case2：我们将需要为 Z 的父结点、叔叔结点和爷爷结点重新着色

case3：情况如下图，所谓 triangle 型即 Z 和 Z 的父结点及爷爷结点形成三角形型：

遇到这种情况时候，我们需要对 Z 的父结点进行 Z 的相反方向旋转，如 Z 为左孩子，则将 A 向右旋转

case4：情况如下图，同理，line 型即 Z 和 Z 的父结点及爷爷结点在一条线上：

对于这种情况，我们将对 Z 的爷爷结点进行反方向旋转，如 Z 在右子树位置，将对 B 进行左旋。

然后再对其原父结点和原爷爷进行重新着色。

---

故对之前的 4 种情况，我们的处理分别为：

1. 插入 Z 为根结点  ➡ 置黑

2. Z 的叔叔结点为红色    ➡ 重新着色

3. Z 的叔叔结点为黑色，triangle型    ➡ 旋转 Z 的父结点

4. Z 的叔叔结点为黑色，line型    ➡ 旋转 Z 的爷爷结点并重新着色

---

一个????

以下是一个例子。现在，我们想要往如下红黑树中插入一个15结点：

(1) 首先，将插入的结点放入正确位置，并先另其为红色：

在这里，我们要使用一种方式 —— 将违规行为上移，满足 case2，重新着色三代。此时我们将 8 、11 结点置为黑色，将 10 结点置为红色。

经过操作后我们可以看到此时的违规行为转移到了 10 与 18 间，10 的叔叔结点为黑色，7 与 18 与 10 呈 triangle 型，满足 case3 ，这时我们要右旋 18 结点。

此时 7-10-18 构成了 case4 ，我们左旋违规行为起始点 18 的爷爷结点 7，并重新着色，可以得到最终结果。

现在这棵树已经是一棵红黑树了。

总结

红黑树的插入操作部分主要的难点在于理解左旋右旋和四种情况的考虑，在下一小节中我们将对删除操作进行详细讲解，并给出所有操作的示例代码。