标签归档:红黑树

红黑树:自平衡的二叉查找树(二)

前一篇博文展示了红黑树在二叉查找树基础上的改进,讨论了红黑树结点的几种变换以及实现了红黑树的插入算法。本文继续红黑树的话题,谈一谈红黑树结点的删除方法并在最后以测试用例对比红黑树和普通二叉查找树在性能上的差异。

在讨论红黑树的删除算法之前,先回顾一下在《键-值查找的基础——二叉查找树(Binary Search Tree)》一文中提到的二叉查找树的删除方法。在二叉查找树中删除一个典型的结点,要先通过查找操作找到被删的结点 N,然后再找到 N 的右子树中最小的结点 Nrmin,把 Nrmin 从原来的位置删出,替换到 N 的位置。那么,如果在红黑树中也用这样的方法实现删除是否可行呢?显然地,如果 Nrmin 在红黑树中恰好是一个红色结点,那么把它从红黑树中删出,再替换到 N 的位置是没有问题的。但如果 Nrmin 不巧是一个黑色结点,把它从红黑树中删出就会导致和在红黑树中插入一个黑色结点一样的问题:Nrmin 所在的子树的所有叶子结点与整棵树其他的叶子结点到树根的路径长度不相等了。

既然删去一个红结点不会影响红黑树的平衡,那么找到一种方法保证在删除操作发生的时候,最终被删去的结点一定是红色,是解决这个问题的一条思路。在研究红黑树插入算法的时候,提到了对结点左旋、右旋和颜色翻转等三种基本变换,可以发现一个规律,除了在根结点处外,红结点似乎不会凭空产生也不会凭空消失,它只会从一个子树旋到另一个子树,或者从左右子结点“汇聚”到父结点。上一篇博文中一幅向红黑树插入一个新红结点的动画很直观地展示了红链接从树的底端向树根传递的过程,可以看到,树底端的红结点通过一步一步的旋转、颜色翻转最终把根结点染红,后根结点重新被置黑,插入操作完成。如果把这个过程倒过来执行,先把根结点染红,再通过与颜色翻转相反的操作以及适当地左旋和右旋就可以把红色结点一步步下推到需要删除的地方,保证被删去的是一个红色的结点。

在一个典型的删除操作中,一共有两个查找步骤。一个是从根结点出发,找到要删除的目标结点 N;另一个是从 N 的右子结点出发,找到这棵子树中键最小的那个结点 Nrmin。这个查找的路径正好也是根结点通往 Nrmin 的路径,于是在红黑树删除的具体实现中,可以一边查找一边“调运”红色结点。典型情形下,要使 Nrmin 在删出时是红色结点,只需要确保这个原则成立:查找过程中保持查找的后继结点或后继结点的左子结点是红色,直至查找到 Nrmin。这是一个递归的条件,只要查找开始时在根结点处保证了这个条件成立,那么后续每一步查找都可以通过有限次的左旋、右旋及“反颜色翻转”使这个条件成立。特别地,在当 N 的右子结点是空结点的情形下,查找操作查到 N 即停止,也能保证 N 本身或 N 的左子结点是红色结点。

假设正在进行红黑树删除结点过程中的查找操作,当前结点是 Ncur,那么分以下几种情形分别执行不同的变换来维持上文中原则的成立。

(一)Ncur 是根结点且根结点的左右两个子结点都是黑色的,先把根结点染红。然后把根结点当作一般结点继续以下的流程。

(二)Ncur 的查找后继 Nnext 是它的左子结点

  1. Nnext 是红色的或 Nnext 的左子结点是红色的,后继满足原则,无需操作,继续查询后继;
  2. Nnext 不满足原则,但 Ncur 的右子结点是红色的,对 Ncur 执行左旋操作,继续查询后继;
  3. Nnext 不满足原则,而且 Ncur 的右子结点是黑色的,此时由于有原则约束, Ncur 一定是红色的(请思考为什么),对 Ncur 执行反颜色翻转操作,Ncur 的左右子结点都变成红色。这时检查 Ncur 的右子结点的左子结点是否也是红色,如果是,则先右旋 Ncur 的右子结点,再左旋 Ncur 以避免在查找路径之外的地方出现双红父子的问题,然后继续查询后继。

(三)Ncur 的查找后继 Nnext 是它的右子结点

  1. Nnext 是红色的或 Nnext 的右子结点是红色的,后继满足原则,无需操作,继续查询后继;
  2. Nnext 不满足原则,但 Ncur 的左子结点是红色的,对 Ncur 执行右旋操作,继续查询后继;
  3. Nnext 不满足原则,而且 Ncur 的左子结点也是黑色的,同样可得出 Ncur 一定是红色的。先对 Ncur 执行反颜色翻转操作,Ncur 的左右子结点都变成红色。这时检查 Ncur 的左子结点的左子结点是否是红色,如果是,则右旋 Ncur 以避免查找路径之外的地方出现双红父子,然后继续查询后继。

(二)和(三)的第 3. 种情形分别图示如下。

rbt-remove-1图1 左右子结点都为黑,查找后继是左子结点时的颜色变换

rbt-remove-2图2 左右子结点都为黑,查找后继是右子结点时的颜色变换

当删出、替换操作完成后,还需要从查找的终点开始沿查找路径向上回溯,清除之前操作遗留下来的双红父子结点以及右红子结点。这个操作与上篇博文中讲到的红黑树插入新结点后向上回溯恢复红黑树性质的操作非常相似,不再赘述。

至此,一棵完整的红黑树就已经可以实现了。为了检验算法的正确性,同时比较红黑树与一般的二叉查找树在不同的输入条件下的性能差异,我用 Java 分别实现了一个一般二叉查找树的符号表和一个红黑树的符号表。编写了一个测试用例,分别用一组相同的随机乱序数据和一组相同的有序递增数据测试两个符号表实现,并测试各自在进行插入、查询和删除操作中的耗时。另外还选择了一个使用类似技术实现的 Java 容器类 TreeMap 作为对照组,在同等条件下执行这个测试。

测试内容包括了:

(一)一个由 0~1,000,000 范围内的随机乱序整数(可能重复)组成的数组作为输入数据,数组长度为 100,000。

  1. 测试这十万个整数分别插入各符号表实现所花费的时间,以毫秒计;
  2. 生成一个由 0~1,000,000 范围乱序整数组成的新数组,长度为 100,000,分别在各符号表中完成一轮查找操作,测试这个操作在每个符号表中实现所花费的时间,以毫秒计;
  3. 生成一个由 0~1,000,000 范围乱序整数组成的新数组,长度为 100,000,分别在各符号表中完成一轮删除操作,测试这个操作在每个符号表中实现所花费的时间,以毫秒计。

(二)一个由 0~99,999 范围内的顺序排列的连续整数组成的数组作为输入数据,数组长度为 100,000。

  1. 测试这十万个整数分别插入各符号表实现所花费的时间,以毫秒计;
  2. 生成一个由 0~1,000,000 范围乱序整数组成的新数组,长度为 100,000,分别在各符号表中完成一轮查找操作,测试这个操作在每个符号表中实现所花费的时间,以毫秒计;
  3. 生成一个由 0~1,000,000 范围乱序整数组成的新数组,长度为 100,000,分别在各符号表中完成一轮删除操作,测试这个操作在每个符号表中实现所花费的时间,以毫秒计。

测试三次取平均值后的数据如下:

表1 随机乱序数据测试结果(单位为 ms)

Put Get Remove
Basic BST 170.7 53.3 62.7
RBT 171.0 72.3 221.7
Java TreeMap 139.0 88.0 65.3

表2 连续递增数据测试结果(单位为 ms)

Put Get Remove
Basic BST 42,475.7 84,783.0 42,424.3
RBT 122.7 33.7 158.7
Java TreeMap 67.3 26.0 18.0

结果显示,在测试数据随机分散的情况下,普通二叉查找树和红黑树的性能接近,甚至普通二叉查找树性能稍优于红黑树;而当用连续有序的测试数据测试时,普通二叉查找树的性能变得极差,操作耗时增加了数千倍,同时红黑树仍然保持了稳定的性能,耗时没有明显的变化。

本文中提到的全部算法和测试用例均已用 Java 实现,GitHub 版本库地址:查看

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=201 )

红黑树:自平衡的二叉查找树(一)

前一篇博文中写道,二叉查找树是一种具有较高性能的符号表实现,在理想情况下它可以保证查找、插入和删除操作的时间复杂度在对数级别。二叉查找树可以动态地插入和删除元素,在插入和删除操作的过程中,二叉查找树的形状也会发生变化。

考虑以下问题:二叉查找树 T 的初始状态 T0 是一棵空树,现分别以两种不同的顺序 M(A, B, C, D, E, F, G) 和 N(D, B, F, A, C, E, G) 向其中插入 A-G 共 7 个相同的元素,当最后一个元素插入完成后,T 的最终形状 TM 和 TN 分别是怎样的。

bst-n图1 按 M(A, B, C, D, E, F, G) 顺序插入后生长的二叉查找树 TM

bst-m图2 按 N(D, B, F, A, C, E, G) 顺序插入后生长的二叉查找树TN

可以发现,同一组元素可以构建多种不同形状的二叉查找树,二叉查找树最终的形状与插入元素的顺序有关。二叉查找树的操作性能与树的深度相关,在 TM 中查找一个元素最多需要比较 7 次,而在 TN 中查找一个元素最多只需要比较 3 次。显然,TN 的性能优于 TM。可以预见,当元素集合的规模增大时,这个性能差距将进一步增大。TN 是一棵完全二叉树,它的查找性能可以达到 O(logN),而 TM 这种只有右非空子树的二叉树是另一个极端,它的查找性能在最坏的情况下是 O(N),甚至退化到与前一篇博文中提到的数组顺序查找性能相同了。

在实际应用中,我们希望有一种不受插入和删除顺序影响的性能稳定的二叉查找树,这种二叉查找树能在插入和删除的过程中自动调整以保持平衡性,保证任何时候查找的时间复杂度都能达到 O(logN) 的级别。

红黑树就是一种自平衡的二叉查找树。

红黑树的结点除了像二叉查找树有键和值的属性外,还有一个颜色属性,红黑树结点的颜色只能取“红”、“黑”之一。另外,为了描述方便,把某结点的颜色等同于指向该结点的链接的颜色,例如 B 的左子结点 A 是一个红结点,也可以描述为 B 与 A 之间的链接是红色的。一棵红黑树满足以下的条件:

  • 所有结点非黑即红;
  • 根结点是黑色的;
  • 红结点不互为父子;
  • 任一结点到其所有叶子结点的简单路径都包含相同数目的黑结点。

红黑树在插入和删除操作后也应满足以上的条件,上述几个条件的约束保证了红黑树在插入和删除结点之后也能保持平衡。如果把红黑树的红链接的长度计为 0,黑链接的长度计为1,那么从任意一个结点出发,到其所有的叶子结点的最短距离是相等的。下图是一棵典型的红黑树,空结点没有画出。

rbt图3 一棵典型的红黑树

当要向一棵红黑树中插入结点时,应当保证插入操作完成后仍然得到一棵满足上文提到的所有条件的红黑树。相比于普通的二叉查找树的插入操作,红黑树的插入操作更复杂,因为像二叉查找树一样向红黑树中插入新的结点,先不论是红是黑,势必破坏红黑树原有的平衡性。因此,向红黑树中插入新结点后,需要做一些调整,使二叉树重新恢复平衡。

在讨论红黑树插入操作的具体算法之前,先了解在红黑树局部执行的几个重要的变换:左旋、右旋和颜色翻转。

  • 左旋

假设红黑树的某个结点 Nx 具有红色的右子结点 Ny,Nx 的父结点记为 Np,可以将 Nx 与 Ny 两个结点连同它们中间的红链接向左旋转,Np 与 Ny 链接作为它的父结点,Nx 作为 Ny 的左子结点,而 Ny 原有的左子结点重新链接到 Nx 作为它的右子结点,同时将 Nx 的颜色设为红色,Ny 的颜色设为原来 Nx 的颜色。这个操作称为对结点 Nx 的左旋。上文中提到红黑树的红链接长度可以看作 0,由于左旋操作只是在被操作结点的右边删去了一条红链接,在其左边增加了一条红链接,因此左旋操作只改变红链接的位置,而并不会破坏树的平衡性。当需要把一个结点的右红链接调整为左红链接时,对这个结点执行左旋操作。下图展示了一个红黑树结点在执行左旋操作前后的变化。

rbt-rotate-left图4 红黑树结点的左旋,灰色结点表示该结点颜色可黑可红

  • 右旋

与左旋类似,假设红黑树的某个结点 Nx 具有红色的左子结点 Ny,Nx 的父结点记为 Np,可以将 Nx 与 Ny 两个结点连同它们中间的红链接向右旋转,Np 与 Ny 链接作为它的父结点,Nx 作为 Ny 的右子结点,而 Ny 原有的右子结点重新链接到 Nx 作为它的左子结点,同时将 Nx 的颜色设为红色,Ny 的颜色设为原来 Nx 的颜色。这个操作称为对结点 Nx 的右旋。与左旋理由的相同,右旋操作同样不会破坏树的平衡性。当需要把一个结点的左红链接调整为右红链接时,对这个结点执行右旋操作。下图展示了一个红黑树结点在执行右旋操作前后的变化。

rbt-rotate-right图5 红黑树结点的右旋,灰色结点表示该结点颜色可黑可红

红黑树结点的左旋与右旋操作互为逆操作。

  • 颜色翻转

假设一棵红黑树的某结点 N 是黑色结点,它的左右子结点均为红色结点,那么可以把它的左右结点均染成黑色,结点 N 染成红色,这个操作称为颜色翻转。这个操作在结点 N 的左右各删除了一条红链接,同时各增加了一条黑链接,而在结点 N 与它的父结点之前删除了一条黑链接,增加了一条红链接。按前文的定义,红链接的长度为 0,N 结点的所有子结点的到根结点的距离都没有变化,因此颜色翻转操作也不会影响红黑树的平衡。下图展示了一个红黑树结点在执行颜色翻转操作前后的变化。

rbt-flip-colors图6 红黑树结点的颜色翻转

用红黑树实现的符号表,同样至少应当支持查询、插入和删除等操作。由于查找操作是一个只读操作,不会改变红黑树的结构,因此在红黑树上进行查找的实现与二叉查找树完全一样,不再赘述。

向红黑树中插入一个新结点分为两个步骤,第一个步骤与二叉查找树的插入操作一样,在红黑树中查找被插入的结点的键,如果查找命中那么直接用被插入结点的值替换命中的结点。如果查找没有命中,那么在查找过程中最后一次访问的那个结点 N 是插入点,如果将要插入的结点的键小于 N 的键,那么将该结点作为 N 的左子结点,否则作为它的右子结点。

新的结点插入后,是时候讨论红黑树平衡的问题了。首先,新插入的结点应当是什么颜色的?红黑树的约束之一是“任意结点到其所有的叶子结点的简单路径都包含相同数量的黑结点”,前面讨论过,如果把红链接的长度看作 0,把黑链接的长度看作 1,这个条件还可以表达为“任意结点到其所有的叶子结点的最小路径长度都相等”。可见,如果新插入的是一个黑色结点 N,由于多出了一条黑链接,那么从根结点出发到 N 的最短路径长度一定比到其它所有叶子结点的最短路径大 1,这违反了红黑树的约束条件。而如果插入的是红结点,则完全没有这样的问题。因此,新插入的结点一律先将其设为红色

尽管可以把新插入的结点设为红色来避免出现不平衡,但有一些问题仍然没有回避,例如如果新插入的结点的父结点也是红色,则这棵树又违反了红黑树“红结点不能互为父子”的原则。当遇到这种情况时,就需要运用上文中提到对红黑树结点的几种变换来使这棵树重新符合红黑树的原则了。

为了简化问题,降低算法的复杂度,在具体实现一棵红黑树时,我参考了《Algorithms (Fourth Edition)》一书中的做法,在标准红黑树的约束条件下,再加一条约束条件:所有红链接一定均为左链接。加上了这个条件的红黑树依然能实现,并且能完成标准红黑树所有的操作。下文所有的内容所描述和实现的红黑树均是加了这个附加条件的红黑树,但请注意,具有右红链接的红黑树也是可用的,只是实现起来更加复杂。

在向一个非空红黑树插入一个新结点后,有多种不同的情况需要分别处理。为了描述方便,将新插入的结点记为 Nn,被插的结点(即新结点的父结点)记为 Np,与 Nn 拥有共同父结点的结点(称为 Nn 的兄弟结点)记为 Nb

(一)如果 Nb 和 Np 都是黑色结点(空结点也视为黑色结点,下同),那么情况比较简单:

  1. 如果 Nn 是 Np 的左子结点,此时整个树仍然满足红黑树所有的约束条件,不再作任何处理,插入操作完成;
  2. 如果 Nn 是 Np 的右子结点,Nn 与 Np 之间出现了一条右链接,不满足上文提到的红黑树附加条件,此时对 Np左旋操作,把红链接旋转为一条左链接,操作完成。

(二)如果 Nb 是红色结点,由红黑树的性质可知 Np 此时一定是黑色结点,此时 Np 的左右均为红链接,对 Np颜色翻转操作,将 Nn 与 Nb 全变为黑色,并将 Np 变为红色。由于 Np 处多了一个红结点,因此同要样要以(一)、(二)和(三)的规则再处理 Np

(三)如果 Np 是红色结点,像(一)一样,有如下两种不同的情况:

  1. 如果 Nn 是 Np 的左子结点,此时出现了两个连续的左红链接,不符合红黑树的约束条件,对 Np 的父结点 Npp(称为 Nn 的祖父结点)做一次右旋操作,把 Np 的左红链接旋转到右侧,于是 Np 左右就有了两条红链接,分别连着 Nn 和 Npp,再对 Np 做(二)中提到的操作;
  2. 如果 Nn 是 Np 的右子结点,此时对 Np 做一次左旋操作,又出现了两条连续的左红链接,再对 Np 做(三).1 中提到的操作。

(二)、(三)情况的图示如下。

图7 红黑树插入新结点后的一些调整操作

上述(二)中的情形会将红链接传递到父结点,当父结点的父结点也碰到红链接时又会将红链接向上传递,直到遇到根结点。当根结点变成红色时,需要把它重新染黑,根结点由红变黑一次意味着红黑树的高度增加了 1。因此,与二叉查找树相反,红黑树是自下向上生长的。下面的动画展示了一棵红黑树在插入一个新的节点后红链接向上传递的过程。

rbt-insert-ani图8 一棵红黑树在插入一个新结点后的生长过程

与二叉查找树一样,红黑树的删除操作比插入操作更加复杂,由于篇幅已经很长,关于红黑树的删除留到下篇博文中讨论。

本文中提到红黑树的所有算法均已用 Java 实现非递归版本,GitHub 版本库地址:查看

参考文献
[1] Sedgewick R, Wayne K. Algorithms[M]. 人民邮电出版社, 2012.
[2] 侯捷. STL 源码剖析[M]. 华中科技大学出版社, 2002.

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=139)