红黑树?看这篇就G(够)了!


简介

红黑树(Red Black Tree,RBT)是一棵二叉搜索树(BST),每个结点都拥有自己的颜色,红色(Red)或者黑色(Black)

通过一些条件进行约束,红黑树达到了近似平衡

AVL 与红黑树的优缺点

  • 红黑树使用非严格的平衡换取增删结点时的旋转次数降低,而 AVL 严格平衡,意味着在增加或删除结点时,根据情况的不同,旋转的次数比红黑树要多
  • AVL 的结构相较于红黑树更为平衡,因此 AVL 的查询效率更高
  • 总体来说,红黑树的统计性能高于 AVL,但如果是频繁查询而少次增删的场景,使用 AVL 更加合适

正文

1. 红黑树的性质

1.1 结点的结构

属性

红黑树的每个结点包含 5 个属性:

  • color 结点的颜色
  • key 结点的大小(这个大小并不是数值上的大小,而是比较的大小)
  • left 左孩子结点
  • right 右孩子结点
  • p 父结点

相比于 AVL 树,红黑树的属性只增加了颜色 color

结构

他俩还有一个不同,AVL 以真实存在的结点作为叶子结点,而红黑树以空指针 NIL 作为叶子节点

如图所示,暂不考虑红黑树结点的颜色,只需明白 AVL 和红黑树在结构上的不同

图1.1.1

由于叶子结点 NIL 是个空指针,所以我们在作图时可以隐藏叶子结点。并将 NIL 视为外部结点,其他带有关键字 key 的结点视为内部节点

因此,图 1.1.1 中的红黑树可以简化为 图 1.1.2

图1.1.2

1.2 性质

性质

红黑树有以下五种性质

  1. 每个结点只能是红色或者黑色的
  2. 根节点是黑色的
  3. 每一个叶子结点(NIL)都是黑色的
  4. 如果一个结点是红色的,那么它的两个子节点都是黑色的
  5. 对任意结点,从该路径到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点

红黑树没有那么神秘,只要符合了这五条性质,就是一棵红黑树


对于性质 1,只要你不发病去搞个的结点,是不会被破坏的

性质2性质3,一来是不难记,二来的话在后面比较少提到(或者说已经默认了)

性质4性质5需要好好理解并记住,在插入删除部分会经常破坏这两个性质,只有理解了这两个性质才能更容易地阅读下文

黑高

黑高很重要,一定要充分理解了再往下看

图1.2.1就是一个红黑树的例子

图1.2.1

图中的数字表示从当前结点 x 到叶结点路径上经过的黑色结点数目(不包括当前结点),称为该结点的黑高(black-height),记为 $bh(x)$

根据性质5,黑高的值是明确的,因为从该结点出发,下降到叶结点的任意简单路径的黑色结点个数都相同

tips: 简单路径的意思是一路往下走,不能往上去父节点绕一圈


例如:

  • $bh(A) = 1$ ,因为只经过了一个 NIL。
  • $bh(C) = 2$,因为经过了 A 和 NIL / 或是 B 和 NIL
  • $bh(D) = 2$,因为不管走左边还是右边,都经过两个黑色结点

需要注意的是,计算黑高时不能将结点自身计算进去,这在黑高的定义中也明确声明了


由于我们通常将注意力放在红黑树的内部结点上,因为他们存储了关键字的值,所以在后面的图片中将忽略叶结点。如 图1.2.2

图1.2.2

再给出几张红黑树的图片理解一下性质

1.3 引理

引理:一棵有 n 个内部结点的红黑树的高度至多为 $2\lg(n + 1)$

关于红黑树的高度与时间复杂度(查找)的计算

1.3.2 是《算法导论》中的严格证明,1.3.1 是我自己的理解方式。

因为我觉得书中的证明并不好记,所以写到了后面

1.3.1 个人理解

(本节中“结点”指代“内部结点”,不包括 NIL)

目标:求得一棵 N 结点红黑树的时间复杂度

红黑树与 AVL 一样,都是自平衡的 BST,所以查找效率的计算方式一致

一棵高度为 h 的二叉搜索树(BST)上的搜索时间为 $O(h)$

那么 AVL 树的高度 $h = \lg(n)$,所以搜索时间为 $O(\lg n)$

而红黑树与 AVL 不同,不是绝对平衡的,所以 h 并不是一个固定的值,但却因为保持性质5,而拥有最大值。(不妨动手画一棵10个结点以上的红黑树,会发现高度不是能无限扩展的,否则性质5将被破坏)


那么第一步,我们将问题“N 结点的红黑树的时间复杂度是多少”转化成了“N 结点的红黑树的最大高度是多少”

目标:求得 N 结点红黑树的最大高度

直接求N 结点的红黑树的最大高度是困难的,我们换个思路。

根据性质5我们可以知道,红黑树的平衡与树的高度没有直接关系,而是与黑高息息相关。

而根据性质4,极端情况下,树的高度等于两倍的黑高(红黑交替),即 $h(x)_{max} = 2bh(x)$


那么又可以把目标换一换,换成求 N 结点红黑树的最大黑高

N 个结点堆成一棵树,路子可多了去了,到底什么情况下才能拥有最大的黑高,好求吗?不好求。

但是把这句话反过来看就容易多了。

求 N 结点红黑树的最大黑高,等价于,求黑高为 $bh(x)$ 的红黑树所包含的最少结点数

理解一下吧

下面开始计算


考虑到读者应该是初学红黑树,我再提示一下,黑高 $bh(x)$ 的计算并不包括 x 结点自身。

如下图中 $bh(c) = 1$ 不是因为 C 结点是黑结点,而是因为它的子节点 NIL 是黑色

图1.3.1.1

以 x 为根,黑高为 $bh(x)$ 的子树所包含的最少结点数

首先需要明确一个概念,虽然《算法导论》中没有指出,但是我们可以根据性质5自行证明:一棵全黑的红黑树必定是满二叉树

基于此,开始我们的计算过程

在这里,我把红黑树分为两种情况:

  1. 全黑
  2. 包含红色结点

那么我们需要分别计算这两种情况并取最小值

  1. 全黑

    上面指出了一棵全黑的红黑树必定是完全二叉树,所以黑高为 $bh(x)$ 的子树如果是全黑,那么它的结点数量是可以定量计算的。

    一棵高度 $h = bh(x)$ 的完全二叉树的结点数量 $N = 2^{bh(x) } - 1$

  2. 包含红色结点

    假设在第 k 层(k > 1,性质2) 出现了第一个红色结点

    • 那么这时 $bh(x) \ge k - 1$ ,同时结点数量 $N \ge 2^{k - 1}$ (当第 k 层只有一个内部结点且为红色时取等号)

    • 而如果是全黑的情况,在 $bh(x) = k - 1$ 的条件下,

      结点数量 $N = 2^{bh(x)} - 1 = 2^{k - 1} - 1$ ,一定小于上面的 2k - 1

所以可以得出结论:一棵黑高为 bh(x) 的树的结点数量 $N \ge 2^{bh(x)} - 1$

或许上面对于包含红色结点的情况描述的不容易理解,那么我再换一种方式:

  • 首先画出一棵 $bh(x) = k$ 的全黑 红黑树,在这里我将 k 取为 3

    如果想要保持黑高不变,并且添加红色结点

    要么在底层添加新的结点,要么将上面某个结点染红

    在底层添加红色结点势必增加结点数量,所以我们仅讨论染色的情况:

    任意挑选一个结点(不能是根节点 X)染红

    这时候黑高已经失衡了,所以我们需要向结点 6 和结点 9 添加黑色子节点才能保证黑高的平衡,而这也将增加结点的数量

    所以得出结论:一棵黑高为 $bh(x)$ 的树只有在结点全黑时拥有的结点数最少

    进而可以推断出:一棵黑高为 $bh(x)$ 的树的结点数量 $N \ge 2^{bh(x)} - 1 $

有了这个结论,我们就可以计算N 结点的红黑树的最大高度


得出结论:N 结点的红黑树最大高度是 $2\lg{(N + 1)}$

所以红黑树的搜索时间复杂度是 $O(\lg n)$

1.3.2 严格证明

以下内容出自(照搬) 《算法导论》第三版(机械工业出版社)

证明:一棵有 n 个内部结点的红黑树的高度至多为 2lg(n + 1)

先证明以任一结点 x 为根的子树中至少包含 $2^{bh(x)} - 1$ 个内部结点。要证明这点,需要对 x 的高度进行归纳。

如果 x 的高度为0,则 x 必为叶结点 NIL,且以 x 为根节点的子树至少包含 $2^{bh(x)} - 1 = 2^0 - 1 = 0$ 个内部结点。

对于归纳步骤,考虑一个高度为正值且有两个子结点的内部结点 x。每个子结点有黑高 $bh(x)$ 或 $bh(x) - 1$,其分别取决于自身的颜色是红还是黑。由于 x 子结点的高度比 x 本身的高度要低,可以 利用归纳假设得出每个子结点至少有 $2^{bh(x)} - 1$ 个内部结点的结论。

于是,以 x 为根的子树至少包含 $(2^{bh(x) - 1} - 1) + (2^{bh(x) - 1} - 1) + 1 = 2^{bh(x)} - 1$ 个内部结点,因此得证。


为完成引理的证明,设 h 为树的高度。根据性质4,从根到叶结点(不包括根节点)的任何一条简单路径上都至少有一半的结点为黑色。因此,根的高度至少为 h / 2;于是有

把 1 移到不等式的左边,再对两边取对数,得到 $\lg(n + 1) \ge h / 2$,或者 $h \le 2\lg(n + 1) $

由该引理可知,SEARCH 操作可在红黑树上在 $O(\lg n)$ 时间内执行,因为这些操作在一棵高度为 h 的二叉搜索树上的运行时间为 $O(h)$

2. 旋转

INSERT(插入)和 DELETE(删除)在含 n 个关键字的红黑树上,运行花费时间为 $O(\lg n)$。由于这两个操作对树做了修改,结果可能违反红黑树的性质。为了维护这些性质,必须要改变树种某些结点的颜色以及指针结构。

修改结点的颜色,称为染色,将在下面的插入删除部分细讲

关于旋转的操作,红黑树与 AVL 树一致,可以参考下面这篇文章

AVL平衡二叉树如何旋转 | Cimoc

3. 插入

3.1 纯纯的插入

单纯的插入很简单,和 BST 没什么区别,而修复平衡才是难点

不过这里有一个问题,插入的结点是什么颜色呢?

答案是红色,原因是,红色的“容错率”高

插入红色结点可能会破坏性质4,而插入黑色结点一定会破坏性质5

同时,红色结点在修复平衡时能起到非常大的作用

不多bb,我直接把插入的伪代码贴上来,同样出自《算法导论》,不过我会加上注释

/* 
 * 这部分代码的函数调用(方法名)是 RB-INSERT(T, z)
 * T 表示这棵树,z 是插入的结点
 * 由于是本文首次贴代码,所以声明一下,任一结点都包含以下5个属性
 * p: 父结点
 * left: 左子结点
 * right: 右子结点
 * key: 结点的关键值
 * color: 结点的颜色
 */

// y 用来指向我们插入 z 的位置的父节点
y = T.nil

// x 用来找我们要插入的位置,当然最后一定是指向 NIL的,与 BST 插入大同小异
x = T.root

// 都学红黑树了,不会不知道 BST 的插入是插到叶子结点吧,不会吧不会吧
while x ≠ T.nil
	// 既然 x 还没走到底,那么 y 也要同步走
	y = x
	
	// 根据关键值判断 x 到底走左子树还是走右子树
	if z.key < x.key
		x = x.left
	else 
		x= x.right

/* 
 * 跳出循环时,x 已经是 NIL 了,不参与接下来的操作
 * 不过 y 作为父节点还是需要参与一些指针的修改的
 * 首先是将 z 的父节点设置为 y
 */ 
z.p = y

// 如果 y 是 NIL,说明根本就没进上面的循环,即树 T 是空的
if y == T.nil
	// 那么这时候就得将树的根节点设置为 z
	T.root = z

// 否则的话根据关键值判断,z 是 y 的左节点还是有结点
elseif z.key < y.key
	y.left = z
else
	y.right = z

// z 是新插入的结点,所以两个孩子结点都得是 NIL
z.left = T.nil
z.right = T.nil

// 新插入的结点设置为红色
z.color = RED

// 虽然没破坏性质5,但是可能会破坏性质4,即出现连续的红色结点
// 所以要调用平衡的修复算法,见下一节 3.2 平衡修复
RB-INSERT-FIXUP(T, z)

3.2 平衡修复

叔节点与祖父结点

父节点是什么意思不用我多讲了,这里我再给出两个名词:叔结点祖父结点

叔结点:父节点的兄弟结点

祖父结点:父节点的父节点

失衡原因

根据 3.1 中的伪代码,应该不难发现造成失衡的原因只有一个就是破坏了性质4,出现了连续的红色结点。也就是当前结点父节点同时为红色

根据性质4,可以确定的是这时候祖父节点一定为黑色,那么不确定的只有叔结点

根据性质1,结点只有两种颜色,所以我们可以简单地将情况分为以下两种:

  1. 叔结点为红色

  2. 叔结点为黑色

  • 不要再问没有叔结点怎么办啦!!!

    没有作为“内部结点”叔结点,那叔结点不就是 NIL 吗,还是黑色呀

  • 也不要再问父节点是黑色怎么办啦!!!

    父节点是黑色又没有失衡,那不是最好吗,一个性质都没有打破

  • 更不要再问没有祖父结点怎么办啦!!!没有祖父结点就意味着父节点是根节点,那父节点一定是黑色,这次插入不会失衡

接下来来讨论这两种情况的处理方案,如何重新维护红黑树的平衡

由于二叉树的对称性,反转左右后的代码几乎相同,下面只介绍父节点祖父结点的左孩子的情况。

3.2.1 case 1 叔结点为红色

这种情况的处理方式十分简单,也很好理解。我们先梳理一下目前的信息:

  1. 父节点与叔结点为红色
  2. 祖父结点为黑色

那么不是就简单了吗,将这两层(不是指整棵树,仅仅是这棵子树的两层)颜色互换不就好了。

这样的话不仅黑高没有变化,连当前结点父节点的颜色冲突也解决了。

不过新的问题也随之而来,祖父结点突然变成红色了,万一它的父节点也是红色,那不是又违反性质4了?

所以我们的 z 不能仅仅指向新增的结点,只要树还没平衡,我们的 z 就得移动到导致树失衡的点,上图中经过变换后,z 应该移动到结点 7

如果 z 移动后新的父节点是黑色,那么平衡修复成功

否则继续根据 z 的叔结点的颜色判断是 case 1 还是 case 2 进行平衡修复。

case 1 的解决方案治标不治本,除非你运气好,刚好没产生连续两个红色结点的冲突,但只要你还在往红黑树里插入结点,总会遇到这种情况的。


这种方法也是有它的作用的,它类似于递归,不断地向上层寻找 case 2 的情况,直到寻找到 case 2,那么就会进入我们的下一小节 3.2.2

然而,case 2 并不一定会出现,如果你的运气真的非常非常好,递归上去走到了根节点还是 case 1 的情况,那不就修复了树的平衡?

细心的你可能发现了,case 1 可能会把根节点 染红 ,又或者是在上面的插入过程中,插入的结点就是根节点,那它同样是红色的

根据性质2,无论何时,根节点一定是黑色的

由于根节点不参与黑高的计算,所以我们重新把根节点染黑也不会破坏红黑树的性质

就算,在另一个世界里的红黑树要计算根节点的黑高,那你说,我把根节点染黑了,左右子树新增的黑高还能不一样不成

用一段伪代码再来感受一下这个过程:

y = z.p.p.right
if y.color == RED
	z.p.color = BLACK
	y.color = BLACK
	z.p.p.color = RED
	z = z.p.p

3.2.2 case 2 叔结点为黑色

case 2 可比 case 1 复杂多了,不能用那种 “取巧“ 的方式来修复平衡,得实打实的用旋转了,既然要旋转,那么根据 z 的位置又得分两种情况

大家都知道 AVL 树有四种旋转方式:LL、LR、RR、RL

我们这里只讨论“父节点是祖父结点的左孩子”的情况,所以第一个方向一定是 L,那么还剩下两种旋转:LL、LR

另外两种刚好对称,不写了

tips: 旋转会影响黑高,对于可能拥有子树的结点,我会用希腊字母表示子树,同时 z 是会移动的,表示造成失衡的红色结点,而不单单是我们刚插入的结点

3.2.2.1 case 2.1—LL

已知:

  • LL 代表父节点祖父结点的左孩子,同时,当前结点 z 是父节点的左孩子
  • 父节点是红色,祖父结点叔结点是黑色

如下图 3.2.1 所示,是 case 2.1 情况下的失衡子树

图2.3.1

图中的黑高看起来失衡了,这是由于我们没有画出子树。

如果结点 z 是新插入的,那么原本的树就是平衡的,黑高也是平衡的。

如果结点 z 是通过 case 1 染红的,那么也没有影响黑高


那么现在的问题就是,如何在不影响这棵子树的黑高的情况下,修复性质4

理论阶段

BST 中我们不能任意移动结点,只能通过旋转的方式改变结点的相对位置。这也就意味着这两个红色结点无论如何都是相连的

(除非,你把他们的孩子结点转上来放俩人中间,直接破坏黑高,那可以当我没说。再说了,他们的子树也是我们在 case 1 中一步步平衡过来的,别想着去动了)

既然他俩是连体的,而 z 被染红是为了其子树的平衡,那么我们只有一条路可以走了,那就是将父节点 f 染黑

可这时候结点 g 的左右黑高就不平衡了,破坏了性质5,我们就需要借助旋转来修复了

开始修复

首先我们染黑结点 f,这一步不管早晚我们都得做,接下去就是解决左子树的黑高多了 1 的这个问题

接下来

不要再有染红祖父结点的冲动啦,这和 case 1 不一样

如果我们染红了祖父节点 g,不仅没有解决树的黑高问题,还使结点 g 可能与其父节点又产生了性质4上的冲突。

这样一来,哪怕我们修复了黑高,还得递归上去,这可不行。

所以我们要对结点 g 来一次 LL 旋转

这时候左子树的黑高问题被转移到了右子树,并且新的根节点 f 与原来一样是黑色,不会向上冲突。

接下来解决最后一个问题:右子树的黑高问题

右子树的这一部分结点可没有红色的,那就好办了

既然黑高多了 1,那找一个结点染红就行了,说的轻松,但是还是要注意细节

图中关于这几个内部结点的子树我并没有画出,但是我们也得考虑到它们

对比初始态(1)状态(3),不难发现经过 LL 旋转后,只有子树 α 变动了相对位置

它的简单路径从 黑->红->α 变成了 黑->黑->α,由于红色不参与黑高计算,相当于是多了一个黑

所以我们需要染红的结点是原本的祖父结点 g

染红了 g 之后,对于 y 来说,g 可以看做是不存在的,那么 y 的状态也和初始态相同

到这里,我们不仅修复了性质4,同时也保持了原有的黑高并且不会继续向上产生冲突,可以直接退出修复流程

再放张图对比下效果

说了这么多,总结起来其实就一句话

结论

如果祖孙三代连成一条向左的直线,且叔叔比较黑,那么我们染黑父节点,染红祖父结点,对祖父结点进行一次LL旋转

伪代码

z.p.color = BLACK
z.p.p.color = RED
LL(T, z.p.p)
// 算法导论中旋转方法的名称是 RIGHT-ROTATE,意为向右旋转
// 而我用 LL 这个名称表示路径的方向,实际的内部实现也是向右旋转
3.2.2.2 case 2.2—LR

开局一张图,内容全靠编

已知:

  • LR 代表父节点祖父结点的左孩子,同时,当前结点 z 是父节点的右孩子
  • 父节点是红色,祖父结点叔结点是黑色

3.2.2.1 中说的一样,父节点 f 是无论如何都得染黑

区别在于我们怎么旋转而已

对 AVL 旋转熟悉的读者应该记得,LR = RR + LL

试想一下,如果我们对父节点 f 进行一次 RR 旋转会发生什么

RR

由于父节点 f 迟早都得染黑,我们不急于一时,这样能更清晰地看到整棵子树的黑高变化

转之前我们分析一下:

由于结点 z 与结点 f 都是红色,那么它俩的子树 α、β、γ 在不考虑 BST 规则(左 < 中 < 右)的情况下,互换位置对于树的平衡没有任何影响

旋转是符合 BST 规则的

那么也就是说,我们对结点 f 进行一次 RR 旋转,其实相当于无事发生,任何性质都没有发生变化。

接下来就大胆地旋转吧!

到这一步感到熟悉吗,这就是 3.2.2.1 中的 LL 情况了

不过上图中 z 需要移动到 f 的位置(我还没有画出。真正旋转后的状态是 z 指向结点 5),记得在旋转前进行移动,因为代码实现简单。

完整的旋转过程如下图:

剩下的应该就不用我再讲一遍了

结论

如果祖孙三代形成一个小于号(LR),且叔叔比较黑,那么我们对父节点进行一次 RR 旋转,就变成了 LL 的情况。

接下来只要 LL 的操作就能修复树的平衡了

伪代码

z = z.p
RR(T, z)
// 接下来就与 3.2.2.1 相同了
z.p.color = BLACK
z.p.p.color RED
LL(T, z.p.p)

3.2.3 整合

流程图

经过 3.2.13.2.2 的学习,可以整理流程图如下

还是老样子,只画一半,对称的另一半请自行研究

伪代码

/* 
 * 循环的条件是当前结点 z 与其父节点同为红色
 * 因为 case1 只能将问题向上抛
 * 直到以下3种情况
 * 要么遇到黑色结点,那么就平衡了
 * 要么遇到根节点,不能向上递归了,这时候根节点被染红,所以伪代码的最后一定要把根节点染黑
 * 要么遇到 case 2
 */
while z.p.color == RED
	// 由于对称,这里只给出一半代码
	if z.p == z.p.p.left
	
		// y 是叔结点
		y = z.p.p.right
		
		// case 1
		if y.color == RED
			z.p.color = BLACK
			y.color = BLACK
			z.p.p.color = RED
			z = z.p.p
			
		// case 2
		else 
			// case 2.2-LR
			if z == z.p.right
                z = z.p
                RR(T, z)
                
            // case 2.1-LL 的代码与 case 2.2-LR 共用
            z.p.color = BLACK
            z.p.p.color = RED
            LL(T, z.p.p)
            
	else (对称的另一部分仅仅是将 left 与 right 互换)
T.root.color = BLACK

最后再贴张《算法导论》里的图巩固一下

图中浅灰色的结点代表红色

3.3 时间复杂度

插入

插入部分的时间复杂度与 BST 一致,$O(\lg n)$

平衡

AVL 的平衡修复是 $O(\lg n)$

而红黑树平衡性修复的时间复杂度,在最坏的情况下是 $O(\lg n)$,也就是“红黑相间”导致的 case 1 递归到根节点

但这毕竟是极端情况,大多数情况下,平衡性修复不会递归这么多次

虽然在形式上与 AVL 的平衡时间复杂度相同,但 AVL 的 $O(\lg n)$ 是固定不变的,红黑树在有的情况下甚至可以是 $O(1)$

4. 删除

删除比插入要更加复杂

开始之前,我们先来复习一下 BST 的删除

BST 的删除有 3 种情况:

  • Case 1:要删除的结点,本身是一个叶子结点,直接删除即可
  • Case 2:要删除的结点,只有一个孩子,让其父结点指向其孩子结点即可
  • Case 3:要删除的结点 z,有两个孩子,先将其与后继结点 y 交换,随后删除那个后继结点(这时候的后继节点已经是 z 了)

注:后继结点即右子树中的最小数据结点,这个结点是一定没有左孩子的


在红黑树中,叶子节点NIL,所以我们要删除的内部结点永远不可能为叶子结点,只能是“两个孩子都是 NIL 的结点”,这种情况可以与 Case 2 一并处理

因此我们只需要考虑 Case 2Case 3

而这两种情况的核心就是替换(不熟悉的话可以先去看看 BST 是如何删除结点的)

先定义一个删除结点的方法

同样是伪代码

/*
 * T 是整棵红黑树,a 是要删除的结点,b 是用来替换的结点
 * 这个方法只是将 b 替换 a 连到了其父结点。而他们的孩子之间的引用关系不在这里实现。
 * 要说为什么的话,因为如果 a 和 b 就是相连的,那么 b 替换 a 后不用管孩子结点,孩子还在它身上
 * 而 a 和 b 不相连,才会出现 b 的孩子失去父亲的情况,那时候需要自己实现引用关系的修改。
 * 说白了这一部分代码就是把反复重用的代码拎出来减少代码量的
 */
TRANSPLANT(T, a, b) {
	if T.root == a
		T.root = b
		b.p = nil
	else
		if a == a.p.left
			a.p.left = b
		else
			a.p.right = b
		b.p = a.p
}

当然删除结点可能引起红黑性质的破坏

接下来我们将分别介绍删除平衡

4.1 纯纯的删除

4.1.1 Case 2 只有一个孩子

这种情况最简单,直接让孩子顶替自己的位置就好了

伪代码:

/* 
 * 记录要被删除的结点的颜色
 * 之所以取 original 这个名字,是因为另外一种情况下结点会被染色
 * 所以在这部分代码中不用深究
 * 记录这个变量的作用是,判断是否影响了树的平衡,在代码最后才用到
 */
original-color = z.color

if z.left == T.nil
	x = z.right // x 记录失去平衡的结点,见下图
	TRANSPLANT(T, z, z.right)
	
else
	x = z.left
	TRANSPLANT(T, z, z.left)

/* 
 * 只有当删除的结点是黑色时才会引起失衡
 * 1. 因为在只有一个孩子的情况下,若删除的是红色结点不会破坏性质4和性质5
 *    而删除黑色结点会影响黑高从而破坏性质5
 * 2. 在有两个孩子的情况下
 *    我们是先与后继节点交换位置,删除时实际删的是原本后继节点的那个位置,也是只有一个孩子,与上面的情况相同
 */
if original-color == BLACK
    // FIX-UP 是修复平衡的方法,将在后面介绍
    FIX-UP(T, x)

图中 z 代表要删除的结点,灰色结点代表实际被删除的结点,x 是灰色结点的唯一孩子。当前情况下刚好重合。

读起来怪怪的,解释一下:

BST 的删除,例如要删除结点 z,如果 z 有两个孩子,那么删除 z 之后这棵子树就缺少了根节点,这时候就得找到子树中的后继节点来替换 z,否则这棵子树就没有根节点了。这种情况下,从逻辑上讲,我们删除的确实是结点 z,但是从树的物理结构上来看,我们删除的其实是那个后继结点,至于 z,相当于只是值变动了

而上图中,或者说现在我们讨论的情况,是 z 只有一个孩子,那么自然不存在缺少根节点的情况了,直接让那个唯一的孩子移动过来就行。所以灰色结点与 z 重合

删除伴随着移动,而移动就容易导致失衡(黑高变动,或者两个红色结点相互连接)

所以 x 指向的是实际被删除的结点孩子结点

所幸的是,不管是 case 2 还是 case 3实际删除的结点都只有一个孩子结点

Case 2 根据情况,可能是左孩子或右孩子作为 x

Case 3 只可能是右孩子

4.1.2 Case 3 有两个孩子

有两个孩子,我们就得去找要删除的结点的后继结点进行替换

这种情况下要删除的结点 z 就不一定会和实际删除的结点重合了,注意了是不一定

下面分 一般情况特殊情况 分别探讨

一般情况

删除后

删除的过程比较抽象。

我们找到 z 的后继节点 y 来替换 z,这时候 z 的本体已经被删除了。

而用 y 替换 z 的这一过程,在树的结构中,删除的是 y 原本位置的结点。

那么此时 x 指向结点 5

y 的移动会导致 x 失去父亲

所以在 y 被移走(“删除”)前,我们需要将 x 与 y 的父节点 4 连起来。或者说,这里是用结点 x 替换 结点 y

然后才能用结点 y 替换结点 z

特殊情况

后继节点 y 就是结点 z 的右孩子时,只要用 y 替换 z 即可,x 依旧是 y 的孩子

伪代码

y = TREE-MINIMUN(z.right) // TREE-MINIMUN 用来寻找子树中最小的结点,应该不难实现

/*
 * original-color 记录 y 原本的颜色
 * 因为 y 去替换 z 了,所以 y 被染成 z 的颜色
 * 而我们在树的整体结构中删除的是 y 原本的位置
 * 所以我们要记录那一时刻 y 的颜色
 */
original-color = y.color
y.color = z.color

// 为什么 x 是 y 的右孩子,通过上面几张图应该说明了
x = y.right

// 如果 p 不是 z 的右孩子,才需要处理 x 失去父亲的问题
if y.p ≠ z
    /*
    * 用后继节点 y 的唯一的孩子替换后继结点 y
    * 因为 y 被拿去替换 z 了
    * 当然 y.right 就是 x,这里这样写是为了更高的可读性
    */
	TRANPLANT(T, y, y.right)
	
	// 替换后,y 失去了原本的右孩子,并即将获得 z 的右孩子
    y.right = z.right
    y.right.p = y


// 用 y 替换 z
TRANSPLANT(T, z, y)

// 替换后 y 就拥有了 z 原本的左孩子
y.left = z.left
y.left.p = y

if original-color == BLACK
	FIX-UP(T, x)

4.1.3 合并

y = z
original-color = y.color
if z.left == T.nil
	x = z.right
	TRANSPLANT(T, z, z.right)
elseif z.right == T.nil
	x = z.left
	TRANSPLANT(T, z, z.left)
else
	y = TREE-MINIMUM(z.right)
	original-color = y.color
	y.color = z.color
	x = y.right
	if y.p ≠ z
        TRANPLANT(T, y, y.right)
        y.right = z.right
        y.right.p = y
    TRANSPLANT(T, z, y)
    y.left = z.left
    y.left.p = y
if original-color == BLACK
	FIX-UP(T, x)

删除部分到这里就结束了。目前,我们成功地删除了结点 z ,同时用 x 标记了可能失衡的子树的根节点

下一步就是修复平衡了

4.2 平衡修复

4.2.0 理论

理论部分

上面的伪代码中的注释应该写了,当 original-color 为黑色才会破坏平衡。

细想一下也能明白,删除红色结点既不会破坏性质4,也不会破坏性质5

确定了 original-color 为黑色后,就可以明确的声明:性质5被破坏了,因为黑高少了 1

性质4是否被破坏取决于结点 x 的颜色和其父节点的颜色是否均为红色

黑高缺失 1,这个概念比较抽象,在图上不好表示,所以我们再次给 x 结点染上一层黑色,这可不是张口就来的,请看下面的解释

  1. 若 x 结点原本为红色,那么这次染黑不仅合法地修复了性质5,还顺带解决了可能存在的性质4问题。一举两得,属实是妙啊

    这也就是删除中最简单的情况,x 为红色,直接将其染黑,平衡就被修复了

    如果只有这种情况就好了,没有后面这么多内容了,可惜,后面的很复杂

  2. 若 x 结点原本为黑色,那么这次染黑又给他镀上去了一层黑皮,我们在这里定义其为“双黑结点”

    image-20220418181052160

    双黑结点拥有值为 2 的黑色,这样,我们也能成功修复性质5,然而,红黑树中并不存在所谓的“双黑结点”

    所以我们的问题:从“黑高缺失 1,变成了”结点 x 多了一层黑皮“

黑 + 黑 = 双黑,黑 + 红 = 黑

那么我们现在的目标,就是找机会弄一个红色结点过来,把黑皮套给它,让它变为黑色结点

思考一个问题,如果 x 的父节点是红的,能把它染黑吗,当然不能,把它染黑,那不是另外一边的子树也被影响了黑高

✨下面这句话非常重要

所以我们要从另外一边的子树偷一个红色结点放入 x 与 x 的父节点中间,而父节点的颜色已经不在乎了,我们不能去动它

学过了之前的插入平衡修复,应该对红黑树的旋转不这么陌生了吧,我们肯定有办法在不破坏平衡的前提下,转一个红色结点过来

当然还有种特殊情况:X 是根节点。

既然是根节点,不管它有几层皮,我们都给它去了也不会影响平衡。

所以这是一个特例

那么根据上面这两种情况,可以写出简单的伪代码

while x ≠ T.root and x.color == BLACK
	...
	找机会偷个红色结点来修复平衡,最终 x 会指向红色结点或根节点
	...
x.color = BLACK

你以为原理结束了?不,还有很多呢。

下面是 X 为黑的细致原理,结合图文更好理解

需要提醒的是,从这一节开始,我们不能再忽略叶子结点 NIL

在这里,规定:

  • x 为失衡的“双黑结点”
  • v 为实际被删除的结点,
  • p 为 v 的父节点,也可以说是删除 v 后,x 的父节点
  • s 为 v 的兄弟结点,也可以说是删除 v 后,x 的兄弟结点

如下图所示,虽然我全画了黑色,但是能确定为黑色的只有 X

V 是要删除的结点 z 的后继结点,所以 V 的左孩子不可能是内部结点,而右孩子有可能是内部结点。我们选择右孩子。

X 是内部结点的情况不用我画了,下图画出 X 是 NIL 的情况,为了体现 NIL 的重要性

注:方块代表 NIL。另外,不要被图里的表象给骗了,虽然看起来删的是 v,但是实际上删的是 z,原本的 v 已经替换了 z

image-20220418191615646

可以很清楚的看到,成为双黑结点的并不一定是内部结点,NIL 不再可以被忽视

分类讨论

首先,失衡是从 X 结点开始的,所以 X 的子树(或者说它的孩子)是怎样已经无关紧要了,它们本来就是相对平衡的,后面的图中我将直接省略

剩下需要讨论的只有,结点 x、p、s 及 s 的子树的颜色情况


我们唯一能确定的颜色就是 X 为双黑,因为我们就是在讨论这种情况

而上面的“理论部分”我提到:这棵子树的根节点 p 的颜色我们不在乎


X 为双黑意味着,在删除操作之前,这里的黑高起码就是 2 了,既然之前是符合性质5的,那么另一边的黑高也起码是 2。

黑高至少为 2,意味着结点 s 一定是内部结点,而 s 的孩子结点可能全是 NIL,也可能是两个内部结点。不过关于 s 的孩子是什么结点已经不重要了,因为在这一节中 NIL 也一视同仁,我们只关注颜色。


所以只剩下三个结点的颜色需要讨论:结点 s 及其两个孩子

  1. 全黑
  2. s 为红色(两个孩子只能为黑色)
  3. s 为黑色,孩子有红色(应该能猜到吧,左红还是右红又得分开讨论)

下面我将分 3 个小节介绍这三种情况,为了节省篇幅,我只介绍 x 为 p 的左孩子的情况,剩下对称的另一种情况请自行探讨

4.2.1 全黑

全黑不包括结点 p,上面提到过,p 的颜色不是我们要关心的,所以全黑有两种情况:

  1. image-20220418195530170

全黑怎么办,兄弟那边没有红色结点可以偷了,所以我们要想办法往上走,偷别人的去。

这和插入中的 case 1 一样,是一个递归的过程,所以我放在第一个讲,因为你只能递归上去,不能做复杂处理,容易理解

既然我们要往上找,那么双黑的这层黑皮也得传递过去,可传递给 p 之后,左边没有问题,右边的黑高变化了怎么办?

显而易见,将 s 染红

因为这一部分是全黑的,不会破坏性质4,同时又巧妙的把黑高降下来了

看图前为防止产生歧义先声明一点:图中的 NIL 只是特例,因为我们只需要关注他们的颜色,所以我把可能是 NIL 的结点标成了 NIL,不代表它们一定是 NIL

  1. p 为黑

    只要新的 x、s、s 的两个孩子是全黑的就继续递归上去

  2. p 为红

    思考一下,这时候平衡了吗?

    我刻意没有直接将 p 涂黑,你应该想到了,这时候已经平衡了。

    所以递归的截止条件之一就是 p 为红,当然在退出递归时要记得将它染黑。这在之前的伪代码中已经存在了,不需要我们重新编写

当然,我不涂黑 p 的原因还有一个,在代码实现中可没有“双黑”或者“黑红”,所以我们的递归判断条件仅仅是看 x 是黑色还是红色

下面给出伪代码

// 外层循环条件这样写的原因在 4.2.0 理论中已经有了
while x ≠ T.root and x.color == BLACK
	
	// 只给出一半代码,剩下一半是对称的
	if x == x.p.left
	
		s = x.p.right
		// 三点全黑
		if s.color == BLACK and s.left.color = BLACK and s.right.color == BLACK
			s.color = RED
			x = x.p
	
		...
		找机会偷个红色结点来修复平衡,最终 x 会指向红色结点
		...
	else (刚好对称,只是将 left 与 right 互换而已)
	
x.color = BLACK

4.2.2 s 为黑色且拥有红色孩子

在这一小节中,我们定义,s 的红色孩子为 r

同时,不确定颜色的结点以白色表示,虽然图中可能有多个白色结点,但是它们的颜色并不一定相同,白色仅表示颜色不确定

根据红色孩子是左孩子还是右孩子,又可以分为两种情况

4.2.2.1 s 的右孩子是红色

image-20220418204148669

终于出现 p 以外的红色结点了,这边建议直接偷。

当然是偷不是抢,不能直接暴力地把 r 移过去,得通过旋转染色,不知不觉中将 r 染黑修复平衡,那才叫偷

结点 10 与结点 11 不确定颜色,但是无论他们是什么颜色都无所谓,最终都能平衡

由于结点 r 是红色结点,对于它的子树来说,他们的简单路径相当于是 p白->黑

同样,结点 11 的简单路径也是 p白->黑

高端操作来了,既然红色不参与黑高计算,那么如果我们把 p 和 s 的颜色往红色那边拉过去(或者理解为红色结点冒泡上去,每一次冒泡,相当于和父节点互换颜色),再把结点 p 变成红色,也不会影响 r 的子树黑高计算,顶多影响了结点 11 和结点 x 的黑高

这是唯一能把红色移动过去的方法,至于结点 11 和结点 x 的黑高?抱歉,老实待着吧,先偷个红过来再说

对于 γ 和 ζ,简单路径依旧是 p白->黑(s 的颜色现在是 p白了)

好了,接下来该思考结点11 和结点 x 的黑高问题了,或者说它们的路径怎么恢复

想一想,我们偷个红孩儿过来是干什么?还不是为了把 X 的黑皮给他套上,但之前又分析过一般情况下 P 不能直接染黑,容易影响右边的黑高

那就转呗,让结点 s 当这棵子树的根节点。转完就可以把 p 染黑

发现了吗,树平衡了,是不是很突然。

实际上一点都不突然

在一开始,结点 11 的简单路径是 p白->黑

而 s 复制了 p 的颜色,在旋转之后我们又把 p 染黑(也就是变成了 s 的颜色)

所以这时候结点 11 的简单路径又等于 color(p) + color(s) = p白->黑

同时,双黑结点 X 也成功把黑皮套到了偷来的红色结点上面,一切都大功告成。

至于 p白11白 究竟是什么颜色并不重要,我们已经证明了他们的简单路径前后一致。

写成伪代码是这样:

s = x.p.right
if s.color == BLACK and s.right.color == RED
	s.color = x.p.color // s 变成 p 的颜色
	s.right.color = BLACK // r 变成 s 的颜色,s 一开始就是黑色
	x.p.color = BLACK // 在上面文字部分其实 p 改变了两次颜色,但是最终都会变成 s 的颜色,也就是黑色
	RR(T, x.p)
4.2.2.2 s 的左孩子是红色

经典的 RL 形状,不用猜都知道这次我们要用 RL 旋转了。但是怎么记呢,怎么理解呢?

如果你熟悉 AVL 的旋转的话,应该知道不管是 RL 还是 LR,在旋转过程中都会将一个结点插入两个结点之中

现在 r 是红色结点,将它插入 p 和 s 之中会影响平衡吗?试试就知道了

我们对 RL 旋转进行拆分,先进行一次 LL

当然转完之后 r 应该改名变成 s(图中还没改), 毕竟我们定义的 s 就是 x 的兄弟结点,后面的伪代码就是用 s 表示这时候的结点 11 的。

现在来看看子树的相对位置变化:

  • 对于子树 α,简单路径变化了,从 p白->黑 变成了 p白
  • 而对于其他结点或者子树,没有产生任何变化

阅读上面这两句话,同时结合图片,有没有发现:

这相当于是 4.2.2.1 中,右边的红色的结点进行了第一次冒泡。所以我们与 4.2.2.1 可以共用一部分代码

接下来应该怎么做,也不难想到了,那就是继续让红色结点冒一次泡上去,然后进行 RR 旋转:

  1. 将 r 染成 p 的颜色
  2. 将 p 染成 s 的黑色
  3. RR(p)

如果你觉得这样太快了,可以将上面 3 步进行一个简单的拆分:

  1. 将 r 与 p 颜色互换,r 变成 p白,p 变成红
  2. RR(p),这时候根节点还是 p白,而红色结点被偷到左边,同时整棵子树状态与最初相同
  3. 染黑红色结点,修复平衡

写成伪代码是这样:

s = x.p.right
if s == BLACK and s.left == RED
	LL(T, s)
	s = x.p.right // 实际上就是 s = r,但是我们的代码没有 r 的指针,所以要从 x 寻找 r

// 下面就是与 4.2.2.1 一样的代码
// 上图为了好理解没有修改结点 11 的名称,实际上应该已经是 s 了
s.color = x.p.color
x.p.color = BLACK
s.right.color = BLACK // 这一步在 4.2.2.2中没有作用,因为本来就是黑的
RR(T, x.p)
4.2.2.3 合并

上面两种情况都有共用的代码,所以可以合并为:

s = x.p.right
if s.right.color == BLACK // 这样判断是为了在左右都是红色时优先判断为右边为红,可以少执行一点代码
	LL(T, s)
	s = x.p.right
s.color = x.p.color
x.p.color = BLACK
s.right.color = BLACK // 这一步在 4.2.2.2中没有作用,因为本来就是黑的
RR(T, x.p)

结合 4.2.1 的递归,我们可以写出一段较为完整的伪代码

while x ≠ T.root and x.color == BLACK
	if x == x.p.left
		s = x.p.right
		
		if s.left.color == BLACK and s.right.color == BLACK
			s.color = RED
			x = x.p
		else
			if s.right.color == BLACK
                LL(T, s)
                s = x.p.right
            s.color = x.p.color
            x.p.color = BLACK
            s.right.color = BLACK
            RR(T, x.p)
            x = T.root // 因为 4.2.2 一定能修复平衡,这里是为了退出循环
	else (刚好对称,只是将 left 与 right 互换而已)
x.color = BLACK

4.2.3 s 为红色

s 为红色的情况,根据性质4,p 一定为黑色

那么这时候 x、p、s、s 的两个孩子,这 5 个结点的颜色全部确定

这时候还能偷红吗,不行了吧。把 s 和 p 互换颜色转一下?还是不行。如果不信的话可以在草稿纸上试试。

当前这种情况,我们可以通过对 p 进行一次 RR 左旋,加上几步染色操作,将其变为 4.2.1 全黑 或者 4.2.2 s 为黑色且拥有红色孩子

image-20220418203547478

  1. 将结点 s 染黑
  2. 将结点 p 染红
  3. RR(p)

这种情况说实话没什么特别好记或者容易理解的方法,起码我是想不到。

不过你可以看做 s 和其左子树一起搬迁到 p 的左子树。

因为 s 是红色结点,不管放在 p 的左边还是右边,都不影响黑高,再加上这种情况下所有结点的颜色确定,也不会破坏性质4

当然咯,说是说搬迁,实际上是旋转染色,看图就知道结点的相对位置是变动了的

伪代码如下:

s = x.p.right
if s.color == RED
	// 这种情况下颜色是确定的
	s.color = BLACK
	x.p.color = RED
	// 旋转
	RR(T, x.p)
	// s 需要重新定位了
	s = x.p.right

4.2.4 合并

while x ≠ T.root and x.color == BLACK
	if x == x.p.left
		s = x.p.right
		if s.color = RED
			s.color = BLACK
			x.p.color = RED
			RR(T, x.p)
			s = x.p.right
		if s.left.color == BLACK and s.right.color == BLACK
			s.color = RED
			x = x.p
		else 
			if s.right.color == BLACK
                LL(T, s)
                s = x.p.right
            s.color = x.p.color
            x.p.color = BLACK
            s.right.color = BLACK
            RR(T, x.p)
            x = T.root
	else (刚好对称,只是将 left 与 right 互换而已)
x.color = BLACK

乞讨环节

能点文章下方的打赏按钮给我个 5 毛钱吗

5. 手撕红黑树

红黑树 (gitee.com)

6. 参考文章


文章作者: ❤纱雾
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ❤纱雾 !
评论
  目录