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

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

在讨论红黑树的删除算法之前,先回顾一下在《键-值查找的基础——二叉查找树(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 )