月度归档:2015年03月

排序

将一个数据集合按照给定的规则以一定的顺序重新排列,这个操作称为排序。排序算法在计算机程序设计中的重要性和应用的广泛性毋须多言,几乎所有高级计算机语言都带有排序算法的库,在程序开发过程中不必再造一次轮子,但掌握排序算法的原理仍然是非常必要的。本文将从一个最直观的排序算法——选择排序开始,不断探讨排序算法的改进和优化空间,期间会谈到多个经典的排序算法。排序算法是如此简洁而优雅:不论是简单直观的选择排序算法,还是应用最广泛而高效的快速排序算法,实现它们的核心代码最长也不过寥寥二十几行。因此,本文提到的每个算法,除了必要的图文描述外,还会配上实现它们的 Java 代码。对于排序算法来说,代码是最好的描述。

选择排序

选择排序是本文所有算法中最直观的,也是效率最低的排序算法。了解选择排序的算法可以帮助理解排序的基本逻辑:比较元素的大小并视情况交换它们。选择排序算法可以很简单地描述如下:从数组的第 0 个元素开始,找出数组中最小(大)的那个元素,并和第 0 个元素交换位置;然后再从第 1 个元素开始,重复以上的过程,直到数组所有的元素都完成一轮这样的操作。这个操作非常容易理解,也能用很简短的程序实现。下面是实现选择排序的 Java 代码,其中 swap(a, x, y) 方法的作用是交换数组 a 中索引为 x 和 y 的两个元素,后面的代码将多次用到这个方法,不再说明。

可以看到,选择排序的性能很稳定,如果数组的长度是 n,不管初始数组内的元素如何排列,排序操作完成时一定会发生 n-1 + n-2 + … + 1 = n(n-1)/2 次比较。

插入排序

选择排序的问题之一是每一轮搜索都执着地要找出最小的那个元素,然而要找出最小的元素,必须将当前集合里所有的元素都访问一遍。就算被排序的数组本身已经是有序的了,选择排序的执行时间跟数组是乱序情况下也是一样的。

插入排序在这一点上做了一些改进。和选择排序一样,插入排序在执行过程中保持当前索引左边的元素集合是有序的;但与选择排序不同的是,这些元素并不一定是整个数组中最小的那部分。假设一个对数组 a 的选择排序在进行过程中,当前的有序集合是 a[0…m],右边未排序的集合是 a[m+1…n],那么只要将元素 a[m+1] 与它左边的元素进行比较并视情况交换位置,直到使 a[0…m+1] 也成为一个有序的数组。将上述操作继续进行,直到整个数组都是有序的。插入排序的 Java 实现代码如下:

插入排序的性能是不稳定的,当被排序的数组已经是一个有序数组时,假设数组的长度是 n,执行一次插入排序只要比较 n 次;而当被排序数组正好是期望顺序的倒序时,插入排序的性能最是坏的情况,需要比较的次数与选择排序完全一样。当被排序的数组存在较大比例的有序部分时,插入排序的性能是很好的,然而,它的缺点是性能不够稳定。

希尔排序(Shell Sort)

希尔排序得名于它的设计者 Donald Shell。希尔排序是在插入排序的基础上改进后的排序算法。在插入排序中,一个相对较大的元素每次比较只能向前移动一个位置,经常需要移动多次才能到达它应到的地方,这限制了插入排序的性能。

希尔排序的思想是将一个数组中彼此间隔为 h 的元素分组,一共有 h 个分组,对每个分组分别执行插入排序,完成后这个数组称为“h 有序数组”。希尔排序的方法是先取一个较大的 h(不大于 n / 2),使数组成为 h 有序数组,然后再适当减小 h 的值,重复上面的操作,直到最后 h = 1,相当于一次普通的插入排序。希尔排序的 Java 实现代码如下。

希尔排序首先使用较大的 h 值进行粗略的排序,较大幅度地移动元素。每完成一轮都增加了数组的有序性,使下一轮 h 更小的更精细的排序能较快地进行,最后当 h = 1 时,数组已经是基本有序的状态了,只要对个别元素进行距离较短的调整即可完成排序。实践表明,在对一般乱序的数组进行排序时,希尔排序的性能远优于插入排序。

对于 h 序列的选择有非常多的研究,对不同的 h 序列进行排序时性能的差别较大,但并没有人证明某个序列的性能是最优的。上述代码中的 step 和 nextStep 方法是返回第一个 h 的值以及后续 h 的值,本文并没有给出,我在实现时参考了《Algorithms (4th Edition)》一书中的序列,有兴趣请移步我的 GitHub 查看这个算法的完整实现。

归并排序(Merge Sort)

在高效算法中,我们会经常见到一种分而治之的思想,即把一个复杂的问题拆分成两个较简单的问题分别处理,简单的问题得解后复杂的问题也就已经解决了。归并排序是将分治和递归结合的一种排序思路:

  1. 拆分:如果数组的长度等于 1,数组已经是有序状态,直接返回;否则将数组拆分成左右两个部分;
  2. 递归:左右两个部分分别再进行归并排序,得到两个有序的部分;
  3. 合并:两个有序的部分合并,数组排序完成。

和其他递归思想的算法一样,把问题不断地拆解最终会得到一个不需要解决的问题:排序长度为 1 的数组,这时候直接返回即可。将两个有序的数组合并也非常容易实现,下面是归并排序的 Java 实现,其中 11-19 行的 while 循环完成了合并操作。

归并排序的效率比之前提到的所有算法都高,达到了 O(nlogn) 的级别,而且它的效率还难得地稳定。事实上,归并排序已经是具有实用价值的排序算法了。归并排序的一个缺点是需要一个额外的辅助数组来暂存合并的结果,这个数组的最大长度与被排序的数组长度相同。

快速排序(Quick Sort)

如果说归并排序是牺牲了一定的空间来换取时间上的最优解,那么快速排序则同时满足了时间和空间上的最优;它不像归并排序一样需要一个额外的辅助数组,更可贵的是,描述和实现它仍然非常简单。

与归并排序一样,快速排序也是一种分治的算法:

  1. 切分:如果被排序的数组长度是 1,无需排序;否则选择一个切分元素 s,移动 s 和其他的元素,保证 s 左边的元素都不大于 s,并且 s 右边的元素都大于 s;
  2. 递归:以 s 为分界,分别对 s 左边的子数组和 s 右边的子数组做快速排序操作。

上述操作完成后数组排序完成。在实现中,通常取第 0 个元素作为切分元素。对于长度为 l(l > 1) 的数组 a,切分操作简单描述如下:

初始令索引 i = 1, 索引 j = l – 1。i 向右搜索,直到找到 i 满足 a[i] > a[0];j 向左搜索,直到找到 j 满足 j[i] < a[0],此时交换元素 a[i] 和元素 j[i]。i 和 j 继续分别向右和向左搜索,直到 i == j,即两个索引相遇。此时比较 a[0] 与相遇处 a[i] 的值,当 a[0] >= a[i] 时交换 a[0] 与 a[i],索引 i 处于切分点;否则交换 a[0] 与 a[i – 1],索引 i – 1 处于切分点,至此切分操作完成。下面是快速排序算法的 Java 实现,其中 7-16 行的 while 循环实现了切分操作。

快速排序一个潜在的缺点在于它是一种不稳定的排序算法,考虑对一个已经有序的数组进行快速排序,会发现每次切分点都在数组的边缘,这时算法的效率将退化到 O(n2) 级别。为了规避这个缺陷,在实际应用中,在进行快速排序之前需要对被排序数组进行随机乱序处理。

性能测试

为了测试上述所有排序算法的性能及算法实现的正确性,我设计了一个测试用例,以几种不同长度、不同排列顺序的数组分别测试排序,并统计运行耗时。测试用例所用的数组有:

  1. 长度 10,000 取值范围 0-100,000 的随机乱序数组;
  2. 长度 100,000 取值范围 0-1,000,000 的随机乱序数组;
  3. 长度 1,000,000 取值范围 0-10,000,000 的随机乱序数组;

测试结果如下(数据单位是 ms):

 

10,000

100,000

1,000,000

SS

122

14,851

*

IS

149

16,657

*

ShS

10

66

1,485

MS

7

84

528

QS

9

92

472

* 超过 60,000 ms 被中止测试

测试结果显示,归并排序和快速排序性能优异,而希尔排序在数组长度较小的情形下有较好的性能。 选择排序和插入排序在测试中表现相对较差,甚至在大数组测试中迟迟没有出现结果,只好中止测试。

本文提到的所有算法和测试用例的源代码均托管于 GitHub,查看

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

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

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

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

键-值查找的基础——二叉查找树(Binary Search Tree)

在计算机程序设计中,我们经常需要一种将键与值联系并存储起来的数据结构,这个结构称为符号表。一个符号表应当至少支持插入、查询和删除等操作。

最简单的符号表之一是将键-值对作为一个结点,直接存入到一个数组中。每当要向符号表中插入新结点时,就将新的结点添加到数组的末尾。这个用数组构建的符号表是无序的,可以看到,当符号表的长度是 n 时,按键查询一个指定的结点最坏的情况下需要比较 n 次,搜索的时间复杂度是 O(n),这个简单实现是非常低效的。

要达到较高的搜索效率,最基本的思想是保持数据集合的有序性。在有序的数组中进行二分查找是一个典型的例子,二分查找可以达到对数级别的时间复杂度,效率远远优于在无序数组中顺序查找。遗憾的是,尽管在有序数组构成的符号表中执行二分查找非常高效,但符号表是应当支持动态插入和删除的,我们在数组上的实现此时陷入了一个矛盾:如果直接向数组尾部插入或删除结点,很可能破坏数组的有序性;如果在数组的中间插入或删除新结点,则因为移动插入或删除位置后的元素非常费时间,导致符号表的插入和删除的时间复杂度很高。另外值得一提的是链表拥有高效的插入和删除操作,但链表无法像数组那样随机访问,不能在链表上实现二分查找。

二叉查找树正是被设计用来解决插入/删除与查找效率矛盾的。将键与值同时保存在一棵二叉树的结点中,并保证所有结点的左子结点(如果不为空)的键小于右子结点(如果不为空)的键,那么这棵二叉树是二叉查找树。

二叉查找树的任一非空子树一定是二叉查找树。

利用以上这个性质,我们可以总结出在二叉查找树中查找键为 k 的结点的方法:
1.从根结点出发,作为当前结点;
2.比较 k 与当前结点键 kn 的大小,如果 k 等于 kn 那么查找命中返回;如果 k 小于 kn 那么继续查找左子树;如果 k 大于 kn ,那么继续查找右子树;
3.如果被查找的子树为空,那么查找失败,符号表中不存在要查找的结点。

向二叉查找树中插入新结点的过程与查找类似,先在二叉查找树中做一次查找,查找的健为 k ,根据情况做以下操作:
1.如果根为空(空二叉查找树)那么生成一个新结点作为根结点;
2.如果查找命中,那么用新的键和值替换命中的结点;
3.如果查找不命中,那么比较 k 与查找过程中最后一次访问的结点 noden 的键 kn ,如果 k 小于 kn ,那么生成一个新结点作为 noden 的左子树,反之如果 k 大于 kn ,那么生成一个新结点作为 noden 的右子树。

删除是二叉查找树中最难以实现的操作。

要向二叉查找树中删除结点时,先查找到指定结点,以下是较简单几种情形对应的操作:
1.没有查到结点,二叉查找树中不存在被删除的目标,删除失败;
2.查到的结点是叶子结点,直接删除;
3.查到的结点有且仅有一个非空子树,删除该结点,并把它的唯一子树连接到其父结点;

当查到的结点同时有两个非空子树时,删除这个结点就变得比较棘手,因为直接删掉这个结点后,会多出两个子树,而它们却只有一个父结点。T.Hibbard 在 1962 年提出了解决这个难题的第一个方法。[1] 为了方便描述,先考察“删除一棵二叉查找树中最小结点”的方法。显然地,一棵二叉查找树中最小的结点的左子树一定为空,所以这个操作符合上文所说的第 2 或第 3 种情形,可以很轻松地完成。定义一个函数:Node removeMinNode(Node node); 删除 node 结点的最小子结点并返回它的引用。现在删除二叉查找树中有两个非空子树的结点的算法可以描述如下:
1.查找到目标结点 nt,找出它的左结点 nl 和右结点 nr
2.执行“删除最小结点操作”,nn = removeMinNode(nr);,nn 替换到原来 nt 所在的位置;
3.分别设置 nl 和 nr 为 nn 的左、右结点。
这个操作可以保证删除目标结点后二叉查找树仍保持有序性。

用 Java 以非递归的方式实现了本文提到的二叉查找树的所有算法:查看

参考文献
[1] Sedgewick R, Wayne K. Algorithms[M]. 人民邮电出版社, 2012.