算法导论 总结索引 | 第三部分 第十四章：数据结构的扩张

1、通过存储 额外信息的方法来扩张一 种标准的数据结构，然后对这种数据结构，编写新的操作来支持所需的应用。因为添加的信息 必须要能被该数据结构上的常规操作更新和维护

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

1、动态顺序统计

1、对于一个无序的集合，能够在O(n) 时间内 确定任何的顺序统计量；可以在 O(lgn) 时间内 确定任何的顺序统计量。还将看到 如何在 O(lgn) 时间内计算一个元素的秩，即它在集合线性序中的位置

2、一个顺序统计树T 只是简单地 在每个结点上 储存附加信息的一棵红黑树。在红黑树的结点x中，除了通常属性 x.key、x.color、x.p、x.left 和 x.right 之外，还包括一个属性 x.size。这个属性 包含了以x为根的子树（包括x本身）的（内）结点数，即这棵子树的大小。如果定义哨兵的大小为0，也就是 设置T.nil.size为0，则有等式：

在一棵顺序统计树中，并不要求关键字各不相同。在有相等关键字的情况下，前面秩的定义 不再适合。为此，通过定义 一个元素的秩 为中序遍历时输出的位置，来消除 原顺序统计树 定义的不确定性
存储在黑色结点的关键字14的秩为5，存储在红色结点的关键字14的秩为6

3、过程OS-SELECT(x, i)返回一个指针，其指向以x为根的子树中 包含第i小关键字的结点

OS-SELECT的非递归版本：

OS-SELECT(x, i)
    r = x.left.size + 1
    while i != r
        if i < r
            x = x.left
        else x = x.right
            i = i - r
        r = x.left.size + 1
    return x
1
2
3
4
5
6
7
8
9

x.left.size + 1就是 以x为根的子树中结点x的秩。如果i > r，那么 第i小元素在x的右子树中。因为 对以x为根的子树 进行中序遍历时，其有 i-r 元素排在x的右子树之前，故在 以x为根的子树中 第i小元素就是 以x.right为根的子树中的 第 (i-r) 小元素

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

4、确认一个元素的秩
给定 指向顺序统计树T中 结点x的指针，过程 OS-RANK 返回 对T中序遍历对应的线性序中x的位置

x的秩是在中序遍历次序排在x之前的结点数再加上1

循环不变式：
while循环 的每次迭代开始，r为以结点x为根的子树中 x.key的秩

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

保持：在每一次while循环迭代的最后，都要置 y=y.p。如果r是在循环体开始 以y为根的子树中x.key的秩，那么 r是在循环结束时以y.p为根的子树中x.key的秩
考虑以y.p为根的子树，故要加上 以y的兄弟结点为根的子树 以中序遍历次序先于x的结点数，如果y.p也先于x， 则该计数还要加1
如果y是左孩子，y.p和y.p的右子树中的所有结点都不会先于x，r保 持不变；否则，y是右孩子，并且y.p和y.p左子树中的所有结点都先于x， 于是在第5行中，将当前的r值再加上y.p.left.size + 1

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

给定元素的值的情况下 求秩
一个递归过程OS-KEY-RANK(T，k)，以一棵顺序统计树T和一个关键字k作为输入，返回k在由T表示的动态集合中的秩。假设T的所有关键字都不相同

OS-KEY-RANK(T, k)
    if k == T.key
        return T.root.left.size + 1
    elseif k < T.key
        return OS-KEY-RANK(T.left, k)
    else return T.root.left.size + 1 + OS-KEY-RANK(T.right, k)
1
2
3
4
5
6

5、对子树规模的维护
说明在不影响插入和删除橾作的渐近运行时间的前提下，如何维护子树规模
红黑树上的插入操作 包括两个阶段：第一阶段 从根开始沿树下降，将新结点插入 作为某个已有结点的孩子。第二阶段沿树上升，做一些变色和旋转操作 来保持红黑树性质

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

红黑树结构上的修改变 仅仅是旋转所致，旋转次数至多为2（上一节中的 情况2 + 情况3）。旋转是一种局部操作：它只会使得两个结点的size属性失效，而围绕旋转操作的链 就是与这两个结点关联
照图13.2节的LEFT-ROTATE(T,x)代码，增加下面两行：

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

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

6、在OS-SELECT或OS-RANK中，注意到无论什么时候引用结点的size属性都是为了计算一个秩。相应地，假设每个结点都存储它在以自己为根的子树中的秩

1）在插入时维护这个信息：
红黑树上的插入操作包括两个阶段。第一阶段从根开始沿树下降，将新结点插入作为某个已有结点的孩子。第二阶段沿树上升，做一些变色和旋转操作来保持红黑树性质。
在第一阶段中 为了维护结点在以自己为根的子树中的秩，对由根至叶子的路径上遍历的每一个结点x，如果新结点将插入到它的左子树中，则它的rank加1，否则它的rank不变。由于一条遍历的路径上共有O ( lgn ) 个结点，故维护rank属性的额外代价为O ( lgn ) 。
在第二阶段，对红黑树结构上的改变仅仅是由旋转所致，旋转次数至多为2。此外，旋转是一种局部操作：它仅会使两个结点rank属性失效，而围绕旋转操作的链就是与这两个结点关联。参照13.2节的LEFT-ROTATE(T，x)代码，增加下面一行：

y.rank = y.rank + x.rank 
1

2）在删除时维护这个信息：
红黑树上的删除操作 也包括两个阶段：第一阶段对搜索树进行操作，第二阶段做至多三次旋转，其他对结构没有任何影响。第一阶段中，要么将结点y从树中删除，要么将它在树中上移
为了更新结点在以自己为根的子树中的秩，我们只需要遍历一条由结点y（从它在树中的原始位置开始）至根的简单路径，如果当前结点是下个结点的左孩子，则下个结点的rank减1，否则下个结点的rank不变。因为在n个结点的红黑树中，这样一条路径的长度为 O(lgn)，所以第一阶段维护rank属性 所耗费的额外时间为 O(lgn)。第二阶段 采用与插入相同的方式来处理删除操作中的 O(1) 次旋转。所以对有n个结点的顺序统计树 进行插入和删除操作，包括维护rank属性，都只需要 O(lgn) 的时间

2、如何扩张数据结构

1、通过 对数据结构进行扩张，来设计一种支持区间操作的数据结构。扩张一种数据结构可以分为4个步骤：
1）选择一种基础数据结构
2）确定基础数据结构中要维护的附加信息
3）检验基础数据结构上的各传统操作能否维护附加信息
4）设计新的操作

对于步骤1，选择红黑树作为基础数据结构。红黑树是一种合适的选择，这源于 它能有效地支持一些基于全序的动态集合操作， 如MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR

对于步骤2，添加了size属性，在每个结点x中由size属性 存储了以x为根的子树的大小。仅用树中存储的关键字来实现 OS-SELECT和OS-RANK，但 却不能在O(lgn)运行时间内完成。有时，附加信息是指针变量值，而不是具体的数值

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

• MINIMUM：用一个指针指向顺序统计树中的最小元素。每次向树中插入元素时与其进行比较，如果新插入的元素更小，则将MINIMUM指向新插入的元素，否则不做修改。如果删除MINIMUM，则将MINIMUM指向它的后继
• MAXIMUM：用一个指针指向顺序统计树中的最大元素。每次向树中插入元素时与其进行比较，如果新插入的元素更大，则将MAXIMUM指向新插入的元素，否则不做修改。如果删除MAXIMUM，则将MAXIMUM指向它的前驱
• SUCCESSOR：给每个结点增加指向后继的指针。每次向树中插入或删除结点时，根据插入或删除结点的父结点的SUCCESSOR，可以在时间内 O(1) 维护插入或删除结点的SUCCESSOR
• PREDECESSOR：给每个结点增加指向前驱的指针。每次向树中插入或删除结点时，根据插入或删除结点的父结点的PREDECESSOR，可以在时间内 O(1) 维护插入或删除结点的PREDECESSOR

2、红黑树扩张：设f是n个结点的红黑树T 扩张的属性，且假设对任一结点x，f的值 仅依赖于结点x、x.left和x.right的信息，还可能 包括x.left.f和x.right.f。那么，可以在 插入和删除操作期间对T的所有结点中的f值进行维护，并且不影响这两种操作的 O(lgn)渐近时间性能

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

一个结点x插入到树T由两个阶段构成。第一阶段是 将x作为一个已有结点x.p 的孩子被插入。因为根据假设，x.f仅依赖于x本身的其他属性信息 和 x的子结点中的信息。在第二阶段期间． 树结构的仅有变动 来源于 旋转操作。由于 在一次旋转过程中 仅有两个结点发生变化． 所以每次旋转更新f属性的全部时间为 O(lgn)

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

在很多情况下，比如 维护顺序统计树的size属性，一次旋转后更新的代价为O(1)，而并不是定理14.1中所给出的O(lgn)

3、能否 在不影响红黑树任何操作的渐近性能的前提下，将结点的黑高 作为树中结点的一个属性来维护？如何维护结点的深度
能在不影响红黑树任何操作的渐进性能的前提下，将结点的黑高作为树中结点的一个属性来维护：
插入和删除操作 只对从根结点到某一叶结点的路径上的结点（包括左右子树）进行修改，即 O(lgn) 个结点。修改每个结点的黑高 只需要 O(1) 时间。因此，总的修改时间为 O(lgn)

3、区间树

1、假设区间都是闭的，将集合推广至 开和半开区间上 是自然和直接的。区间便于表示 占用一定时间段的事件

我们可以把一个区间［t1, t2] 表示成一个对象，其中属性 i.low ＝ t1 为低端点，属性 i.high = t2 为高端点

任何两个区间i和i’满足 区间三分律，即下面三条性质之一成立：
a. i和i’重叠。
b. i在i’的左边(也就是说i.high<i’.low)。
c. i在i’的右边(也就是说i.high<i’.low)。

2、区间树 是一种对动态集合进行维护的红黑树，其中每个元素x都包含一个区间x.int。区间树支持下列操作：

• INTERVAL-INSERT(T,x)：将包含区间属性int的元素x插入到区间树T中
• INTERVAL-DELETE(T,x)：从区间树T中删除元素x
• INTERVAL-SEARCH(T,i)：返回一个指向区间树T中元素x的指针，使x.int与i重叠； 若此元素不存在，则返回T.nil
  

3、步骤1：基础数据结构
红黑树，其每个结点z包含一个区间属性x.int，且x的关键字为区间的低端点z.int.low。因此，该数据结构按中序遍历列出的 就是按低端点的次序排列的区间

步骤2：附加信息
每个结点x中除了 自身区间信息之外，还包含 一个值x.max，它是以x为根的子树中所有区间的端点的最大值

步骤3：对信息的维护
通过给定区间 x.int 和 结点x的子结点的最大值，可以确定x.max值：

x.max = max(x.int.high, x.left.max, x.right.max)
1

插入和删除操作的运行时间为O(lgn)。事实上，在一次旋转后，更新x.max仅需O(1)时间

步骤4：设计新的操作
仅需要 唯一的新操作 INTERVAL-SEARCH(T, i)，用来找出树T中 与区间i重叠的那个结点

INTERVAL-SEARCH(T,i)
1 x = T.root
2 while x ≠ T.nil and i does not overlap x.int
3     if x.left ≠ T.nil and x.left.max ≥ i.low 
4         x = x.left
5     else x = x.right
6 return x
1
2
3
4
5
6
7

查找与i重叠的区间x的过程中 从以x为根的树根开始，逐步向下搜索。当找到一个重叠区间 或者 x指向T.nil时过程结束。由于基本循环的每次迭代 耗费O(1)的时间，又因为n个结点的 红黑树的高度为O(lgn)，所以 INTERVAL-SEARCH 过程耗费O(lgn)时间

假设 要找一个与区间[22, 25]重叠的区间。开始时x为根结点，它包含区间[16, 21]，与i不重叠。由于x.left.max=23 大于 i.low=22，所以这时以 这棵树根的左孩子 作为x继续循环。现在结点x包含区间[8, 9]，仍不与i重叠。x.left.max=10 小于 i.low=22，因此 以x的右孩子作为新的x继续循环。现在，由于 结点x所包含的区间[15, 23]与i重叠，过程结束并返回这个结点

要明白INTERVALSEARCH的正确性， 必须理解 为什么该过程只需检查 一条由根开始的简单路径即可。该过程的基本思想是在任意结点x上，如果x.int不与i重叠，则查找 总是沿着一个安全的方向进行：如果 树中包含一个与i重叠的区间， 则该区间必定会被找到

定理：INTERVALSEARCH(T, i) 的任意一次执行，或者 返回一个其区间与i重叠的结点，或者 返回T.nil，此时 树T中没有任何结点的区间与i重叠

证明：当 x=T.nil 时while循环终止的情况
对第2~5行的while循环 使用如下的循环不变式：
如果树T 包含与i重叠的区间，那么以x为根的子树x中 将包含此区间

初始化：在第一次迭代之前，第1行置x为T的根，循环不变式成立

保持：如果 x.left=T.nil，则以x为根的子树 不会包含i重叠的区间，所以置x为 x.right 以保持 这个不变式。假设x.left≠T.nil且x.left.max < i.low。对x左子树的任一区间i’，都有

i'.high ≤ x.left.max < i.low
1

根据区间三分律，i和i’不重叠。因此，x的左子树不会包含与i重叠的任何区间，置x为 x.right 使循环不变式保持成立

如果在以 x.left 为根的子树中 没有与i重叠的区间，则树的其他部分 也不会包含与i重叠的区间。有x.left.max ≥ i.low，根据max属性的定义，在x的左子树中 必定存在某区间i’，满足：

i'.high = x.left.max ≥ i.low
1

因为i’和i’不重叠，又因为i’.high < i.low 不成立，所以根据区间三分律有：i.high < i’.low。区间树是 以区间的低端点为关键字的，所以搜索树根随意向 对x右子树中的任意区间i’，有（右子树有部分区间重叠 都没事）

i'.high < i'.low ≤ i''.low
1

根据区间三分律，i和i’不重叠
不管x的左子树中是否存在与i重叠的区间，置x为x.left保持循环不变式成立

终止：如果循环在 x=T.nil 时终止，则表明在以x为根的子树中，没有与i重叠的区间。循环不变式的对等情况 说明了 T中不包含与i重叠的区间，故返回 T.nil 是正确的

4、作用于区间树的结点且在 O(1) 时间内 更新max属性的过程LEFT-ROTATE的伪代码：

LEFT-ROTATE(T, x)
    y = x.right
    x.right = y.left
    if y.left ≠ T.nil
        y.left.p = x
    y.p = x.p
    if x.p == T.nil
        T.root = y
    elseif x == x.p.left
        x.p.left = y
    else x.p.right = y
    y.left = x
    x.p = y
    // 下两行区别
    y.max = x.max
    x.max = max(x.int.high, x.left.max, x.right.max)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5、改写 INTERVAL-SEARCH 的代码，使得当所有区间都是开区间时，它也能正确地工作

INTERVAL-SEARCH(T, i)
    x = T.root
    while x ≠ T.nil and i does not overlap x.int
        if x.left ≠ T.nil and x.left.max > i.low // 闭区间变开区间唯一区别：>=变成>
            x = x.left
        else x = x.right
    return x

1
2
3
4
5
6
7
8

对一个给定的区间i，返回一个与i重叠且具有最小低端点的区间；或者当这样的区间不存在时返回T.nil

MIN-INTERVAL-SEARCH(T, i)
    x = INTERVAL-SEARCH(T, i)
    while x ≠ T.nil and i overlap x.left.int // 求最小，只要考虑左子树的区间就行
            x = x.left
    return x
1
2
3
4
5

6、给定一棵区间树T和一个区间i，描述如何在 O(min(n,klgn)) 时间内 列出T中 所有与i重叠的区间（之前只要找一个），其中k为输出的区间数

ALL-INTERVAL-SEARCH(T, i)
    QUEUE Q
    ENQUEUE(Q, T.root)
    ARRAY A
    while !QUEUE-EMPTY(Q)
        x = DEQUEUE(Q)
        if i overlap x.int
            PUSH(A, x)
        if x.left ≠ T.nil and x.left.max ≥ i.low // 区别
            ENQUEUE(Q, x.left)
        if x.right ≠ T.nil and x.int.low ≤ i.high // 区别
            ENQUEUE(Q, x.right)
    return A
1
2
3
4
5
6
7
8
9
10
11
12
13

需要对 树有可能的部分 进行完整的遍历，中间满足条件的加入（各个结点的low是有序的，high不是）

7、对区间树T和一个区间i，修改有关区间树的过程 来支持新的操作 INTERVAL-SEARCH-EXACTLY(T，i)，它返回一个指向T中结点x的指针，使得 x.int.low = i.low 且 x.int.high = i.high；或者，如果T 不包含这样的区间时 返回T.nil。所有的操作（包括INTERVAL-SEARCH-EXACTLY）对于包含n个结点的区间树的运行时间 都应为 O(lgn)

如果 x.left.max >= i.low 还找不到，不代表 i’.low > i.high，可能 有重叠但是不相等

8、说明如何维护一个支持操作MIN-GAP的一些数的动态集合Q，使得该操作能输出Q中 两个最接近的数之间的差值。例如Q={1, 5, 9, 13, 22}，则MIN-GAP返回 18-15=3，因为15和18是Q中两两个接近的数。要使得操作INSERT, DELETE,SEARCH和MIN-GAP尽可能亢效． 并分析它们的运行时间

1）数据结构选择
选择一种平衡二叉搜索树，例如红黑树。红黑树的基本性质使得插入、删除和搜索操作都能够在O(log n)的时间内完成。为了支持MIN-GAP操作，需要在每个结点中存储一些额外的信息

2）扩展红黑树
在每个结点中增加以下额外信息：

• min_gap：该子树中任意两个相邻元素之间的最小差值。
• left_max：该子树中左子树的最大元素。
• right_min：该子树中右子树的最小元素。

3）插入操作（INSERT）
插入操作和标准红黑树插入操作类似，但需要在插入后更新相关结点的min_gap、left_max和right_min信息

def insert(root, key):
    # 标准红黑树插入操作
    root = rb_insert(root, key)
    # 更新min_gap, left_max, right_min
    update_info(root)
    return root

def update_info(node):
    if not node:
        return
    # 更新左子树和右子树的信息
    update_info(node.left)
    update_info(node.right)
    
    node.left_max = max(node.left.left_max if node.left else float('-inf'), node.key)
    node.right_min = min(node.right.right_min if node.right else float('inf'), node.key)
    
    left_gap = node.key - (node.left_max if node.left else float('-inf'))
    right_gap = (node.right_min if node.right else float('inf')) - node.key
    node.min_gap = min(left_gap, right_gap, node.left.min_gap if node.left else float('inf'), node.right.min_gap if node.right else float('inf'))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4）删除操作（DELETE）
删除操作和标准红黑树删除操作类似，但需要在删除后更新相关结点的min_gap、left_max和right_min信息

def delete(root, key):
    # 标准红黑树删除操作
    root = rb_delete(root, key)
    # 更新min_gap, left_max, right_min
    update_info(root)
    return root
1
2
3
4
5
6

5）搜索操作（SEARCH）
搜索操作不需要额外修改，直接使用红黑树的搜索操作，时间复杂度为O(log n)

6）MIN-GAP操作
MIN-GAP操作只需要返回根结点的min_gap属性即可

def min_gap(root):
    return root.min_gap if root else float('inf')
1
2

9、运行时间分析
INSERT: 插入操作需要O(log n)的时间来插入结点，并且在回溯时更新min_gap、left_max和right_min属性，故总时间复杂度为O(log n)
DELETE: 删除操作需要O(log n)的时间来删除结点，并且在回溯时更新min_gap、left_max和right_min属性，故总时间复杂度为O(log n)
SEARCH: 搜索操作在红黑树中需要O(log n)的时间
MIN-GAP: MIN-GAP操作只需要访问根结点的min_gap属性，时间复杂度为O(1)