标签归档:算法

动态规划与编辑距离问题

动态规划Dynamic Programming)是一种精妙的算法设计技巧,在多种成熟的算法模型中都有动态规划思想的运用。

首先考虑一个简单的爬楼梯问题:一段楼梯共有 n 级阶梯,每次可以向上爬 1 级或 2 级,问一共有多少种上楼梯的方法。

假设在一段楼梯中,爬上第 i 级阶梯一共有 Si 种方法,容易观察到存在 Si = Si-2 + Si-1 (i = 3, 4, 5, …, n)的递推关系,同时显而易见地,有 S1 = 1, S2 = 2 的初始条件。因此,要求 Sn 的值,只需要通过递推关系先后求出 S3, S4, S5, … Sn 的值即可。

存在递推关系是一个问题可以用动态规划思想求解的必要条件。像上述求解爬楼梯问题一样,用动态规划求解一个规模为 n 的问题时,先考虑规模为 1, 2, 3… 等子问题是否有显而易见的解,再找出递推关系,利用递推关系逐步求解更大规模子问题的解,直到最终解出规模为 n 的问题。

动态规划思想经常用于解决最大、最小、最短、最优的路径等问题,在解决这类问题时,要确保找到的递推关系在每一步的计算结果都是符合问题中最大、最小、最短或最优要求的。另外,这类问题经常在每一步都有多个候选的解,需要用数组将这些候选解全部暂时存储起来。下面是一个经典的用动态规划求解的问题:一些数排列成一个三角形,从三解形的顶部出发,每次可以向左下或右下走一步,求走到最底部时经历的所有数之和最小的路径。

   2
  3 4
 6 5 7
4 1 8 3

首先,很显然的是,当这个问题的规模为 1(即只有一行)时,问题的解就是 2。设 Nij 表示这个三角形的第 i 行的第 j 个数(i、j 均从 0 开始计),Sij 表示从根出发到 Nij 可能的所有路径中经历所有的数(包括 Nij)的最小的和,可以得到如下的递推关系:Sij = min(Si-1 j, Si-1 j-1) + Nij。min(x, y) 表示 x, y 中较小的那个数。

然后逐步增加问题的规模,用递推关系解出每一步的结果:当子问题规模为 2、3、4(即 2 行、3 行、4 行)时,(Sn0, Sn1, …, Snn) 分别是 (5, 6)、(11, 10, 13)、(15, 11, 18, 16)。在最终的结果中选出最小的数 11 即为本问题的解。

下面的代码是上述算法的 Python 实现。

不同的问题递推关系中需要的已知条件可能各不相同,有的只需要前一步的结果有的需要前更多步甚至之前所有的结果;如上面的问题只需要前一步的结果,而爬楼梯问题则需要前一步和前两步的结果等。在编写程序时应当根据递推关系的特点暂存前一步或更多步的计算结果。

动态规划一个实用的应用是求编辑距离Edit Distance)。一个字符串可以经历有限次变换步骤转变成另一个字符串,假设每个步骤只允许在字符串的任意位置增加、删除或修改一个字符,由字符串甲转换到字符串乙可行的最少步骤数即是这两个字符串之间的编辑距离。编辑距离在 DNA 分析、拼写检查、语音识别、抄袭检测等多个领域都有应用。

例如,可以通过如下的三个步骤将单词“kitten”转变为“sitting”:

  1. kitten → sitten(k → s)
  2. sitten → sittin (e → i)
  3. sittin → sitting (→ g)

从源字符串经过一系列编辑动作转换为目标字符串的可行路径很多,求解编辑距离实质上就是寻找一条这样的最短路径,并得到它的长度。为了找到最短的编辑路径,可以运用上述的动态规划的思想。

前文中讲到,用动态规划求解问题,首先考虑一个较小规模的子问题是否有显而易见的解。对于编辑距离问题来说,“规模”存在于源字符串和目标字符串的长度两个维度,例如“将字符串 k 转变为字符串 s”是最小规模的一个子问题;“将字符串 ki 转变为字符串 s”与“将字符串 k 转变为字符串 si”为两个维度上不同的两个次小规模的子问题。显然,它们都有显而易见的解。

用下图的一个二维表格来表示上述编辑距离问题中每一个子问题的解的情况。

图 1 用二维表格表示一个编辑距离问题解的情况

在上述表格中,设 Cij 为第 j 行第 i 列的单元格,单元格 Cij 中将填入的数字表示源字符串的长度为 i 的子字符串转换为目标字符串长度为 j 的子字符串的编辑距离。例如,C45 表示字符串 kitt 转换为字符串 sitti 的编辑距离。特别地,当 i 或 j 为 0 时的单元格表示的是空源字符串或空目标字符串。

上述的表格第 0 行表示一个字符串转换为空字符串的编辑距离,显而易见地,这一行中所有单元格的数值是所对应的源字符串的长度;同理,上述表示中第 0 列表示一个空字符串转换为目标字符串的编辑距离,这一列中所有单元格的数值是所对应的目标字符串的长度。所以有 C0p = p, Cq0 = q,可以简单地填满第 0 行和第 0 列的所有单元格如下:

图 2 填写表格的第 0 行和第 0 列

接下来,考虑这个问题的递推关系。先假设 Si 表示源字符串长度为 i 的子字符串,Dj 表示目标字符串长度为 j 的子字符串,所以单元格 Cij 表示的是字符串 Si 转换为字符串 Dj 的编辑距离。由于编辑距离的定义中允许每步插入、删除或修改一个字符,因此由字符串 Sm 转换为字符串 Dn 有如下三种可行的方案:

  • 在由 Sm 转换的字符串 Dn-1 的末尾增加一个字符,编辑长度计 1,即 C’mn = Cm n-1 + 1;
  • 在由 Sm-1 转换的字符串 Dn 的末尾删去一个字符,编辑长度计 1,即 C”mn = Cm-1 n + 1;
  • 在由 Sm-1 转换的字符串 Dn-1 的末尾修改一个字符,编辑长度计 1,即 C”’mn = Cm-1 n-1 + 1;特别地,如果源字符串的第 m 个字符正好与目标字符串的第 n 个字符相同,则此次不必修改字符,即 C”’mn = Cm-1 n-1

由于编辑距离有路径最短的要求,必须在每一步转换中选择编辑长度最短的方案,以达到局部最优解。因此,Cmn 最终的结果可表示为 Cmn = min(C’mn, C”mn, C”’mn),min(a, b, c) 表示取 a, b, c 中最小的数。因为 Cmn 的结果只与 Cm-1 n、Cm n-1 和 Cm-1 n-1 三个数有关,所以上述式子构成解决编辑距离问题的递推关系。

有了递推关系,就可以从初始条件出发,逐步推算出每一个阶段的编辑路径了。在上文的例子中,从上向下、从左向右逐步填写二维表格最终如下:

图 3 通过递推关系逐步推算出所有单元格中的值

取表格中右下角单元格中的值,即是最终要求的编辑距离。如以上的例子中,字符串 kitten 到字符串 sitting 的编辑距离是 3。

下面是用 Python 语言实现的求解两个字符串编辑距离的程序代码。

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

参考文献
[1] Wikipedia. 编辑距离[EB/OL]. https://zh.wikipedia.org/wiki/%E7%B7%A8%E8%BC%AF%E8%B7%9D%E9%9B%A2
[2] Wikipedia. Edit Distance[EB/OL]. https://en.wikipedia.org/wiki/Edit_distance

Boyer-Moore 子字符串查找算法

前一篇博文中讨论了子字符串查找的问题,并给出了一个能高效地解决这个问题的算法:KMP 算法。我们知道,KMP 算法仅需在被查找字符串中顺序访问其中每个字符一次,便能找到其中匹配指定模式的子字符串。然而令人惊讶的事实是,KMP 并不是解决子字符串查找问题最快的算法,这意味着有时并不需要完整地扫描被查找字符串中的每一个字符便能完成子字符串查找。

Bob Boyer 和 J Strother Moore 在 1977 年设计了一个比 KMP 更快的字符串查找算法[1]。与 KMP 算法一样,这个算法也以设计者的名字命名,得名 Boyer-Moore 算法。Boyer-Moore 算法的主要思想是,在比对被查找字符串与模式中的字符时,启发式地跳过一些不事实上不需要比较的字符,大大减少了查找过程中比较的次数。更难得的是,Boyer-Moore 算法非常容易理解,实现也很简洁。

为了理解 Boyer-Moore 算法,先考察如下的例子:在字符串 S = “http://luodichen.com/blog/” 中查找模式 R = “luodichen”。像之前讨论过的暴力查找算法一样,先从被查找的字符串 0 索引处开始查找;但匹配字符的方向与暴力查找相反——自右向左匹配模式中的字符。如下图所示,在这个例子中当查找索引 i = 0 时,右边首先匹配的是被查找字符串中的字符 S[8] = ‘u’ 与 模式中的字符 R[8] = ‘n’,结果是这两个字符不相匹配。按照暴力查找的做法,当出现了不匹配的情况时,需要做的是将查找索引的值加 1,重新进行匹配,此时不妨也这样做,将查找索引 i 的值加 1,此时 i = 1。现在应该比较哪两个字符呢?比较 S[8] = ‘u’ 与 R[7] = ‘e’,同样不匹配,重复增加 i 的值,直到 i = 7 时,S[8] = ‘u’ 与 R[1] = ‘u’ 匹配。接着逐字向左匹配剩下的字符,最后会发现子字符串匹配成功了。

bm-ani1图 1  暴力算法的小改动——先匹配右边的字符

然而这并没有比暴力算法更快(与暴力算法一样慢)。仔细回想一下上面的操作,实质上是在不断增加查找索引 i 的同时检查 S[8] 与 R[8 – i] 是否匹配,换句话说,就是在 R 中自右向左寻找第一个字符 S[8]。如果在字符串查找开始之前就对模式 R 做一些处理,记住 R 中每一个字符自右向左第一次出现的位置(上例中 ‘u’ 第一次出现的位置是 R[1]),就可以在发生不匹配的情况时直接推算出 i 应当增加的数值,而不必每次只加 1 地尝试。如下图。

bm-ani2图 2 查表并推算出 i 需要增加的值,直接设置 i

以上的例子便是运用了 Boyer-Moore 算法的思想。将这个思路推广到一般情形,为了描述方便,先假设被查找的字符串为 S 假定 S 足够长,匹配模式为 R,R 的长度为 l;查找索引为 i,i 的初始值是 0;函数 m(c) 表示 R 中自右向左第一次出现字符 c 时 R 的索引,若 c 从未在 R 中出现过,返回 -1。Boyer-Moore 算法由以下几个步骤组成:

  1. 找到模式 R 最右匹配的字符 S[i + l – 1] 与 R[l – 1];
  2. 如果匹配,则继续向左检查,直到找到 S[i + l – n] 与 R[l – n] 不匹配或全部字符都匹配成功;
  3. 如果全部字符匹配成功,则子字符串查找到一个结果;否则调用 j = m(S[i + l – n]),得到 j 表示 S 中不匹配的那个字符在 R 中自右向左第一次出现的索引,然后查找索引向右移动 (l – j – 1),重复步骤 1。

Boyer-Moore 算法在应用中通常能跳过大部分字符,因此具有非常快的速度。并且模式相对越长,查找速度越快。以下的图片演示了 Boyer-Moore 算法的一个经典示例:在 “HERE IS A SIMPLE EXAMPLE” 中查找 “EXAMPLE”。

bm-ani3图 3 在 “HERE IS A SIMPLE EXAMPLE” 中查找 “EXAMPLE”

本文所提到的所有算法均以 Java 实现,代码托管于 GitHub,查看

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

参考文献
[1] Wikipedia. Boyer-Moore字符串搜索算法[EB/OL]. http://zh.wikipedia.org/wiki/Boyer-Moore%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95.

KMP 算法:实现高效的子字符串搜索

在计算机日常应用中,我们经常会遇到需要在一篇文章中搜索某个字词的情形,这就是子字符串查找算法运用的实例。例如在字符串 “http://luodichen.com/blog/” 中找出子字符串 “luodichen.com” 第一次出现的位置(索引),通过观察可以很轻松地得到答案是 7。在子字符串查找中,期望查找的子字符串是以“字符串某一部分与期望查找的子字符串完全相同”的规则存在的,这个以子字符串表示的匹配规则称为“模式(Pattern)”。上面查找 “luodichen.com”的例子中,模式就是 “luodichen.com”。

如何编程实现子字符串查找呢?假设有长度为 l 字符串 S,需要在 S 中寻找长度为 m 的子字符串 R 第一次出现的位置(m < l)。粗看起来,这个问题似乎并不难回答。一个直观的做法就是依次设查找索引 i = 0, 1, 2, …, l – m,每次都检查 S 在索引 i 处长度为 m 的子字符串是否与 R 完全相等,如果相等,则说明查找成功,i 就是要找的答案;否则就尝试下一个 i 的值,如果尝试了每一个 i 的值都没有找到答案,说明查找失败,S 中不存在要找的子字符串。这是一种简单粗暴的方法,下文称其为“暴力算法”。

考察“检查在索引 i 处长度为 m 的子字符串是否与 R 完全相等”的实现过程,我们会逐一比较字符 S[i + j] 与 R[j](0 <= j < m)是否相等,会发现这个操作实质上可以看作一个确定有限状态自动机。这个状态机在每比较一个字符时发生一次状态转移:如果比较的两个字符相等,则进入下一个状态,否则匹配失败停机,直到比较完所有的字符,转入成功停机状态。状态机停机之后,只要判断当前的状态是成功还是失败就能得出此次匹配的结果。假设要查找的字符串是 “LUODC”,状态机的图示如下。

图1 在字符串中查找 “LUODC” 时的状态机表示

对于每个 i 的取值,这个操作最少需要 1 次字符比较,最多需要做 m 次字符比较。因此,这种字符串搜索算法在最差的情况下的时间复杂度是 O(ml – m2)。当然,在实际应用中碰到较差的情况是比较罕见的,因为在通常情况下,大部分匹配尝试都会在前几个字符的比较中就会转到失败状态,暴力算法在一般的情形下性能还是可以接受的。

然而,1970 年,S.Cook 在理论上证明一个关于某种特定类型的抽象计算机的结论,该结论暗示了一种在最坏情况下用时也只是与 m + l 成正比的解决子字符串查找问题的算法[1]。D.E.Knuth 与 V.R.Pratt 在这些基础上做了一些改进,提出了一个相对简单而实用的算法。另外,J.H.Morris 也独立发明了相似的子字符串查找算法。后来,这个算法取发明者三人名字的首字母,得名 KMP 算法

考虑以下问题:在字符串 S[] = “AAAAAAAAAB” 中搜索模式 R[] = “AAAAB”。按上文中提到的暴力算法,先测试 S[0…4] 与 R[] 是否相等,直到比较到字符 S[4] 与 R[4] 时,才发现 S[4] 的值是 ‘A’ 而 R[4] 的值是 ‘B’,此时子串 s[0…4] 测试失败,下一步应当测试 S[1…5] 与 R[] 是否相等。在下一轮测试中,又需要依次比较 S[i + 1] 与 R[i](1 <= i <= 5)的值是否相等,并最终以 S[5] 与 R[4] 不相等而匹配失败收场。

等等——我们注意到,在第一轮测试中,其实已经可以知道 S[1…4] 的值是 “AAAA”,与 R[0…3] 的四个字符是完全吻合的,实际上只需要比较 S[5] 与 R[4] 两个字符是否相等就行了,接下来的几轮比较也是如此。这样,通过这个小的改进,省下了多次不必要的字符比较,节省了操作时间。

以上是一个特殊的例子,KMP 算法将这种思路推广到了一般情形,对于任意模式的查找操作都能最大限度地省去不必要的字符比较。

在暴力算法的状态机描述中,假设某一轮测试将 a[i], a[i+1] ,…, a[i+m-1] 依次输入状态机中后,发生了失败停机,则下一轮需要将 a[i+1], a[i+2], …, a[i+m] 输入状态机中重新测试。在最坏的情形下,每轮测试都不得不输入 m – 1 个与上次重复的字符。KMP 算法最大的优势在于,如果把它也用状态机来描述,KMP 状态机是没有失败状态的,它可以连续地接收被查找字符串中的所有字符,直到找到一个匹配的子字符串才停机。在这个过程中,被查找的字符串中竟没有任何重复扫描的字符!下面是一个用 KMP 算法在只由 ‘A’、’B’ 和 ‘C’ 构成的字符串中查找子字符串 “ABABAC” 的状态机的例子。

kmp-fsm-2图2 用 KMP 算法在字符串中查找子字符串 “ABABAC” 时的状态机

KMP 算法按顺序连续(而不回头)地读取被查找字符串中的字符,每读取一个字符都会改变一次状态机的状态,自发地根据当前的状态“决策”最适合的下一个状态以达到找出子字符串的目的。如上图所示,KMP 算法为每一个匹配进度都设置了一个状态,假定要查找的模式 R[] 的长度是 m,那么状态机 DFA 就有 S0, S1, …, Sm-1 一共 m 个状态,其中每个状态都根据不同的输入对应一个转移路径。例如上图中的例子,假设当前的状态为匹配进度 “ABABA_”,那么如果下一个输入正好是 ‘C’,毫无疑问此时子字符串匹配成功,转移到 succeed 状态;如果下一个输入是 ‘B’,意味着当前匹配到了一个 “ABABAB” 的字符串,最佳的决策是丢掉前面两个字符 “AB”,再期望输入一个 ‘A’ 和一个 ‘C’ 即可达到子字符串匹配的目的,因此转移到匹配进度为 “ABAB_” 的状态;如果下一个输入是 ‘A’,意味着当前匹配到了一个 “ABABAA”,的字符串,显然地,这时只能丢掉前五个字符 “ABABA”,只留下字符 “A”,并期望输入 “BABAC” 来达到匹配的目的,因此转移到匹配进度为 “A_” 的状态。

可见,KMP 算法高效的原因是有一个“聪明的”状态机总能根据当前的匹配进度为每种可能的输入选择最佳的匹配方案。那么,现在的问题是如何构建一个任意的模式 R[] 对应的状态机。假设 R 的长度为 m,那么 R 所有可能的匹配进度有匹配前 0 个字符、匹配前 1 个字符、匹配前 2 个字符……匹配前 m 个字符,每个匹配进度对应状态机一个状态,记作 S0, S1, S2, …, Sm。另设构成被查找字符串的字符集为 E,则构成确定有限自动机 DFA 的 5-元组要素如下:

  • 状态集合 Q = {S0, S1, S2, …, Sm}
  • 输入字母表 ∑ = E
  • 开始状态 s = S0
  • 接受状态集合 F = {Sm}

接下来要做的是构造自动机的转移函数。设当前状态为 S,输入的字符为 c 时的状态转移函数为 f(S, c),另设模式 R[0…m-1] 的字符分别为 c0, c1, …, cm-1,显然地,当状态机处于 Si 状态时,说明已经完成了 c0-ci-1 共 i 个字符的匹配,此时如果输入的字符正好与 ci 相等,那么状态机一定会再次完成一次匹配,进入 Si+1 状态。于是可以得出下式:

f(Si, ci) = Si+1    ①
特别地:f(S0, c0) = S1    ②

再考虑状态机处于 S0 状态时,显然只有当输入的字符与 c0 相等时才会进入下一个状态 S1,其他输入都是不匹配的,只会让状态机回到原地。因此对 S0 的其他非 c0 输入又可以得到下式:

f(S0, c) = S0 (c ≠ c0)    ③

那么,在非 S0 状态时的不匹配输入,应当怎样处理呢?显然,状态机不匹配时应当回到当前状态之前某个状态,这正是 KMP 算法的精妙之处。再回过头来看图 2 中的例子,假设当前状态是已匹配 “ABABA_”,已经匹配了 5 个字符,也就是当前的状态是 S5。当输入 c ≠ ‘C’ 时,状态机需要回退到之前某个状态,目前已知的是如果向状态机中依次输入 (‘A’, ‘B’, ‘A’, ‘B’, ‘A’, c) 一定是不匹配的,在输入 c 后能获得最佳匹配结果的状态是将 (‘B’, ‘A’, ‘B’, ‘A’, c) 依次输入重新初始化过的状态机,最终得到的状态,这个状态即是要求的 S5 转换函数 f(S5, c)。因为 5 个输入最多能使状态机转换到 S5,所以使用上述方法推导 S5 的转换函数时,只需要已知 S0-S4 各个状态的转换函数即可!换言之,如果要推导 Sn (n > 0) 的转换函数,最多只需已知 S0, S1, …, Sn-1 即可,有了这个递推关系之后,竟可以只已知 S0 的全部转换函数而推导出其他所有状态的非匹配转换函数!总结以上的方法,当需要求 Sn (n > 0) 的转换函数时,只需将当前已经匹配过的字符,跳过第一个后(即 c1, c2, …, cn)依次输入到已初始化的状态机中,状态机给出的状态即 Sn

设函数 g(Si, cm, cn) = f(f(f(…f(Si, cm), cm+1), cm+2), …, cn) (n > m),则有
f(Si, c) = f(g(S0, c0, ci-1), c) (i > 0, c ≠ ci)   ④

至此就可以从 S1 开始,依次根据已知的状态函数推导出状态机所有状态对全部输入的转换函数了。下面是一个由模式 mPattern 生成 KMP 算法状态机转换函数表的 Java 实现。

KMP 算法的 Java 完整实现包括测试用例已经托管于我的 GitHub,查看

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

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

优先队列与堆排序

队列(Queues)是应用中常见的数据结构,一个队列至少有“入队”和“出队”两个基本操作。队列具有“先入先出(First In First Out, FIFO)”性质,就像排队一样,入队会将新元素插入到队列的末尾,而出队会取出队列中排在最前的(也是最早入队的)一个元素。

优先队列(Priority Queues)的接口与基本队列一样,至少有“入队”和“出队”两个基本操作。与基本队列不同的是,优先队列的出队顺序不是先入先出,而是以队列中元素的健作为优先级出队,键最大(或最小)的元素最先出队,其次是键次大(或次小)的元素。键大优先出队的优先队列称为面向大元素的优先队列;键小优先出队的优先队列称为面向小元素的优先队列。为了方便,在没有特别说明的情况下,下文所有提到的优先队列均指面向大元素的优先队列。

要实现一个高效的优先队列并不十分容易,一个直观而简易的实现方式是使用有序链表。设 L 是一个按从大到小顺序排列的链表,使用这个链表充当优先队列。当有一个元素 N 需要入队时,只需从头到尾遍历队列,找到插入 N 之后不会破坏链表有序性的位置,将 N 插入链表;当需要出队一个元素时,因为链表的有序性保证了第一个元素一定是最大的元素,因此只需直接取出链表中第一个元素返回,并删除这个元素。

使用链表构建的优先队列入队效率比较低,假设队列长度是 n 那么入队平均需要遍历 n / 2 个结点;而它的出队效率又非常高,显然,它出队的时间复杂度是常数 1。造成链表优先队列入队效率底的根本原因是搜索的效率低,在一个有序的数据结构中逐个元素顺序搜索是不明智的。以往的经验告诉我们,在有序的数据集合中进行查找,高效的做法是用二分的思想。而链表不支持随机访问,在数组中运用的二分法查找在链表中是无效的。

实现优先队列,另一个更聪明的办法是用二叉树来组织数据。维护一棵始终满足以下条件的二叉树,就能实现一个较高效的优先队列:

  1. 是一棵完全二叉树;
  2. 每个结点的键都比它的非空子结点的键大。

通常的二叉树是以链式结构组织的,树各个结点的物理存储位置是离散的,每个结点通过保存该结点的两个子结点以及父结点的引用(或“指针”)来彼此关联。而为了实现优先队列,我们按从上到下、从左到右的顺序将一棵二叉树组织到数组里,所有结点都在数组中连续存放,形成一个二叉堆。按习惯,二叉堆又简称“”,下文也遵循习惯使用简称“堆”指二叉堆。之所以用堆的形式来组织优先队列而不是通常的链式结构,是因为堆能更快更容易地实现优先队列入队和出队的操作,具体的理由总结如下:

  1. 完全二叉树除了底部外所有结点的子结点全都非空,且生长点只能在树的底部,用数组来存放它既没有空位,又无需在插入之后移动元素;
  2. 数组支持随机访问,访问效率优于链式结构的二叉树;
  3. 无需每个结点都保存其子结点或父结点的引用,只需对自身的索引进行简单的运算即可找到子结点或父结点;
  4. 插入新元素时,能非常容易地找到插入点。

假设用数组 a[] 来组织上面说到的堆,为了方便,元素 a[0] 置空不用,从 a[1] 开始存放堆的所有元素。这样,堆的根结点即是 a[1],假设存在某个结点 a[n] (n > 1),那么它的父结点就是 a[n / 2],它的左子结点是 a[2 * n],它的右子结点是 a[2 * n + 1]。

实现对优先队列的入队就是当向堆插入一个元素,先将新的元素插入到堆的尾部成为一个新结点。此时,这个结点很可能并不比它的父结点小,因此堆的性质之一“每个结点的键都比它的非空子结点的键大”可能会遭到破坏,必须做一些处理使堆重新满足这个条件。

这些处理称为结点的“上浮”。结点上浮的目的是将新插入的结点移动到合适的位置,使这个结点既大于它所有的子结点,又小于它的父结点。结点上浮的操作算法很简单:比较被上浮的结点与它的父结点的大小,如果当前结点大于父结点,则交换它们的位置;然后重复上述操作,直到当前结点不大于父结点或者当前结点已经是根结点。下面的 Java 代码实现了堆结点上浮的操作。

实现对优先队列的出队就是读出堆顶部的结点,然后删除它。删除一般二叉树的一个结点,就有可能留下两个孤立的子树,此时需要在树中删出一个没有非空子结点或只有一个非空子结点的结点来填补到删除结点后产生的空缺中。删除堆顶的一个结点,同样需要找一个结点来填补空缺,最容易的办法是删出堆底的结点,填补到堆顶空缺的位置,然后堆大小减 1。这时填补到堆顶的结点几乎一定是会比它的左右子结点都小的,不满足优先队列堆要求的条件,需要做一些处理使堆重新满足条件。

这些处理称为结点的“下沉”。结点下沉的目的是将处于堆顶部的小结点向堆底移动,使这个结点既大于它所有的非空子结点,又小于它的父结点。像结点的上浮操作一样,结点的下沉操作也很容易实现。先从结点的左右子结点中找出非空且较大的那一个,被下沉的结点与之交换,重复这个过程,直到当前结点大于它的所有非空子结点或者它的所有子结点均为空。下面的 Java 代码实现了堆结点的下沉操作。

如果将一串乱序数据全部入队到一个优先队列中,然后从优先队列中出队所有的数据,数据出队时将是有序的,这无疑提供了一个新的排序思路。

堆排序就是利用了上述优先队列思想的排序算法。对一个乱序的数组进行堆排序时,分为两个阶段,第一阶段称为建堆,将数组原地组织成一个符合上文中描述的条件的堆;另一个阶段把这个堆当作优先队列,不断地出队元素,并把出队的元素填到因出队而空缺的位置。当堆逐步缩小直至为空时,堆排序完成,数组变成了有序数组。

如何对一个数组实现原地建堆是一个值得思考的问题,为了讨论问题方便,先定义“堆有序”指一个堆满足上文提到的优先队列堆的所有条件。显然,一个大小为 1 的堆一定是堆有序的。如果一个堆 H 的左右两个子堆都是堆有序的,只要对这个堆的根结点做一次下沉操作,堆 H 也一定会转化为一个堆有序的堆。设有一个乱序数组 a[1…n],把它看作一个堆,Hi 表示以 a[i] 为堆顶的子堆,则可以得出 Hn/2+1, Hn/2+2, …, Hn 均是大小为 1 的子堆,换言之,这些子堆都是堆有序的,数组 a 中有半数子堆是堆有序的。为了使整个数组都成为堆有序的堆,只要先后对 a[n/2], a[n/2-1], …, a[1] 执行下沉操作即可。

建堆完成后,就可以开始第二步骤了。将数组当作一个优先队列,出队一个元素 N1,此时 a[n] 处因出队产生了一个空缺,将 N1 填补到 a[n] 处,继续出队 N2,填补到 a[n-1] 处,直到出队 Nn,填补到a[1] 处,数组 a 排序完成。

值得注意的是,在实际运用中,大部分程序设计语言的数组第一个元素的索引并不是 1 而是 0,但只要在上述算法的基础上对索引稍作处理即可实现堆排序。

堆排序无需额外的空间,时间复杂度也能达到比较理想的 O(nlogn) 的级别,是一种优秀的排序算法。

本文提到的全部算法均已用 Java 实现,代码托管于 GitHub,查看

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

排序

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