众里寻他，10亿数据中只需要进行10几次比较就能查找到目标，这便是红黑树的魅力所在。

Q:

  1. 红黑树是一种比较难的数据结构，要完全搞懂非常耗时耗力，红黑树怎么自平衡？
  2. 什么时候需要左旋或右旋？
  3. 插入和删除破坏了树的平衡后怎么处理？
先修知识点
  • 二叉查找树
  • 完美平衡二叉树

红黑树也是二叉查找树，我们知道，二叉查找树这一数据结构并不难，而红黑树之所以难是难在它是自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。想想场景就有点烦心。

红黑树定义和性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

  • 性质1：每个节点要么是黑色，要么是红色。
  • 性质2：根节点是黑色。
  • 性质3：每个叶子节点（NIL）是黑色。
  • 性质4：每个红色结点的两个子结点一定都是黑色。
  • 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

从性质5又可以推出：

  • 性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

图中就是一颗简单的红黑树。其中Nil为叶子结点，并且它是黑色的。(值得提醒注意的是，在Java中，叶子结点是为null的结点。)

红黑树并不是一个完美平衡二叉查找树，从图中可以看到，根结点 P 的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的。

亦即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡。

接着我们还来约定下红黑树一些结点的叫法，如图所示

前面讲到红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色。

  • 左旋： 以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
  • 右旋： 以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
  • 变色： 结点的颜色由红变黑或由黑变红。

在这里插入图片描述
$$
左旋
$$

在这里插入图片描述
$$
右旋
$$

上面所说的旋转结点也即旋转的支点，也即图中的P结点。

我们先忽略颜色，可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的。

  • 左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
  • 右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。

旋转操作是局部的。当一边子树的结点少了，那么向另外一边子树“借”一些结点；当一边子树的结点多了，那么向另外一边子树“租”一些结点。

注意：

但要保持红黑树的性质，结点不能乱挪，还得靠变色了。怎么变？具体情景又不同变法，后面会具体讲到，现在只需要记住红黑树总是通过旋转和变色达到自平衡。

Q:

  黑结点可以同时包含一个红子结点和一个黑子结点吗？

红黑树查找

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异：

  1. 从根结点开始查找，把根结点设置为当前结点；
  2. 若当前结点为空，返回null；
  3. 若当前结点不为空，用当前结点的 key 跟查找 key 作比较；
  4. 若当前结点 key 等于查找 key，那么该 key 就是查找目标，返回当前结点；
  5. 若当前结点 key 大于查找 key，把当前结点的左子结点设置为当前结点，重复步骤2；
  6. 若当前结点 key 小于查找 key，把当前结点的右子结点设置为当前结点，重复步骤2；

在这里插入图片描述
非常简单，但简单不代表它效率不好。

正由于红黑树总保持黑色完美平衡，所以它的查找最坏时间复杂度为 $O(2lgN)$，也即整颗树刚好红黑相隔的时候。能有这么好的查找效率得益于红黑树自平衡的特性。

红黑树插入

插入操作包括两部分工作

  • 一、查找插入的位置；
  • 二、插入后自平衡。

查找插入的父结点很简单，跟查找操作区别不大：

  1. 从根结点开始查找；
  2. 若根结点为空，那么插入结点作为根结点，结束。
  3. 若根结点不为空，那么把根结点作为当前结点；
  4. 若当前结点为null，返回当前结点的父结点，结束。
  5. 若当前结点key等于查找key，那么该key所在结点就是插入结点，更新结点的值，结束。
  6. 若当前结点key大于查找key，把当前结点的左子结点设置为当前结点，重复步骤4；
  7. 若当前结点key小于查找key，把当前结点的右子结点设置为当前结点，重复步骤4；

在这里插入图片描述
插入位置已经找到，把插入结点放到正确的位置就可以啦。

Q:
但插入结点是应该是什么颜色呢？

A:
红色。

理由：

红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

插入场景

在这里插入图片描述
根据二叉树的性质，除了情景2，所有插入操作都是在叶子结点进行的。这点应该不难理解，因为查找插入位置时，我们就是在找子结点为空的父结点的。

还是先做个约定：

插入情景1：红黑树为空树

最简单的一种情景，直接把插入结点作为根结点就行，但注意，根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。

处理： 把插入结点作为根结点，并把结点设置为黑色。

插入情景2：插入结点的Key已存在

插入结点的Key已存在，既然红黑树总保持平衡，在插入前红黑树已经是平衡的，那么把插入结点设置为将要替代结点的颜色，再把结点的值更新就完成插入。

处理：

  • 把I设为当前结点的颜色
  • 更新当前结点的值为插入结点的值

插入情景3：插入结点的父结点为黑结点

由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

处理： 直接插入。

插入情景4：插入结点的父结点为红结点

回想下红黑树的性质2：根结点是黑色。

如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，因为后续的旋转操作肯定需要祖父结点的参与。
情景4又分为很多子情景，下面将进入重点部分，各位看官请留神了。

插入情景4.1：叔叔结点存在并且为红结点

从红黑树性质4可以，祖父结点肯定为黑结点，因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。如图所示。

处理：

  • 将P和S设置为黑色
  • 将PP设置为红色
  • 把PP设置为当前插入结点

可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；但如果PP的父结点是红色，根据性质4，此时红黑树已不平衡了，所以还需要把PP当作新的插入结点，继续做插入操作自平衡处理，直到平衡为止。

试想下PP刚好为根结点时，那么根据性质2，我们必须把PP重新设为黑色，那么树的红黑结构变为：黑黑红。换句话说，从根结点到叶子结点的路径中，黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景。

我们还可以总结出另外一个经验：红黑树的生长是自底向上的。这点不同于普通的二叉查找树，普通的二叉查找树的生长是自顶向下的。

插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点

单纯从插入前来看，也即不算情景 4.1 自底向上处理时的情况，叔叔结点非红即为叶子结点(Nil)。因为如果叔叔结点为黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了，这不满足红黑树的性质5。后续情景同样如此，不再多做说明了。

前文说了，需要旋转操作时，肯定一边子树的结点多了或少了，需要租或借给另一边。插入显然是多的情况，那么把多的结点租给另一边子树就可以了。

插入情景4.2.1：插入结点是其父结点的左子结点

处理：

  • 将P设为黑色
  • 将PP设为红色
  • 对PP进行右旋

左边两个红结点，右边不存在，那么一边一个刚刚好，并且因为为红色，肯定不会破坏树的平衡。

Q:
 可以把P设为红色，I和PP设为黑色吗？

A:
 可以！看过《算法：第4版》的同学可能知道，书中讲解的就是把P设为红色，I和PP设为黑色。但把P设为红色，显然又会出现情景4.1的情况，需要自底向上处理，做多了无谓的操作。

插入情景4.2.2：插入结点是其父结点的右子结点

这种情景显然可以转换为情景4.2.1.

处理：

  • 对P进行左旋
  • 把P设置为插入结点，得到情景4.2.1
  • 进行情景4.2.1的处理

在这里插入图片描述

插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

该情景对应情景4.2，只是方向反转，不做过多说明了，直接看图。

插入情景4.3.1：插入结点是其父结点的右子结点

处理：

  • 将P设为黑色
  • 将PP设为红色
  • 对PP进行左旋
插入情景4.3.2：插入结点是其父结点的右子结点

处理：

  • 对P进行右旋
  • 把P设置为插入结点，得到情景4.3.1
  • 进行情景4.3.1的处理

在这里插入图片描述
Q:
 上面的情景举例的都是第一次插入而不包含自底向上处理的情况，那么上面所说的情景都适合自底向上的情况吗？

A:
 答案是肯定的。理由很简单，但每棵子树都能自平衡，那么整棵树最终总是平衡的。