红黑树

宋正兵 on 2021-05-13

红黑树

红黑树本质上是一种带颜色的二叉查找树,同时带有一定的规则,保证了一种平衡。

插入、查找、删除的时间复杂度是 $O(log n)$。

在 Java 集合框架中,HashMap、Tree Map、TreeSet 等都有红黑树的应用。

红黑树的性质

  1. 每个节点要么是黑色,要么是红色。
  2. 根节点是黑色。
  3. 所有的叶子节点都是黑色。(这里的叶子节点指的是为 null 的节点)
  4. 每个红色节点的两个子节点一定都是黑色的。
  5. 从任意一个节点到其子树的每个叶子节点的路径都包含相同数量的黑色节点。

注意:

对于性质 4,从每个根到节点的路径上不会有两个连续的红色节点,但黑色节点是可以连续的。因此若给定黑色节点的个数 N,最短路径的情况是连续的 N 个黑色,树的高度为 N - 1;最长路径的情况为节点红黑相间,树的高度为 2(N - 1) 。

红黑树的平衡插入

步骤:

  • 查找插入的位置;
  • 插入后调整结构保持平衡,包括对节点重新着色和对树进行相关的旋转操作。

思想

我们把要插入的节点设置为红色,这样插入后就不会影响性质 5,只需要专心调整性质 4 即可。我们只需要关心插入节点的父节点是否为红色,如果是红色,就要把父节点进行变化,让父节点变成黑色或者换一个黑色节点当父亲节点,当然这些操作不能同时影响不同路径上的黑色节点数的一致的原则。

实例

进行实例讲解前,约定如下:

下面的情况都属于父亲节点是祖先节点的左孩子,对于父亲节点是祖先节点的右孩子的情况是对称操作,就不多举例了。

情况1. 父亲节点和叔叔节点都是红色

情况2. 父亲节点为红色,叔叔节点为黑色或不存在

情况3. 对于情况 2 的拓展当前节点为父节点的右孩子

先对父亲节点进行左旋,让原来的父亲节点作为插入节点,使得插入节点变成父亲节点的左孩子,即得到情况 2,然后按照情况 2 处理。

红黑树的删除调整

删除

待删除节点按照孩子节点的个数分为三种情况:

  1. 待删除节点没有子节点, 则直接删除该节点;
  2. 待删除节点有一个子节点,则用该子节点替换它的父节点;
  3. 待删除节点有两个子节点,则取它的后继节点替换它,并删除这个后继节点原来的位置,它可能有两种情况:
    1. 后继节点是待删除节点的右孩子
    2. 后继节点不是待删除节点的右孩子

情况1 和情况 2

如果待删除节点的颜色是红色,直接删除无需调整;如果删除的节点是黑色的,则需要对红黑树进行调整。

情况 3

设待删除节点为 Z,后继节点为 Y。

如果后继节点 Y 是待删除节点 Z 的右子节点:用后继节点 Y 去替换待删除节点 Z。

如果后继节点 Y 不是待删除节点 Z 的右子节点:用后继节点 Y 去替换待删除节点 Z,然后用后继节点 Y 的右孩子 X 来填补节点 Y 的位置。由于移动后节点 Y 保持了原来节点 Z 的颜色,而节点 X 再替代 Y 节点之后可能会出现问题(当 Y 是黑色的时候),需要进行调整。

调整

如果删除节点的颜色是红色,从上面的节点到叶节点所经历的黑色节点没有变化,所以有一个前置条件就是待删除的节点是黑色的。这个原来是黑色的节点被删除后,我们要通过一定的变化,使得这棵树仍然是合法的红黑树。

情况1. 当前节点的兄弟节点是红色的

当前节点 x 的兄弟节点 w 是红色,那么从红黑树的属性来看,它的兄弟节点必然有两个黑色的子节点。那么我们就可以通过节点 x 的父亲节点左旋,然后将父亲节点 B 的颜色变成红色,原来兄弟节点 D 变成黑色。这样我们就能够转换成情况 2,为下一步调整做好准备。

情况2 当前节点的兄弟节点,包括兄弟节点的所有子节点都是黑色

这种情况下,我们将兄弟节点 w 设置为红色,然后将 x 节点指向它的父节点。

为什么这么一变就平衡了呢?假定节点 A 是要调整的节点一路调整过来的。因为原来那个要调整的节点是黑色的,它一旦被删除后该路径上的黑色节点就少了 1,所以这里节点 A 所在的路径都是黑色节点少 1。这里将节点 A 的兄弟节点变成红色后,从它的父节点到下面的所有路径就都统一少了 1,于是父亲节点 B 所在的路径都有了相同的黑色节点数量。

不用担心当前对于“一棵树中间的子树少了一个黑色节点”没办法保证整个红黑树的合理性,继续向上调整的过程中会对节点 B,也就是 x 所指向的这个节点设置为黑色,这样就保证前面亏的那一个黑色节点就补回来了。

情况3 当前节点的兄弟节点是黑色,且兄弟节点的左子节点是红色,右子节点是黑色

将兄弟节点 w 做一个右旋操作,转变成情况 4。

情况4 当前节点的兄弟节点是黑色,且兄弟节点的左子节点是任意颜色,右子节点是红色

将父节点 B 做一个左旋操作,同时将父亲节点 B 变成黑色,将原来的兄弟节点 D 变成红色,并且将 D 的右子节点变成黑色。这样保证了新的子树中间根节点到各叶子节点的路径依然是平衡的。然后直接将 x 指向其根节点。

为什么这一步调整结束后就直接 x = T.root了呢?也就是说我们一走完这个就可以把 x 直接跳到根节点,其他的都不需要看了。这是因为我们前面的一个前提,A 节点向上所在的路径都是黑色节点少了一个的,这里我们以调整之后相当于给它增加了一个黑色节点,同时对其他子树的节点没有任何变化。相当于我内部已经给它补偿上来了。所以后续就不需要再往上去调整。

前面讨论的这 4 种情况是在当前节点是父节点的左子节点的条件下进行的。如果当前节点是父节点的右子节点,则可以对应的做对称的操作处理,过程也是一样的。