《算法导论》第十四章

第十四章  数据结构的扩张

一些工程应用需要的只是一些“教科书”中的标准数据结构，比如双链表、散列表或二叉搜索树等，然而也有许多其他的应用需要对现有数据结构进行少许地创新和改造，但是只在很少情况下需要创造出一类全新类型的数据结构。更经常的是，通过存储额外信息的方法来扩张一种标准的数据结构，然后对这种数据结构，编写新的操作来支持所需要的应用。然而对数据结构的扩张并不总是简单直接的，因为添加的信息必须要能被该数据结构上的常规操作更新和维护。

本章讨论通过扩张红黑树构造出的两种数据结构。14.1 节介绍一种支持一般动态集合上顺序统计操作的数据结构。通过这种数据结构，我们可以快速地找到一个集合中的第i小的数，或给出一个指定元素在集合的全序中的位置。14. 2节抽象出数据结构的扩张过程，并给出一个简化红黑树扩张的定理。14.3节使用这个定理来设计一种用于维护由区间（如时间区间）构成的动态集合的数据结构。给定一个要查 询的区间，我们能快速地找到集合中一个能与其重叠的区间。

14. 1 动态顺序统计

第9章中介绍了顺序统计的概念。n个元素集合中的第i(i∈{1, 2, ...，n})个顺序统计量就是简单地规定为该集合中的具有第i小关键字的元素。对于一个无序的集合，我们知道能够在O(n)的时间内确定任何的顺序统计量。本节将介绍如何修改红黑树，使得可以在O(lgn)时间内确定任何的顺序统计量。我们还将看到如何在O(lgn)时间内计算一个元素的秩， 即它在集合线性序中的位置。

图14-1显示了一种支持快速顺序统计操作的数据结构。顺序统计树(order-statistic tree)T只是简单地在每个结点上存储附加信息的一棵红黑树。在红黑树的结点x中，除了通常属性x. key、x. color、x.p、 x. left和x. right之外，还包括另一个属性x. size。这个属性包含了以x为根的子树(包括x本身)的(内)结点数，即这棵子树的大小。如果定义哨兵的大小为0，也就是设置T.nil.size为0，则有等式：

图14-1 一棵顺序统计树， 它是一棵扩张的红黑树。浅阴影结点为红色，深阴影结点为黑色。除了通常的红黑树所具有的属性外，每个结点x还具有属性x. size,即以x为根的子树(除哨兵外)的结点个数

在一棵顺序统计树中，我们并不要求关键字各不相同。(例如，图14-1 中的树就包含了两个值为14的关键字和两个值为21的关键字。）在有相等关键字的情况下，前面秩的定义便不再适合。为此，我们通过定义一个元素的秩为在中序遍历树时输出的位置，来消除原顺序统计树定义的不确定性。如图14-1所示，存储在黑色结点的关键字14的秩为5,存储在红色结点的关键字14的秩为6。

查找具有给定秩的元素

在说明插入和删除过程中如何维护size信息之前，我们先来讨论利用这个附加信息来实现的两个顺序统计查询。首先一个操作是对具有给定秩的元素的检索。过程OS SELECT(x, i)返回一个指针，其指向以x为根的子树中包含第i小关键字的结点。为找出顺序统计树T中的第i小关键字，我们调用过程OS-SELECT(T. root, i)。

OS-SELECT的第1行计算以x为根的子树中结点x的秩r。x. left. size的值是对以x为根的子树进行中序遍历后排在x之前的结点个数。因此，x left. size+1就是以x为根的子树中结点x的秩。如果i=r，那么结点x就是第i小元素，这样第3行返回x。如果i<r，那么第i小元素在x的

左子树中，因此在第5行中对x left进行递归调用。如果i>r,那么第i小元素在x的右子树中。因为在对以x为根的子树进行中序遍历时，共有r个元素排在x的右子树之前，故在以x为根的子树中第i小元索就是以x right为根的子树中第（i-r)小元素。 第6行通过递归调用来确定这个元素。

为明白OS-SELECT是如何操作的，考察在图14-1所示的顺序统计树上查找第17小元素的查找过程。以x为根开始，其关键字为26，i=17。 因为26的左子树的大小为12,故它的秩为13。因此，秩为17的结点是26的右子树中第17- 13=4小的元素。递归调用后，x为关键字41的结点，i=4。因为41的左子树大小为5，故它的秩为6。这样，可以知道秩为4的结点是41的左子树中第4小元素。再次递归调用后，x为关键字30的结点，在其子树中它的秩为2。如此，再进行一次递归调用，就能找到以关键字38的结点为根的子树中第4- 2=2小的元素。它的左子树大小为1，这意味着它就是第2小元素。最终，该过程返回一个指向关键字为38的结点的指针。

因为每次递归调用都在顺序统计树中下降一层， OS-SELECT的总时间最差与树的高度成正比。又因为该树是一棵红黑树，其高度为O(gn)，其中n为数的结点数。所以，对于n个元素的动态集合，OSSELECT的运行时间为O(lgn)。

确定一个元素的秩

给定指向顺序统计树T中结点x的指针，过程OS-RANK返回对T中序遍历对应的线性序：中x的位置。

这个过程工作如下。我们可以认为x的秩是中序遍历次序排在x之前的结点数再加上1(代表x自身)。OS-RANK保持了以下的循环不变式：

第3~6行while循环的每次迭代开始，r为以结点y为根的子树中x. key的秩。

下面使用这个循环不变式来说明OS RANK能正确地工作。

初始化：第一次迭代之前，第1行置r为以x为根的子树中x. key的秩。第2行置y=x，使得首次执行第3行中的测试时，循环不变式为真。

保持：在每一次while循环迭代的最后，都要置y=y. p。这样，我们必须要证明：如果r是在循环体开始处以y为根的子树中x. key的秩，那么r是在循环体结尾处以y. p为根的子树中x. key的秩。在while循环的每次迭代中，考虑以y. p为根的子树。我们对以结点y为根的子树

已经计数了以中序遍历次序先于x的结点个数，故要加上以y的兄弟结点为根的子树以中序遍历次序先于x的结点数，如果y. p也先于x，则该计数还要加1。如果y是左孩子，y.p和y.p的右子树中的所有结点都不会先于x，r保持不变;否则，y是右孩子，并且y.力和y. p左子树中的所有结点都先于x，于是在第5行中，将当前的r值再加上y. p. left. size+1。

终止：当y=T.root 时，循环终止，此时以y为根的子树是一棵完整树。因此，r的值就是这棵完整树中x. key的秩。

作为一个例子，当我们在图14-1的顺序统计树上运行OS-RANK，以确定关键字为38的结点的秩时，在while循环的开始处，y. key和r的一系列值如下：

该过程返回的秩为17。

因为while 循环的每次迭代耗费O(1)时间，且y在每次迭代中沿树上升一层，所以最坏情况下OS-RANK的运行时间与树的高度成正比：在n个结点的顺序统计树上为O(lgn)。

对子树规模的维护

给定每个结点的size 属性后，OS-SELECT和OS-RANK能迅速计算出所需的顺序统计信息。然而除非能用红黑树上经过修改的基本操作对size属性加以有效的维护，否则，我们的工作将变得没意义。下面就来说明在不影响插入和删除操作的渐近运行时间的前提下，如何维护子树规模。

由13.3 节可知，红黑树上的插入操作包括两个阶段。第一阶段从根开始沿树下降，将新结点插入作为某个已有结点的孩子。第二阶段沿树上升，做一些变色和旋转操作来保持红黑树性质。

在第一阶段中为了维护子树的规模，对由根至叶子的路径，上遍历的每一个结点x，都增加x. size属性。新增加结点的size为1。由于一条遍历的路径上共有O(lgn)个结点，故维护size属性的额外代价为O(lgn)。

在第二阶段，对红黑树结构上的改变仅仅是由旋转所致，旋转次数至多为2。此外，旋转是一种局部操作:它仅会使两个结点的size 属性失效，而围绕旋转操作的链就是与这两个结点关联。参照13.2节的LEFT-ROTATE(T, x)代码，增加下面两行：

图14-2说明了size 属性是如何被更新的。对RIGHT-ROTATE做相应的改动。

图14-2 在旋转过程中 修改子树的大小。与围绕旋转的链相关联的两个结点，它们的size 属性要更新。这些更新是局部的，仅需要存储在x

和y中的size信息，以及图中三角形子树的根中的size 信息

因为在红黑树的插入过程中至多进行两次旋转，所以在第二阶段更新size属性只需要O(1)的额外时间。因此，对一棵有n个结点的顺序统计树插入元素所需要的总时间为O(lgn)，从渐近意义上看，这与一般的红黑树是一样的。

红黑树上的删除操作也包括两个阶段：第一阶段对搜索树进行操作，第二阶段做至多三次旋转，其他对结构没有任何影响(见13.4节)。第一阶段中，要么将结点y从树中删除，要么将它在树中上移。为了更新子树的规模，我们只需要遍历一条由结点y(从它在树中的原始位置开始)至根的简单路径，并减少路径上每个结点的size属性的值。因为在n个结点的红黑树中，这样一条路径的长度为O(lgn)，所以第一阶段维护size属性所耗费的额外时间为O(lgn)。第二阶段采用与插入相同的方式来处理删除操作中的O(1)次旋转。所以对有n个结点的顺序统计树进行插入与删除操作，包括维护size 属性，都只需要O(lgn)的时间。

练习

14.1-1  对于图14-1中的红黑树T，说明执行OS SELECT(T. root, 10) 的过程。

14.1-2  对于图 14-1中的红黑树T和关键字x. key为35的结点x，说明执行OS-RANK(T, x)的过程。

14.1-3  写出OS-SELECT的非递归版本。

14.1-4  写出一个递归过程OS-KEY-RANK(T, k)， 以一棵顺序统计树T和一个关键字k作为输入，要求返回k在由T表示的动态集合中的秩。假设T的所有关键字都不相同。

14.1-5  给定n个元素的顺序统计树中的一个元素x和一个自然数i，如何在O(lgn)的时间内确定x在该树线性序中的第i个后继？

14.1-6  在OS-SELECT或OS-RANK中，注意到无论什么时候引用结点的size属性都是为了计算一个秩。相应地，假设每个结点都存储它在以自己为根的子树中的秩。试说明在插入和删除时，如何维护这个信息。(注意，这两种操作都可能引起旋转。)

14. 1-7  说明如何在O(n lgn)时间内，利用顺序统计树对大小为n的数组中的逆序对(见思考题2-4)进行计数。

*14.1-8 现有一个圆上的n条弦，每条弦都由其端点来定义。请给出一个能在O(n lgn)时间内确定圆内相交弦对数的算法。(例如，如果n条弦都为直径，它们相交于圆心，则正确的答案为假设任意两条弦都不会共享端点。

14. 2 如何扩张数据结构

对基本的数据结构进行扩张以支持一些附加功能，在算法设计过程中是相当常见的。在下一节中，我们将再次通过对数据结构进行扩张，来设计一种支持区间操作的数据结构。本节先来介绍这种扩张过程的步骤，同时证明一个定理，在许多情况下，该定理使得我们可以很容易地扩张红黑树。

扩张一种数据结构可以分为4个步骤：

1. 选择一种基础数据结构。

2. 确定基础数据结构中要维护的附加信息。

3. 检验基础数据结构上的基本修改操作能否维护附加信息。

4. 设计一些新操作。

以上仅作为一个一般模式，读者不应盲目地按照上面给定的次序来执行这些步骤。大多数的设计工作都包含试探和纠错的成分，过程中的所有步骤通常都可以并行进行。例如，如果我们不能有效地维护附加信息，那么确定附加信息以及设计新的操作（步骤2和步骤4）就没有任何意义。然而，这个4步法可以使读者在扩张数据结构时，目标明确且有条不紊。

在14. 1节设计顺序统计树时，我们就依照了这4个步骤。对于步骤1，选择红黑树作为基础数据结构。红黑树是一种合适的选择，这源于它能有效地支持一些基于全序的动态集合操作，如MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR。

对于步骤2，添加了size属性，在每个结点x中的size属性存储了以x为根的子树的大小。一般地，附加信息可使得各种操作更加有效。例如，我们本可以仅用树中存储的关键字来实现OS-SELECT和OS-RANK，但它们却不能在O(lgn)运行时间内完成。有时候，附加信息是指针类信息，而不是具体的数据，如练习14.2-1。

对于步骤3，我们保证了插入和删除操作仍能在O(lgn)时间内维护size 属性。比较理想的是，只需要更新该数据结构中的几个元素就可以维护附加信息。例如，如果把每个结点的秩存储在树中，那么OS SELECT和OS-RANK能够较快运行，但是当插入一个新的最小元素时，会导致树中每个结点的秩发生变化。如果我们存储的是子树的大小，则插入一个新的元素时仅会使O(lgn)个结点的信息发生改变。

对于步骤4，我们设计了新操作OS-SELECT和OS-RANK.归根结底，一开始考虑去扩张一个数据结构的原因就是为了满足新操作的需要。然而有时并不是为了设计一些新操作，而是利用附加信息来加速已有的操作，如练习14.2-1。

对红黑树的扩张

当红黑树作为基础数据结构时，可以证明，某些类型的附加信息总是可以用插入和删除操作来进行有效的维护，从而使步骤3非常容易做到。下面定理的证明与14. 1节用顺序统计树来维护size属性的论证类似。

定理14. 1（红黑树的扩张）设 f是n个结点的红黑树T扩张的属性，且假设对任一结点x，f的值仅依赖于结点x、x left和x. right的信息，还可能包括工left. f和x.right. f。那么，我们可以在插入和删除操作期间对T的所有结点的f值进行维护，并且不影响这两个操作的

O(lgn)渐近时间性能。

证明    证明的主要思想是， 对树中某结点x的f属性的变动只会影响到x的祖先。也就是说，修改xf只需要更新x.p.f,改变x.p.f的值只需要更新x.pp.f，如此沿树向上。一旦更新到T. root. f,就不再有其他任何结点依赖于新值，于是过程结束。因为红黑树的高度为O(lgn)，所以改变某结点的f属性要耗费O(lgn)时间，来更新被该修改所影响的所有结点。

一个结点 x插入到树T由两个阶段构成（见13.3节)。第一阶段是将x作为一个已有结点x. p的孩子被插入。工f的值可以在0(1)时间内计算出。因为根据假设，x f仅依赖于x本身的其他属性信息和x的子结点中的信息，而此时x的子结点都是哨兵T.nmil。 当x.f被计算出时，这个变

化就沿树向上传播。这样，插入第一阶段的全部时间为O(lgn)。在第二阶段期间，树结构的仅有变动来源于旋转操作。由于在一次旋转过程中仅有两个结点发生变化，所以每次旋转更新f属性的全部时间为O(lgn)。又因为插入操作中的旋转次数至多为2，所以插入的总时间为O(lgn)。

与插入操作类似，删除操作也由两个阶段构成（见13.4节)。在第一阶段中，当被删除的结点从树中移除时，树发生变化。如果被删除的结点当时有两个孩子，那么它的后继移人被删除结点的位置。这些变化引起f的更新传播的代价至多为O(lgn),因为这些变化对树的修改是局部的。第二阶段对红黑树的修复至多需要三次旋转，且每次旋转至多需要O(lgn)的时间就可完成f的更新传播。因此，和插入一样，删除的总时间也是O(lgn)。

在很多情况下，比如维护顺序统计树的size属性，一次旋转后更新的代价为0(1)，而并不是定理14.1中所给出的O(lgn)。练习14. 2-3就给出这样的一个例子。

练习

14. 2-1  通过为结点增加指针的方式，试说明如何在扩张的顺序统计树上，支持每一动态集合查询操作MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR在最坏时间O(1)内完成。顺序统计树上的其他操作的渐近性能不应受影响。

14. 2-2  能否在不影响红黑树任何操作的渐近性能的前提下，将结点的黑高作为树中结点的一个属性来维护？说明如何做，如果不能，请说明理由。如何维护结点的深度？

*14.2-3 设为一个满足结合律的二元运算符，a为红黑树中每个结点上的一个要维护的属性。假设在每个结点x上增加一个属性f，使x. f=x₁. ax₂. a...x_m.a，其中心x₁，x₂，...，x_m是以x为根的子树中按中序次序排列的所有结点。说明在一次旋转后，如何在O(1)时

间内更新f属性。对你的扩张稍做修改，使得它能够应用到顺序统计树的size 属性中。

*14.2-4 希望设计一个操作 RB-ENUMERATE(x, a, b), 来对红黑树进行扩张。该操作输出所有的关键字k，使得在以x为根的红黑树中有a≤k≤b。描述如何在日(m+ lgn)时间内实现RB- ENUMERATE，其中m为输出的关键字数目，n为树中的内部结点数。(提示：不需要向红黑树中增加新的属性。)