数据结构的扩充与联合

作者：　转载 　 更新日期：　2004-7-19　　出处：　《算法与数据结构》



在许多工程性应用的场合下，本书中所介绍的一些基本抽象数据类型和标准数据结构就已够用了。但也有一些情况需要使用新的数据结构或新的抽象数据类型。通常没有必要创造一个全新的数据结构去满足应用上的要求，只要对某个特定的标准数据结构进行适当改造就可以达到预期的目的。本节以实例来介绍对标准数据结构进行扩充和联合的基本思想和方法。
一、动态选择树——红黑树的扩充
1、动态选择树的定义
在第七章中，我们讨论了选取n个元素中第ｉ小元素的算法SELECT。我们可以在O(n)时间内从n个未排序的元素中找出第ｉ小元素。如果对红－黑树进行适当的扩充，我们可以在O(logn)时间内就找到第ｉ小元素。另外，对于一个给定元素，我们也可以在O(logn)时间内确定它的秩，即它在排好序后的n个元素中的位置。
这种扩充后的红－黑树T称为动态选择树。它的每个结点除了红－黑树结点中的域外，还增加了一个size域。一个结点P↑的size域中存储以P↑为根的子树(包括P↑本身)中结点的个数。动态选择树T的结点类型可形式地定义为：
type
nodetype=reckrd
element:elementtype;
size:integer;
color:(red,black)
leftchild,rightchild,parent:↑nodetype
end;
如果我们定义当p=nil时，p↑．size=o，则对动态选择树T中任何结点P↑有：
p↑．size=（p↑．lefchild）↑．size+（p↑．rightchild）↑．size+l。
为了下确处理关于nil的边界条件，在每次实际存取size时要对指针进行nil测试。
动态选择树T的类型可定义为指向T的根结点的指针，即：
type
DYNAMIC-TREE=↑nodetype；
图11-21　是一棵动态选择树的示意图。
图11-21　动态选择树
2、用动态选择树找第i小元素
下面的函数DYNAMIC-SELECT(i,p)返回一个指向动态选择树T中以结点P为根的子树中第i小元素所在结点的指针。要找出T中第i小元素，只要调用DYNAMIC-SELSCT(i,t)即可。
function DYNAMIC-SELECT(i:integer;p:nodetype):nodetype;
var
j:integer;
begin
(1)j:=(p↑．leftchild)↑．size+1;
(2)if i=j then return(p)
(3)else if i＜j then return (DYNAMIC-SELECT(i,p↑．leftchild))
(4)else return (DYNAMIC-SELECT(i-j,p↑．rightchild))
end;｛DYNAMIC-SELECT｝
上述算法DYNAMIC-SELECT在第(1)行中计算以P↑为根的子树中结点P↑的秩j。如果i＜j，则第i小元素在P↑的左子树中，故在第(3)行对p↑．leftchild进行递归调用。如果i＞j，则第i小元素在P↑的右子树中。因为在对以P↑为根的子树进行中序遍身时，有i个元素排在P↑的右子树之前，故在以P↑为根的子树中第i小元素即为以p↑．rightchid为根的子树中第i-j小元素。在算法的第(4)行中处理这种情形。
为了进一步说明DYNAMIC-SELECT的工作过程，我们来看它如何在图11-21的动态选择树中找第17小的元素。开始时，P为根结点。其中元素的键值为26，i=17。由于此时P↑的左子树的大小为12，故P的秩为13。这样，我们就可以断定秩为17的结点是P↑的右子树中第17-13=4小元素。在进入递归调用时，P↑为元素键值为41的结点，i=4。此时P↑的左子树的大小为5，故其秩为6。于是我们知道秩为4的结点是P↑的左子树中第4小元素。在第二次进入递归调用时，P↑为元素键值为30的结点，其秩为2。这样再次进入递归调用时，P↑为元素键值为38的结点，i=2。此时P↑的左子树大小为1，故P↑的秩为2，也就是说此时的结点P↑即我们要找的元素所在的结点。至此，函数返回指向这个结点的指针P↑。
由于DYNAMIC-SELECT的每一次递归调用都在动态选择树中下降了一层，故在最坏情况下，它所需的计算时间与树的高度成正比。若动态选择树中有几个结点，则由于它是一棵红-黑树，故其高度为O(logn) 。因此对于含有几个元素的动态有序集，DYNAMIC-SELECT的计算时间为O(logn) 。
3、用动态选择树确定元素的秩
给定指向动态选择树T中一个结点的指针P，下面的函数DYNAMIC-RANK返回在对T进行中序遍身得到的结点序列中P↑的位置。
function DYNAMIC-RANK(p:↑nodetype;T:DYNAMIC-TREE):integr
var
i:integer;
q: nodetype
begin
(1)i:=(p↑．leftchild)↑．size+1;
(2)q:=p;
(3)while q <>T do
(4)begin
(5)　　if q=(q↑．parent)↑．rightchild then
(6)　　　i:=i+((q↑．parent)↑．Leftchild)↑．size+1
(7)　　q:=q↑．parent
(8) end;
(9)return(i)
end; ｛DYNAMIC-RANK｝
上述算法的工作过程如下：P↑的秩可以看作是在对树T进行中序遍身时，排在P↑之前的结点个数再加上1。算法中维持了一个不变量，即i始终为以结点q为根的子树中结点P↑的秩。在每一次执行while循环体时，都要检查以q↑．parent为根的子树。我们已经对以结点q↑为根的子树中，按中序排在结点P↑之前的结点个数进行了计数。因此对于 q↑．parent而言，还要加上q↑的兄弟结点为根的子树中，按中序排在P↑之前的结点个数。另外，如果q↑．parent也前于P↑，则该计数还要再加上1。如果q↑是个左儿子，则q↑．parent或其右子数中所有结点都不前于P↑，故i保持不动；否则，q↑是个右儿子，此时q↑．parent及其右子树中所有结点，按中序都排在 P↑之前，于是在第(6)行中交当前的i值再加上 ((q↑．parent)↑．Leftchild)↑．size+1 ，在第(7)行置q:=q↑．parent，使得在一轮循环中仍保持不变量为真。当q=T时，该函数返回的i值，就是结点P在树T中的秩。
现在我们来看一个例子。当我们在图11-21的动态选择树中用DYNAMIC-RANK来确定键值为38的结点P↑的秩时，q↑．element和i 的值变化如下：
迭代 q↑．element i
1234 38304126 24417
返回的秩为17无误。
在算法DYNAMIC-RANK中，每执行一次while循环体需要O(1)时间，且q在每次迭代中沿树上升一层，故在最坏情况下，算法所需的时间与树的高度成正比。含有n个结点的动态选择树的高度为O(logn)，故DYNAMIC-RANK所需的时间为O(logn)。
若用动态选择树T表示一个有序集S，则对于任意X∈S，要确定它在S中的秩，可以先在T中搜索存储储元素X的结点P，然后调用DYNAMIC-RANK确定其秩。也可将搜索X的过程与确定秩的过程合在一起，用自顶向下的方式来确定X的秩。其实现的缃节留作练习。
4、维护动态选择树
 在红-黑树中增加了size域后，我们就能迅速地找第i小元素，并能迅速地确定一个元素或一个结点的秩。这要求对红- 黑树的其它运算能有效地维护size域。因此我们要考虑如何修改红- 黑树的插入和删除算法，使得它们能正确地维护结点的size域，又不影响插入和删除运算的渐近时间。
在第五章中我们已经讨论过，红-黑树上的插入运算分两个阶段完成：第一阶段由根开始沿树向下搜索，将存储插入元素的新结点作为某个已有结点的儿子插入；第二阶段由新插入的结点开始沿树上升，作一些旋转变换并改变一些结点的颜色以保持红-黑性质。
在第一阶段中要维护结点的size域，只要在由根至叶的搜索路径上，使每个结点的size域值增1，新结点的size域值置为1。由于所经过的路径上共有O(logn)个结点，故用于维护size域所耗费的时间为O(logn)。在第二阶段中，红-黑树结构上的改变是由旋转变换所引起的。
在第二阶段中，最多只要作两次旋转变换。旋转变换是一种局部操作，经旋转变换后，size域值会发生变化的只有旋转链两头的结点。例如，在第五章中的左旋变换算法LEFT-ROTATE的最后增加下面的语句即可维护结点的size域：
y↑．size :=x↑．size;
x↑．size :=x↑．leftchild↑．size+x↑．rightchild↑．size+1;
图11-22说明了这个更新过程。对RIGHT-ROTATE所作的修改是对称的。
图11-22　旋转变换中size域的更新
红-黑树上的删除运算也是分两个阶段进行的：第一阶段在红黑树中搜索要删除的结点Y并将它从红-黑树中删去；第二阶段通过最多3次旋转变换来维持红-黑性质。
在第一阶段中要维护结点的size域，只要在从根到叶的搜索路径上将各结点size域值减1即可。由于O含有n个结点的红-黑树高度为O(logn)，所以在删除的第一阶段维护size域要花费O(logn) 时间。第二阶段中的O(1)次旋转变换可象插入运算一样处理。这样，在动态选择树中进行插入和删除运算并维护size域仍然只要O(logn)时间。
二、扩充数据结构的方法
1、基本思想
在设计一个算法时，常需要对一些标准的数据结构进行扩充以支持一些新的功能。通常我们可以按以下4个步骤实现对一种数据结构的扩充：
(1)、选择基础数据结构；
(2)、确定要在基础数据结构中存储的附加信息；
(3)、验证可以通过修改基础数据结构上的基本运算来维护附加信息；
(4)、设计新的运算。
以上给出的只是扩充数据结构的一般模式，在实际操作时应灵活运用。许多设计过程是采用试探的方法，并行地考虑以上4个步骤。例如，如果我们不能有效地维护附加信息，就没有必要在第(2)步中确定如何在基础数据结构中存储附加信息，也没有必要在第(4)步中设计新的运算。然而，以上这4个步骤可以使我们在扩充数据时思路清晰，注意力集中。我们在设计动态选择树时就是遵循上述步骤进行的。
在步骤(1)中，我们选择了红-黑树作为基础数据结构。这是由于红-黑树能有效地支持MIN，SUCCESSOR，PREDECESSOR，INSERT，各DELETE等动态集合运算。
在步骤(2)中，为了保存子树规模的附加信息，我们在红-黑树的结点中增加了size域。一般来讲，附加信息可以使某些运算更加有效。例如，如果不增加子树规模的信息，我们也可以用红-黑树中存储的元素键值来找第i小元素，但所需的时间就不止是O(logn)了。有时候附加的信息是指针类信息，而不是具体的数据。
在步骤(3)中，我们保证了增加size域后的红-黑树在作插入和删除运算时，只要花O(logn)的时间就能维护size域中的信息，因而不影响插入和删除运算的渐近复杂性。一般情况下，我们应选择恰当的附加信息，使得在维护附加信息时，数据结构的变化尽可能地小。这样就可以使维护附加信息所需的时间尽可能少。例如，如果我们选择每个结点的秩作为附加信息，则能更好地实现DYNAMIC-SELECT和DYNAMIC-RANK运算。但是如果插入一个新的最小元素会使树中每个结点的秩发生变化。如果我们存储的是子树的规模，则插入一个新元素的运算只会影响到O(logn)个结点。
在步骤(4)中，我们设计了新的运算DYNAMIC-SELECT和DYNAMIC-RANK。扩充后的红-黑树能有效地支持这两个运算。一般情况下，我们是为了有效地支持某些新运算才去扩充数据结构的。但有时也可以通过对数据结构的扩充，利用附加信息来加速已有运算的执行速度，实现某种时间和空间效率上的折衷。
2、对红-黑树的扩充
在对数据结构进行扩充时，常选红-黑树作为基础数据结构。此时，步骤(3)的主要工作是验证在扩充后的红-黑树中作插入和删除运算时，能有效地维护附加信息。下面我们给出一个较一般的结果，使得我们用红-黑树作为基础数据结构进行扩充时，容易完成步骤(3)的验证工作。
定理11-3(红-黑树的扩充)
设T是一棵有几个结点的红-黑树，对T进行扩充后，每个结点增加了一个域f，用于存储附加信息。假设在扩充后的红-黑树T中，任一结点P中域f的内容可以仅用结点P，p↑．leftchild和p↑．rightchild中的内容(包括p↑．leftchild↑．f和p↑．rightchild．f)来计算，则在作插入和删除运算时，我们可以在不影响这两个运算的O(logn)渐近性能的情况下，对T中所有结点的f域值进行维护。
证明：在红-黑树T中插入一个新结点P是分两个阶段进行的。在第一阶段中，P作为树T中已存在的一个结点的儿子被插入。p↑．f的值可在O(1)时间内算出。因为根据假设p↑．f的值仅依赖理P中其它域的信息以及P的儿子结点中的信息。而结点P新插入时其两个儿子结点都是nil 。一旦确定了p↑．f后，由定理的假设知，p↑．parent↑．f的值可能发生变化，且可在O(1)时间内根据p↑．f的值对其更新。此后p↑．parent↑．parent↑．f又可能发生变化，且也可在O(1)时间内根据p↑．parent↑．f的新值进行更新。这个f域值的更新过程沿树T向上传播。当T的根结点的f域值被更新后，就不再有别的结点要依赖于其新的f域值，这个更新过程就结束了。由于T的高度为O(logn)，故插入的第一阶段中维护f域需要O(logn)时间。在第二阶段中，树结构的改变是由旋转变换引起的。每次旋转变换使T中两个结点发生变化，因此，每次旋转变换需要O(logn)时间来维护f域。每次插入运算至多执行了两次旋转变换，因此，每次插入运算需要O(logn)时间来维护f域。
与插入运算类似地，删除运算也由两个阶段完成。在第一阶段中，被删除的结点由其后继结点替代，且其后继结点从T中删去。此时涉及两个结点的变化，域f更新向上传播最多涉及O(logn)结点。因此，维护f域需要O(logn)时间。第二阶段中至多需要3次旋转变换来维持红-黑性质。每次旋转变换需要O(logn)时间来维护f域。因此，每次删除运算需要O(logn)时间来维护f域。
在许多情况下，每次旋转变换只需要O(1)时间来维护f域，而不需要O(logn)时间。例如在动态选择树中，每次旋转变换只需要O(1)时间来维护size域。
三、区间树
根据前面讨论的扩充数据结构的一般方法，我们可以对红-黑树进行扩充，以支持由区间构成的动态集合上的运算。一个闭区间是由实数对t1和t2,t1≤t2,表示的实数集合。
［t1, t2］=｛t∈R, t1≤t≤t2｝
不含闭区间的两个端点的称为开区间。不含闭区间的一个端点的区间称为半开区间。在下面的讨论中，我们假设所有的区间都是闭区间。区间可以用于表示占用一段连续时间的事件。例如，我们可以将特定时间发生的事件记录起来，构成一个时间区间数据库。通过对这个数据库的查询可以找出在特定时间内发生了什么事件。用我们下面要讨论的区间树可以有效地维护这样一个数据库。
我们可以用一个记录i来表示区间［t1, t2］，其中，i．low= t1存储区间的低端点，
i．high= t2存储区间的高端点。对于两个区间i1和i2，当i1．low≤i2．high 且i2．low≤i1．high时，区间i1和i2重叠。否则i1和i2不重叠。更确切地说，对于任意两个区间i1和i2，下面的3种情况中有且只有一种情况发生：
(1)、i1和i2重叠;
(2)、i1．high＜i2．low;
(3)、i2．high＜i1．low;
图11-23的(a)，(b)和(c)分别展示了这3种情况
图11-23 　区间的相对位置
为了有效地表示由区间组成的动态集合，我们将红-黑树扩充成为一棵区间树，用区间树的结点来存储区间元素的有关信息。因此，存储在区间树结点中元素类型可定义为：
type
elementtype=record
low:real
high:rea
end;　
图11-24是用区间树表示一个区间集合的例子。
图11-24 　用区间树表示动态区间集合
下面我们要讨论如何按照扩充数据结构的4步模式实现区间树以及区间树上运算的设计。
 步骤(1)、基础数据结构
我们选择红-黑树作为区间树的基础数据结构，使我们能够按照区间左端点的自然顺序，将区间集合作为一个有序集来处理，从而能有效地在一个区间集合中搜索一特定区间。
步骤(2)、附加信息
在区间树的每个结点P中，除了区间元素的信息外，还增加了一个域p↑．max，用来存储区间树以P为根的子树中所有区间端点的最大值。由于任一区间的高端点不小于其低端点，所以p↑．max中存储的是以P为根的子树中所有区间右端点的最大值。因此区间树中结点类型可说明为：
type
nodetype=record
element:elementtype;
max:real;
leftchild,rightchild,parent:↑nodetype
end;
区间树的数据类型可用指向根结点的指针来说明：
INTERVAL-TREE=↑nodetype
步骤(3)、维护附加信息
给定区间树中任一结点P，及其儿子结点的max域值，即可确定p↑．max的值如下：
p ↑．max=max(p↑．element↑．high,p↑．leftchild↑．max,p↑．rightchild↑．max)
因此，由定理11-3即知，在有几个结点的区间树中执行插入和删除运算时，维护max域中的附加信息需要O(logn)时间。事实上，在执行一次旋转变换后，维护max域只需要O(1)时间。
步骤(4)、设计新运算
在树间树表示的区间集合中，需要支持一个新的运算INTERVAL SEARCH(i，T)，用来找出T中与区间i重叠的区间。如果T中没有与区间i重叠的区间，则返回nil。
function INTERVAL-SEARCH(i:elementtype;T:INTERVAL-TREE):↑nodetype;
var
p:↑nodetype;
begin
(1)P:=T;
(2)while(p< >nil)and(i与p↑element不重叠)do
(3)　if(p↑leftchild< >nil)and(p↑leftchild max>=i low)
(4)　　then p:=p↑leftchild
(5)　else p:=p↑rightchild
(6)return(p)
end;｛INTERVAL-SEARCH｝
上述算法从区间树的根结点开始，向下搜索与区间i重叠的区间。当找到一个重叠区间或遇到空指针时，算法结束。由于每执行一次while循环体需要O(1)时间，含有几个结点的红-黑树的高度为O(logn)，故INTERVAL-SEARCH所需的时间为O(logn)。
在说明INTERVAL-SEARCH的正确性之前，我们先来看一下在图11-24所示的区间树上，它是如何工作的。假设我们要在该区间树中找出一个与区间i=［22,25］重叠的区间。开始时，P为根结点，相应的区间为［16，21］，它与区间i不重叠。由于p↑．leftchild↑．max=23＞i．low=22故循环进入P的左子树。此时，P所指的结点包含区间［8，9］，仍然与区间i不重叠。此时，p↑．leftchild↑．max=10＜i．low=22故循环进入P的右子树。此时P所指结点存储的区间为［15，23］，它与区间i重叠。因此，算法结束并返回P所指的结点。
下面我们再来看一个不成功搜索的例子。假设我们要在图11-24所示的区间树中找出一个与区间i=［11,14］重叠的区间。开始搜索时P为根结点，相应的区间为［16，21］，它与区间i不重叠。由于p↑．leftchild↑．max=23＞i．low=11，故转向P的左子树中搜索。(注意此时右子树中没有与区间i重叠的区间，为什么?)在左子树中，P所指的结点包含的区间［8,9］与i不重叠，且p↑．leftchild↑．max=10＜i ．low=11，因而转向右子树(注意此时左子树中没有与i重叠的区间)。区间［15,23］也不与i重叠，且它的左儿子为nil，故转向右子树，循环结束，返回nil。
要证明算法INTERVAL-SEARCH的正确性，就必须证明为什么算法只要检查一条从根开始的路径上的区间就够了。这可以表述为如下的结论：
在INTERVAL-SEARCH(i,T)的每次while循环中：
(1) 如果执行了第(4)行的向转语句，则P的左子树中有与i重叠的区间或P的左、右子树中都没有与区间i重叠的区间；
(2)如果执行了第(5)行的向右转语句，则P的左子树中没有与区间i重叠的区间。
我们先来考虑第(2)种情况。如果在while循环中执行了第(5)行的语句，则由第(3)行的分支条件可知，p↑．leftchild=nil或p↑．leftchild↑．max＜i．low。若p↑．leftchild=nil，则P的左子树中没有任何区间，当然也没有与i重叠的区间。若p↑．leftchild≠nil，且p↑．leftchild↑．max＜i．low，则P的左子树中包含的任一区间 有，i1．high≤p↑．leftchild↑．max＜i．low如图11-25(a)所示。由任意两个区间相对位置的3种情况可知，此时区间i与i1不重叠。因此，在这种情况下，P的左子树中没有与i重叠的区间。
现在我们来考虑第(1)种情况。如果在while循环中执行了第(4)行的语句，而且P的左子树中没有与i重叠的区间，我们要证明此时P的右子树中也没有与i重叠的区间。事实上，由第(3)行的分支条件知，执行第(4)行的语句时，我们有，p↑．leftchild↑．max≥i．low。由max域的定义知，P的左子树中有一区间i1，使得i1．high=p↑．leftchild↑．max≥i．low，如图11-25(b)所示。由于i与i1不重叠，且i1．high＜i．low为成立，由两区间相对位置的3种分类情况可知，此时必有i．high＜i1．low。因为区间树是以区间的低端点值为序的，所以P的右子树中任一区间i2，有i2．low≥i1．low。由此可得，i．high＜i2．low。因此区间i2与i不重叠。换句话说，此时，P的右子树中没有与i重叠的区间。
图11-25　while循环中区间的重叠情况
上述的性质(1)和(2)保证了在INTERVAL-SEARCH中沿P的某个儿子结点搜索也找不到重叠区间，从而证明了算法INTERVAL-SEARCH的正确性。
四、数据结构的联合
在实际应用中，有些问题看起来很简单，但要选择一个合适的数据结构来实现它却很困难。对于这类问题，即使一个好的数据结构，也只能使其中的部分运算容易实现，而要实现另一些运算却很麻烦，或效率不高。在这种情况下，我们可以将两个或更多个不同的数据结构联合起来使用，从而取得较好的效果。数据结构的联合问题比较复杂，通常要根据实际选择合适的数据结构并将它们恰当地联合在一起。下面我们用一个例子来说明这个问题。
假设有一个围棋俱乐部，其中每一个成员的级别都不相同，新参加者的级别最低。俱乐部中每个成员都可以向比他高一级的成员挑战。如果挑战者获胜，则交换两人的级别。
我们可以将这个问题表述为一个抽象数据类型，基础模型是俱乐部中成员的名字(字符串)到级别(整数)的一个映射。该抽象数据类型应支持以下3个运算：
(1)、ADD(name)，名字为name的人加入围棋俱乐部，并赋予他最低级别(级别的数目最大)。
(2)、CHALLENGE(name)，这是一个函数，当成员name的级别为i时，其函数值为i-1级成员的名字。
(3)、EXCHANGE(i)，交换i级与i-1级两个成员的名字。
前两个运算的参数是字符串，而第三个运算的参数是一个整数。
如果用数组LADDER来表示上述映射关系，LADDER［i］表示级别为i的成员的名字，另外，再用一个计数器记录俱乐部中成员总数，那么执行ADD和EXCHANGE运算都可以在O(1)时间内完成。但执行CHALLENGE运算就比较麻烦。如果俱乐部中有几个成员，在最坏情况下，CHALLENGE要用O(n)时间去找出被挑战者的名字。
如果用散列表来表示这个映射，并使散列表的桶数与俱乐部中成员总数差不多相等，则执行ADD运算平均需要O(1)时间。执行CHALLENGE运算时，我们先用O(1)平均时间找到name所在的单元，再用O(n)时间找到比name高一级的成员的名字。因此，执行CHALLENGE运算需要O(n)时间。执行EXCHANGE运算时，我们要找出级别为i和i-1的两个成员的名字，因此也需要O(n)时间。
以上两个数据结构都不能有效地实现所有运算。但是如果将这两个数据结构联合起来，就可以获得很好的效果。
我们在散列表的每个单元中存储由成员名字及其级别组成的记录。数组LADDER中的每个单元LADDER［i］中存储一个指向散列表中级别为i的成员所在的单元，如图11-26所示。
图11-26　两种数据结构的联合
这样，在联合起来的数据结构中，执行ADD(name)时，把name插入到散列表中，并根据游标 next (见图(11-26)所指的位置在数组LADDER中添加一个指向新单元的指针，共用O(1)平均时间。执行CHALLENGE(name)时，先用O(1)平均时间在散列表中找到name所在的单元，得到name的级别i，再按指针LADDER［i-1］所指的位置，用O(1)时间找到被挑战者的名字，总共也用O(1)平均时间。执行EXCHANGEi时，先由LADDER［i］和LADDER［i-1］找到级别为i和i-1的成员在散列表中所处的单元，然后交换这两个单元中的级别以及LADDER［i］和LADDER［i-1］中的指针。因此，执行EXCHANGE运算在最坏情况下只需要O(1)时间。