开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【算法学习】数据结构的扩张 -> 正文阅读

[数据结构与算法]【算法学习】数据结构的扩张

参考算法导论第14章数据结构的扩张

文章目录

1. 动态顺序统计
1.1 查找具有给定秩的元素
1.2 确定一个元素的秩
1.3 对子树规模的维护

2. 如何扩张数据结构
对红黑树的扩张

3. 区间树
3.1 步骤一：基础数据结构
3.2 步骤二：附加信息
3.3 步骤三：对信息的维护
3.4 步骤四：设计新的操作

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

这里讨论通过扩张红黑树构造出的两种数据结构：

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

1. 动态顺序统计

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

图14-1显示了一种支持快速顺序统计操作的数据结构。顺序统计树 order-statistic tree $T$ 只是简单地在每个结点上存储附加信息的一棵红黑树。在红黑树的结点 $x$ 中，除了通常属性 $x.key,\ x.color,\ x.p,\ x.left,\ x.right$ 以外，还包括另一个属性 $x . s i z e$ ，这个属性包含了以 $x$ 为根的子树（包括 $x$ 本身）的（内）结点数，即这棵子树的大小。如果定义哨兵的大小为 $0$ ，也就是设置 $T . n u l l . s i z e = 0$ ，则有等式： $x . s i z e = x . l e f t . s i z e + x . r i g h t . s i z e + 1$

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

1.1 查找具有给定秩的元素

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

OS-SELECT(x, i)
	r = x.left.size + 1
	if i == r
		return x
	else if i < r
		return OS-SELECT(x.left, i)
	else return OS-SELECT(x.right, i - r)

OS-SELECT 的第一行计算以 $x$ 为根的子树中结点 $x$ 的秩 $r$ 。 $x . l e f t . s i z e$ 的值是对「以 $x$ 为根的子树」进行中序遍历后、排在 $x$ 之前的结点个数。因此， $x . l e f t . s i z e + 1$ 就是以 $x$ 为根的子树中结点 $x$ 的秩。如果 $i = r$ ，那么结点 $x$ 就是第 $i$ 小元素，这样第三行返回 $x$ 。如果 $i < r$ ，那么第 $i$ 小元素在 $x$ 的左子树中，因此在第五行中对 $x . l e f t$ 递归调用。如果 $i > r$ ，那么第 $i$ 小元素在 $x$ 的右子树中。因为在对以 $x$ 为根的子树进行中序遍历时，共有 $r$ 个元素排在 $x$ 的右子树之前，故在以 $x$ 为根的子树中第 $i$ 小元素，就是以 $x . r i g h t$ 为根的子树中第 $(i ? r)$ 小元素。第六行通过递归调用来确定这个元素。

为明白 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$ 。
如此，再进行一次递归调用，结点 $x$ 的关键字为 $38$ ，它的左子树大小为 $1$ ，这意味着它就是当前子树的第 $2$ 小元素。
最终，该过程返回一个指向关键字为 $38$ 的结点的指针。

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

1.2 确定一个元素的秩

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

OS-RANK(T, x)
	r = x.left.size + 1
	y = x
	while y != T.root
		if y == y.p.right
			r = r + y.p.left.size + 1
		y = y.p
	return r

这个过程工作如下。我们可以认为： $x$ 的秩是「中序遍历次序排在 $x$ 之前的结点数」再加上 $1$ （代表 $x$ 自身）。OS-RANK 保持了以下的循环不变式：第 $\sim 6$ 行 while 循环的每次迭代开始， $r$ 为以结点 $y$ 为根的子树中 $x . k e y$ 的秩。

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

初始化：第一次迭代之前，第 $1$ 行置 $r$ 为以 $x$ 为根的子树中 $x . k e y$ 的秩。第 $2$ 行置 $y = x$ ，使得首次执行第 $3$ 行中的测试前，循环不变式为真。
保持：在每一次 while 循环迭代的最后，都要置 $y = y . p$ 。这样，我们必须要证明：如果 $r$ 是在循环体开始处「以 $y$ 为根的子树」中 $x . k e y$ 的秩，那么到循环体结尾处 $r$ 是「以 $y . p$ 为根的子树」中 $x . k e y$ 的秩。
在 while 循环的每次迭代中，考虑以 $y . p$ 为根的子树。我们对「以结点 $y$ 为根的子树」已经计数了中序遍历次序中先于 $x$ 的结点数，故要加上「以 $y$ 的兄弟结点为根的子树」以中序遍历次序先于 $x$ 的结点数，如果 $y . p$ 也先于 $x$ ，则该计数还要加 $1$ 。
- 如果 $y$ 是左孩子，则 $y . p$ 和 $y . p$ 的右子树中的所有结点都不会先于 $x$ ， $r$ 保持不变；
- 否则 $y$ 是右孩子，并且 $y . p$ 和 $y . p$ 的左子树中的所有结点都先于 $x$ ，于是在第 $5$ 行中，将当前的 $r$ 值再加上 $y . p . l e f t . s i z e + 1$ 。
终止：当 $y = T . r o o t$ 时，循环终止，此时以 $y$ 为根的子树是一棵完整树。因此， $r$ 的值就是这棵完整树中 $x . k e y$ 的秩。

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

迭代	$y . k e y$	$r$
1	38	2
2	30	4
3	41	4
4	26	17

该过程返回的秩为 $17$ 。

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

1.3 对子树规模的维护

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

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

在第一阶段中为了维护子树的规模，对由根至叶子的路径上遍历的每个结点 $x$ ，都增加 $x . s i z e$ 属性。新增加结点的 $s i z e$ 为 $1$ 。由于一条遍历的路径上共有 $O(\log n)$ 个结点，故维护 $s i z e$ 属性的额外代价为 $O(\log n)$ 。
在第二阶段，对红黑树结构上的改变仅仅是由旋转所致，旋转次数至多为 $2$ 。此外，旋转是一种局部操作：它仅会使两个结点的 $s i z e$ 属性失效，而围绕旋转操作的链就是与这两个结点关联。参照（算导13.2节的）LEFT-ROTATE(T, x) 代码，增加下面两行：
```
y.size = x.size
x.size = x.left.size + x.right.size + 1
```
图14-2说明了 $s i z e$ 属性是如何被更新的。对 RIGHT-ROTATE 做相应的改动。

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

红黑树的删除操作也包括两个阶段：第一阶段对搜索树进行操作，第二阶段做至多三次旋转，其他对结构没有任何影响（参见算导13.4节）。

第一阶段中，要么将结点 $y$ 从树中删除，要么将它在树中上移。为了更新子树的规模，我们只需要遍历一条由结点 $y$ （从它在树中的原始位置开始）至根的简单路径，并减少路径上每个结点的 $s i z e$ 属性的值。因为在 $n$ 个结点的红黑树中，这样一条路径的长度为 $O(\log n)$ ，所以第一阶段维护 $s i z e$ 属性所耗费的额外时间为 $O(\log n)$ 。
第二阶段中，采用与插入相同的方式来处理删除操作中的 $O (1)$ 次旋转。

所以，对有 $n$ 个结点的顺序统计树进行插入和删除操作，包括维护 $s i z e$ 属性，都只需要 $O(\log n)$ 的时间。

2. 如何扩张数据结构

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

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

选择一种基础数据结构；
确定基础数据结构中要维护的附加信息；
检验基础数据结构上的基本修改操作能否维护附加信息。
设计一些新操作。

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

（算导14.1节）设计顺序统计树时，我们就依照了这四个步骤。

对于步骤一，选择红黑树作为基础数据结构。红黑树是一种合适的选择，这源于它能有效地支持一些基于全序的动态集合操作，如 MINIMUM, MAXIMUM, SUCCESSOR, PREDECESSOR 。
对于步骤二，添加了 $s i z e$ 属性，在每个结点 $x$ 中的 $s i z e$ 属性存储了以 $x$ 为根的子树的大小。一般地，附加信息可使得各种操作更加有效。例如，我们本可以仅用树中存储的关键字来实现 OS-SELECT, OS-RANK ，但它们却不能在 $O(\log n)$ 运行时间内完成。有时候，附加信息是指针类信息，而不是具体的数据（如算导练习14.2-1）。
对于步骤三，我们保证了插入和删除操作仍能在 $O(\log n)$ 时间内维护 $s i z e$ 属性。比较理想的是，只需要更新该数据结构中的几个元素，就可以维护附加信息。例如，如果把每个结点的秩存储在树中，那么 OS-SELECT 和 OS-RANK 能够较快运行，但是当插入一个新的最小元素时，会导致树中每个结点的秩发生变化。如果我们存储的是子树的大小，则插入一个新的元素时仅会使 $O(\log n)$ 个结点的信息发生改变。
对于步骤四，我们设计了新操作 OS-SELECT 和 OS-RANK 。归根到底，一开始考虑去扩张一个数据结构的原因，就是为了满足新操作的需要。然而有时并不是为了设计一些新操作，而是利用附加信息来加速已有的操作（如算导练习14.2-1）。

对红黑树的扩张

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

定理14.1（红黑树的扩张 Augmenting a red-black tree ）设 $f$ 是 $n$ 个结点的红黑树 $T$ 扩张的属性，且假设对任一结点 $x$ ， $f$ 的值仅依赖于结点 $x,\ x.left,\ x.right$ 的信息，还可能包括 $x.left.f,\ x.right.f$ 。那么，我们可以在插入和删除操作期间，对 $T$ 的所有结点的 $f$ 值进行维护，并且不影响这两个操作的 $O(\log n)$ 渐近时间性能。
证明：证明的主要思想是，对树中某结点 $x$ 的 $f$ 属性的变动只会影响到 $x$ 的祖先 a change to an f attribute in a node x propagates only to ancestors of x in the tree 。也就是说，修改 $x . f$ 只需要 $x . p . f$ 因此更新，改变 $x . p . f$ 的值只需要 $x . p . p . f$ 因此更新，如此沿树向上 changing x.f may require x.p.f to be updated, but nothing else; updating x.p.f may require x.p.p.f to be updated, but nothing else; and so on up the tree 。一旦更新到 $T . r o o t . f$ ，就不再有其他任何结点依赖于新值，于是过程结束。因为红黑树的高度为 $O(\log n)$ ，所以改变某结点的 $f$ 值要耗费 $O(\log n)$ 时间、来更新「被该修改所影响的所有结点」。

一个结点 $x$ 插入到树 $T$ ，由两个阶段构成（算导13.3节）。

第一阶段是将 $x$ 作为一个已存结点 $x . p$ 的孩子来插入。 $x . f$ 的值可以在 $O (1)$ 时间内计算出。因为根据假设， $x . f$ 仅依赖于 $x$ 本身的其他属性信息和 $x$ 的子结点中的信息，而此时 $x$ 的子结点都是哨兵 $T . n u l l$ 。当 $x . f$ 被计算出时，这个变化就沿树向上传播。这样，插入第一阶段的全部时间为 $O(\log n)$ 。
在第二阶段期间，树结构的仅有变动来源于旋转操作。由于在一次旋转过程中仅有两个结点发生变化，所以每次旋转更新 $f$ 属性的总时间为 $O(\log n)$ 。又因为插入操作中的旋转次数至多为 $2$ ，所以插入的总时间为 $O(\log n)$ 。

与插入操作类似，删除操作也由两个阶段构成（算导13.4节）。

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

在很多情况下，比如维护顺序统计树的 $s i z e$ 属性，一次旋转后更新的代价为 $O (1)$ ，而非定理14.1中给出的 $O(\log n)$ 。（算导练习14.2-3）还给出了这样的一个例子。

3. 区间树

在这一节，我们将扩张红黑树来支持「由区间构成的动态集合」上的一些操作。闭区间 closed interval 是一个实数的有序对 $[t_1, t_2]\ (t_1 \le t_2)$ 。区间 $t_1, t_2 ]$ 表示了集合 $\{ t \in \R \mid t_1 \le t \le t_2 \}$ 。开 open 区间和半开 half-open 区间分别略去了集合的两个或一个端点。本节中假设区间都是闭的，将结果推广至开和半开区间上是自然和直接的。

区间便于表示占用一连续时间段的一些事件。例如，查询一个由时间区间数据构成的数据库，去找出给定时间区间内发生了什么事件。本节中介绍的数据结构，可用来有效地维护这样一个区间数据库。

我们可以把一个区间 $t_1, t_2]$ 表示成一个对象 $i$ ，其中属性 $i.low = t_1$ 为低端点 low endpoint ，属性 $i.high = t_2$ 为高端点 high endpoint 。如果 $\cap i' \ne \varnothing$ ，即如果 $\le i'.high$ 且 $\le i.high$ ，我们称区间 $i, i^{'}$ 重叠 overlap 。如图14-3所示，任何两个区间 $i, i^{'}$ 满足区间三分律 interval trichotomy ，即下面三条性质之一成立：

$i, i^{'}$ 重叠；
$i$ 在 $i^{'}$ 的左边（也就是 $i . h i g h < i^{'} . l o w$ ）；
$i$ 在 $i^{'}$ 的右边（也就是 $i^{'} . h i g h < i . l o w$ ）。

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

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

图14-4说明了，区间树是如何表达一个区间集合的。我们按照（算导14.2节）四步法来分析区间树、以及区间树上各种操作的设计。
在这里插入图片描述

3.1 步骤一：基础数据结构

我们选择这样一棵红黑树，其每个结点 $x$ 包含一个区间属性 $x . i n t$ ，且 $x$ 的关键字为区间的低端点 $x . i n t . l o w$ 。因此，该数据结构按中序遍历列出的，就是按低端点的次序排列的各区间。

3.2 步骤二：附加信息

每个结点 $x$ 中除了自身区间信息之外，还包含一个值 $x . m a x$ ，它是以 $x$ 为根的子树中所有区间的端点的最大值。

3.3 步骤三：对信息的维护

我们必须验证， $n$ 个结点的区间树上的插入和删除操作，能否在 $O(\log n)$ 时间内完成。通过给定区间 $x . i n t$ 和结点 $x$ 的子结点的 $m a x$ 值，可以确定 $x . m a x$ 值： $\max(x.int.high,\ x.left.max,\ x.right.max)$
这样，根据定理14.1可知，插入和删除操作的运行时间为 $O(\log n)$ 。事实上，在一次旋转后，更新 $m a x$ 属性只需 $O (1)$ 时间（如算导练习14.2-3、14.3-1所示）。

3.4 步骤四：设计新的操作

这里我们仅需要唯一的一个新操作 INTERVAL-SEARCH(T, i) ，它是用来找出树 $T$ 中与区间 $i$ 重叠的那个结点。若树中与 $i$ 重叠的结点不存在，则下面过程返回指向哨兵 $T . n u l l$ 的指针。

INTERVAL-SEARCH(T, i)
	x = T.root
	while x != T.null and i does not overlap x.int
		if x.left != T.null and x.left.max >= i.low
			x = x.left
		else x = x.right
	return x

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

在说明 INTERVAL-SEARCH 的正确性之前，先来看一下这个过程在图14-4所示的区间树上是如何查找的。假设要找一个与区间 $i = [22, 25]$ 重叠的区间。

开始时 $x$ 为根结点，它包含区间 $[16, 21]$ ，与 $i$ 不重叠。由于 $x . l e f t . m a x = 23$ 大于 $i . l o w = 22$ ，所以这时以这棵树根的左孩子作为 $x$ 继续循环。
现在结点 $x$ 包含区间 $[8, 9]$ ，仍不与 $i$ 重叠。此时， $x . l e f t . m a x = 10$ 小于 $i . l o w = 22$ ，因此以 $x$ 的右孩子作为新的 $x$ 继续循环。
现在，由于结点 $x$ 包含的区间 $[15, 23]$ 与 $i$ 重叠，过程结束并返回这个结点。

现在来看一个查找不成功的例子。假设要在图14-4所示的区间树中找出与 $i = [11, 14]$ 重叠的区间。

再一次，开始时 $x$ 为根。因为根包含的区间 $[16, 21]$ 不与 $i$ 重叠，且 $x . l e f t . m a x = 23$ 大于 $i . l o w = 11$ ，则转向左边包含区间 $[8, 9]$ 的结点。
区间 $[8, 9]$ 仍不与 $i$ 重叠，且 $x . l e f t . m a x = 10$ 小于 $x . l o w = 11$ ，因此我们转向右子树（注意，其左子树中没有一个区间与 $i$ 重叠）。
这时区间 $[15, 23]$ 仍不与 $i$ 重叠，且它的左孩子为 $T . n u l l$ ，故向右转，循环结束，返回 $T . n u l l$ 。

要明白 INTERVAL-SEARCH 的正确性，我们必须理解为什么该过程只需检查一条由根开始的简单路径即可。该过程的基本思想是，在任意结点 $x$ 上，如果 $x . i n t$ 不与 $i$ 重叠，则查找总是沿着一个安全的方向进行：如果树中包含一个与 $i$ 重叠的区间，则该区间必定会被找到。下面的定理更精确地叙述了这个性质。

定理14.2 INTERVAL-SEARCH(T, i) 的任意一次执行，或者返回一个其区间与 $i$ 重叠的结点，或者返回 $T . n u l l$ ，此时树 $T$ 中没有任何结点的区间与 $i$ 重叠。
证明：当 $x = T . n u l l$ 或 $i$ 与 $x . i n t$ 重叠时，第 $\sim 5$ 行的 while 循环终止。后一种情况，过程返回 $x$ ，显然是正确的。因此，主要考虑前一种情况，也就是当 $x = T . n u l l$ 时 while 循环终止的情况。

对第 $\sim 5$ 行的 while 循环使用如下的循环不变式：如果树 $T$ 包含与 $i$ 重叠的区间，那么以 $x$ 为根的子树必包含此区间。循环不变式使用如下：

初始化：在第一次迭代之前，第 $1$ 行置 $x$ 为 $T$ 的根，循环不变式成立。
保持：在 while 循环的每次迭代中，第 $4$ 行或第 $5$ 行被执行。下面将证明，循环不变式在这两种情况下都能成立。
如果执行第 $5$ 行，则由于第 $3$ 行的分支条件，有 $x . l e f t = T . n u l l$ 或 $x . l e f t . m a x < i . l o w$ 。如果 $x . l e f t = T . n u l l$ ，则以 $x . l e f t$ 为根的子树显然不包含与 $i$ 重叠的区间，所以置 $x$ 为 $x . r i g h t$ 以保持这个不变式。因此，假设 $\ne T.null$ 且 $x . l e f t . m a x < i . o w$ 。如图14-5(a)所示，对 $x$ 左子树的任一区间 $i^{'}$ ，都有： $\le x.left.max < i.low$ 根据区间三分律， $i^{'}$ 和 $i$ 不重叠。因此， $x$ 的左子树不包含与 $i$ 重叠的任何区间，置 $x$ 为 $x . r i g h t$ 使循环不变式保持成立。

另外，如果是第 $4$ 行被执行，我们将证明循环不变式的对等情况。也就是说，如果在以 $x . l e f t$ 为根的子树中中没有与 $i$ 重叠的区间，则树的其他部分也不会包含与 $i$ 重叠的区间。因为第 $4$ 行被执行，是由于第 $3$ 行的分支条件导致的，所以有 $\ge i.low$ 。根据 $m a x$ 属性的定义，在 $x$ 的左子树中必定存在某区间 $i^{'}$ ，满足： $\ge i.low$

图14-5(b)显示了这种情况。因为 $i, i^{'}$ 不重叠，又因为 $i^{'} . h i g h < i . l o w$ 不成立，所以根据区间三分律有 $i . h i g h < i^{'} . l o w$ 。区间树是以区间的低端点为关键字的，所以搜索树性质隐含了对 $x$ 右子树中的任意区间 $i^{''}$ ，有： $\le i''.low$ 根据区间三分律， $i, i^{''}$ 不重叠。我们得出这样的结论，即不管 $x$ 的左子树中是否存在与 $i$ 重叠的区间，置 $x$ 为 $x . l e f t$ 保持循环不变式成立。
终止：如果循环在 $x = T . n u l l$ 时终止，则表明在以 $x$ 为根的子树中，没有与 $i$ 重叠的区间。循环不等式的对等情况，说明了 $T$ 中不包含与 $i$ 重叠的区间，故返回 $x = T . n u l l$ 是正确的。 $\blacksquare$