归档 技术 呓语

红黑树─算法导论(15)
2015年10月29日 22:47

1. 什么是红黑树

1.1 简介

上一篇介绍了基本动态集合操作时间复杂度均为O(h)的二叉搜索树。但遗憾的是，只有当二叉搜索树高度较低时，这些集合操作才会较快；即当树的高度较高（甚至一种极端情况是树变成了1条链）时，这些集合操作并不比在链表上执行的快。

于是我们需要构建出一种“平衡”的二叉搜索树。

红黑树（red-black tree）正是其中的一种。它可以保证在最坏的情况下，基本集合操作的时间复杂度是O(lgn)。

1.2 性质

与普通二叉搜索树不同的是，红黑树在每个结点上增加了一个存储位来表示该结点的颜色（只能是Black或Red中的一种），因此此时一个结点包含5个属性：color，key，left，right和p。通过对各个结点的颜色进行约束，可以保证任何一条从根到叶子的简单路径上不会比其他路径长2倍（这就保证了“平衡”）。

这个约束（性质）是：

  1. 根结点和叶结点是黑色的；

  2. 红色结点的子结点必是黑色的；

  3. 任何一个结点到其所有后代叶结点的简单路径包含相同数目的黑色结点，并称这个黑色结点的数目（不包含出发结点）为黑高（black-height，用bh(x)表示，红黑树的黑高为根结点的黑高）。

例如，下图就是一棵合法的红黑树：

也许你会奇怪上面的红黑树并没有满足叶结点必须是黑色这条性质呀。事实上它是满足的，因为上图画出的其实是树的内部结点。在真正处理时，会把上图中的叶结点的左右孩子指向一个值为NIL，颜色为黑色的结点（外部节点），即真正的叶结点是这个黑色的值为NIL的结点，这样就满足红黑树性质了。如下图所示：

但是如果采用上面的方法处理，无形中加入了许多“无用”的结点，势必会浪费大量的存储空间。好的做法是，把这些NIL结点合并为一个，就像下图做的那样：

但为了方便起见，我们之后的讨论将忽略这个值为NIL的结点。

1.3 为什么红黑树是一种好的搜索树

这是因为通过上述约束条件构造出来的红黑树一定满足：

一棵有n个结点的红黑树的高度至多为2lg(n+1)。

证明方法很简单，可以用数学归纳法：以任一结点x为根的子树至少包含2bh(x)−12^{bh(x)}-1个内部结点。然后根据约束③便可以得出上述结论（具体证明略）。

因此，动态集合操作Search、Minimum、Maximum、Successor 和 Predecessor 在红黑树上均可在O(lgn)O(lgn)时间内完成。

由于红黑树其实是一种“平衡”的二叉搜索树，因此我们只需要研究它的插入和删除操作，其他操作和二叉搜索树一致。

2. 旋转

在介绍插入和删除操作之前，先介绍一种叫做旋转的动作。旋转又分左旋和右旋，如下图所示：

下面是左旋动作的伪代码：

右旋动作与左旋类似，不再赘述。可以看出，左旋和右旋动作可以在O(1)时间内完成。

下图是一个左旋动作的具体例子：

3. 插入

3.1 算法

可以用类似于二叉搜索树的方法来向树中插入一个元素。它可以在O(lgn)时间内完成。插入算法的描述如下：

可以看出上述代码默认把新插入的结点着为红色插入（原因之后给出）。与二叉搜索树的插入算法最为不同的是，在最后一步调用了RB-INSERT-FIXUP方法来维护红黑树的性质。下面是它的具体描述：

下面是一个具体的例子：

3.2 分析

上述过程可能有些复杂，下面仔细分析一下，从两个方面入手：

  1. 应当明确RB-INSERT-FIXUP方法是来维护红黑树的性质的，因此我们要搞清楚插入一个结点（红色）将会打破哪些约束条件。

  2. 要具体分析上述的三种情况究竟在做什么、有什么影响。

哪些性质会被破坏

很明显，只有性质①——根结点必须是黑色（当且仅当插入时树为空会发生这种情形）和性质2——红色结点的孩子必为黑色会被破坏。

三种情况

下面分析代码中的三种情况，需要说明的是：

  1. 循环的前提是z的父结点是红色。

  2. 分析的三种情况建立在z的父结点是左孩子基础上（相反情况类似，不做分析）。

  3. 容易看出：在每次迭代前，z结点总是红色的；y结点为z结点的“叔叔”（y = z.p.p.right，下面称y为z的叔结点）。

Case 1：

z的叔结点y为红色（同时也说明了z的“爷爷”结点是黑色的）。在做什么：把z的“爷爷”结点着为红色；而把“爷爷”结点的子结点都着为黑色；z上升2级，指向它的“爷爷”结点。有什么影响：以上操作对任何一条简单路径的黑高都不会产生影响；操作其实并没有让情况得到“改善”，只是使z上升了2级。

Case 2： z的叔结点y为黑色且z为右孩子。在做什么：z指向自己的父结点；对z结点进行左旋操作。有什么影响：以上操作对任何一条简单路径的黑高都不会产生影响，只是将Case 2变为了Case 3。

Case 3：z的叔结点y为黑色且z为左孩子。在做什么：把z的父结点置为黑色；把z的“爷爷”结点置为红色；对z的“爷爷”结点进行右旋操作。有什么影响：在两次修改颜色后，会导致从根结点向左出发的所有路径的黑高加1，而向右出发的所有路径的黑高不变；而右旋操作会使黑高回归平衡。

3.3 证明

下面用循环不变式来证明上述过程，这个不变式是：

  1. 结点z是红色的；

  2. 最多仅有1条红黑性质被打破，要么是性质1—根结点为黑色被打破；要么是性质2—红结点的孩子必须是黑色被打破。

初始化：由于我们默认把新插入的结点置为红色，因此初始时，结点z是红色显然成立。在迭代之前，如果只有一个结点，即只有根结点，性质1被打破；否则，z和z.p都为红色，性质2被打破；综上所述，不变式在初始时成立。

保持： 从上面对三种情况的分析我们可以看出：结点z始终是红色的；三种操作都没有改变任何路径上的黑高，即性质3始终是满足的。显然每次完成case 1后，性质1或性质2是被打破的。完成Case 2一样。当完成case 3后，循环就终止了（因为在case 3中我们把z.p置为了黑色），此时满足红黑性质。不变式始终成立。

终止： 迭代终止的条件是：z.p为黑色。通过保持性分析我们看出，终止只可能发生在执行完Case 1和Case 3情形后。而在执行完Case 1后z为红色，z.p为黑色，因此性质2不可能被打破，那么只可能是性质1被打破；在执行完Case 3后，就已经满足所有红黑性质，即已经是一棵合法的红黑树。由上述分析，我们可以得出：在循环结束后，要么二叉树已经是一棵合法的红黑树；要么只有性质1—根结点为黑色被打破。于是在循环结束后，我们只需要做一次将根结点置为黑色，那么便修正了红黑树的合法性。

3.4 说明

由于一棵有n个结点的红黑树的高度为O(lg n)，因此执行RB—INSERT的前16行需要O(lg n)时间；在RB-INSERT-FIXUP中，仅当case 1发生时，while循环才会执行下去；而每次执行完case 1，指针z都会上升2层。因此while循环最多执行lg n次；所以RB-INSERT-FIXUP时间复杂度为O(lg n)，因此整个插入操作的时间复杂度为O(lg n)。

4. 删除

4.1 算法

同二叉搜索树一样，先给出TRANSPLANT方法，该方法会用以v为根结点的子树替换以u为根结点的子树：

下面是删除操作的算法描述：

可以看出，以上删除操作与普通二叉搜索树相比没有太大差别。其中最大的差别是以上操作在22行加了一个维护红黑性质的过程，RB-DELETE_FINXUP，该操作的过程如下：

4.2 分析

RB-DELETE 也分了三种不同的情况，其中第三种情况又分了两小种，分别依次对应如下图所示的情形：

同样还是分析各种情况在做什么，有什么影响（对红黑性质而言）。

可以发现上图其实就是普通二叉搜索树在删除时的分类情况，事实上，以上的代码完全包含了普通二叉搜索树删除操作的代码，只是在其基础上加上了维护红黑性质的代码。因此对于这些重复的代码做了什么可以不用分析。

在每次删除前，对于上面前两幅图中的情况，会记录下被删除结点z的颜色，因为它决定了最后是否需要修正红黑性质（若z为红色，其父结点和孩子必为黑色，删除z将不会违背性质3，用z的孩子去替代z也不会影响性质2），y指向z，x指向z的右孩子；对于后两种情况，记录的是被删除结点z右子树中关键字最小的结点y的颜色，同样，如果它是红色，不管z是什么颜色，统一将y的颜色修改为z的颜色，并按照图中的方式去置换掉z，都不会对红黑性质产生影响。综合上述分析，可以发现四种情况的“输出”（处理后的结果）是一致的：若记录的颜色是红色，说明红黑性质未改变；如果是黑色，说明红黑性质一定被打破了。具体的说，如果结点y是黑色，如下图，将会造成3种影响：

  1. 如果y原来是根结点，而y的一个红孩子成为了新的根结点，将会违背性质1。如上图①中左侧情况。

  2. 如果x和x的父结点都为红色，将违背性质2。如上图③中的左侧，x为红色的情况。

  3. 所有的情况（除了y原来是根结点外）都将导致之前包含y结点的简单路径上的黑结点数少1，将违背性质3。修正这一问题的方式是将现在占据y结点位置的x结点“再涂上一层黑色”，当然，“涂色”操作并不反映在代码上，即不会修改x的color属性，只是“在心中记住”，适当的时候会把x的这层黑色涂到某个红色结点上以达到目的。“涂了两层色”的x结点可能是双层黑色或红黑色，它们分别会“贡献”2或1个黑色结点数。

下面再分析 RB-DELETE-FIXUP 修正过程，分4种情况，如下图所示：

Case 1：x的右兄弟w是红色，说明x的父结点一定是黑色。所作的操作是：交换w和其父结点的颜色，即把w换为黑色，其父结点换位红色；然后对父结点左旋，w重新指向x的右兄弟（该结点原本是w的左孩子，所以一定为黑色）。这是Case 1过度到Case 2。

Case 2：w的孩子都为黑色（w也是黑色）。所作的操作是：将w换为红色，x指向其父结点。

Case 3：w的左孩子是红色，右孩子是黑色（w也是黑色）。所作的操作是：交换w和其左孩子的颜色，即把w换位红色，其左孩子换为黑色；然后对w右旋，w重新指向x的右兄弟。

Case 4：w的右孩子是黑色（w是黑色）。w与x的父结点交换颜色；并把w的右孩子设为黑色，对x的父结点左旋，x直接指向根结点，循环结束。

做完以上的while循环，还要做的一步操作是将根结点置为黑色。这样就能保证满足性质1。

可以证明做完上述操作，所有的红黑性质便满足了。具体证明过程和插入操作时的证明类似，这里省略。

同样不难分析出 RB-DELETE 的时间复杂度是O(lgn)O(lg n)。

End