数据结构2

计算机科学 > 数据结构
3 24~32 分钟

第一部分：指针搜索树 (Finger Search Trees)

首先，我们来谈谈指针搜索树。

1. 指针搜索树的动机与基础

我们先从一个熟悉的场景开始：二分查找 (Binary Search)。对于一个大小为 N 的有序列表，二分查找在最坏情况下的比较次数是 log N，这无疑是高效的 ``。然而，如果遇到一些特殊情况，例如：

  • 我们搜索的目标 X 可能更靠近列表的左侧 ``。

  • 或者，我们面对的列表是无界的，或者大小未知 ``。

  • 再或者，我们已经有一个“参照点”或“指针”，希望搜索效率能随着目标与该参照点的距离而提高。

在这些场景下，标准的二分查找可能不是最优解。

为了解决这个问题，我们可以考虑一种被称为“倍增搜索 (Doubling Search)”的技术 。其思想是：从一个起点开始，我们以指数级的步长（例如，1, 2, 4, 8, ..., 2^k）探测，直到我们“越过”目标值 X。一旦我们确定了 X 位于 [2^(k-1), 2^k] 这个区间内，我们就可以在这个已知大小的区间内进行标准的二分查找 。如果目标 X 与起点之间的距离是 d，那么这种方法所需的总比较次数大约是 2 * log2 d。这比在整个大小为 N 的列表中进行 log N 次比较要好，特别是当 d 远小于 N 时。

我们可以将这种倍增搜索的概念扩展到树结构中。将倍增搜索视为一个二叉搜索树（BST），它的右侧主干由大小呈指数增长的完整子树构成 ``。这种思想为我们引出了指针搜索树。

2. 指针搜索树的核心思想与结构

指针搜索树 (Finger Search Tree) 的核心思想是：给定一个“指针” X（它是树中的一个节点），我们搜索另一个元素 Y 的效率应该与 X 和 Y 之间的“距离”d 相关 。这里的 d 指的是在树中位于键值区间 [X, Y] 之间的元素数量。我们的目标是使搜索操作的成本达到 O(log d) ``，这比传统的 O(log n)（n 是树中所有元素的数量）更具有适应性，尤其当 d 远小于 n 时。

为了实现这种自适应的性能，指针搜索树通常采用以下通用方法：

  • 层级链接 (Level Links)： 在树的每个层级上，节点之间会构建双向链表 ``。这使得我们可以在同一层级上高效地移动。

  • 额外指针： 每个节点通常会额外存储两个指针 ，这有助于在树中进行高效导航，例如检测两个节点之间的最低公共祖先 (LCA)。

3. 指针搜索树的基本操作

通过上述的结构增强，指针搜索树能够支持高效的基本操作：

  • 搜索 (Search)、插入 (Insert) 和 删除 (Delete)： 这些操作的成本通常为 O(log d)，其中 d 是被操作的元素与“指针”之间的距离 。更精确地说，是 O(log(1+d))。

  • 分裂 (Split) 和 合并 (Join)： FSTs 也支持将一个树分裂成两部分（例如小于 X 和大于 X 的部分），或者将两个树合并。这些操作的成本通常为 O(log n) ``。

4. 指针搜索树的应用

指针搜索树因其自适应的性能，在多个领域都有着重要的应用：

  • a. 自适应堆 (An Adaptive Heap) ``

    • 传统的堆操作（如 insert 和 extract-min）通常是 O(log N)。但如果需要对靠近最小值或最大值的元素进行频繁操作，FST可以提供更优的性能。

    • 插入 (Insert(x))： 将元素 x 插入堆中。如果堆的“指针”始终指向最小值，那么插入一个新元素的成本是 O(log d)，其中 d 是 x 的秩，即堆中比 x 小的元素数量 。这意味着，当插入的元素非常接近最小值时，插入操作会非常高效。

    • 提取最小值 (Extract-min)： 这个操作只需要 O(1) 的时间，因为“指针”直接指向最小值，且可以高效地找到其后继 ``。

  • b. 合并两个有序列表 (Merging two sorted lists) ``

    • 假设我们有两个有序列表，大小分别为 m 和 n。标准的“磁带合并”算法需要 O(m+n) 次比较 ``。

    • 如果我们将其中一个列表 X 存储为指针搜索树，然后将另一个列表 Y 中的元素 y_i 逐个插入到 X 中 。关键在于，我们可以利用指针搜索，将 y_i 从 y_{i-1} 的位置开始搜索并插入。

    • 这种方法使得总的合并成本从朴素的 O(m log n) 优化到了 O(m log(n/m)) 。这在理论上被证明是合并两个有序列表所需的最低比较次数。

  • c. 可分裂列表的集合 (Collection of splittable lists) ``

    • 这个应用展示了FST在动态列表操作中的强大能力。我们维护一个有序列表的集合，初始时只有一个大小为 n 的完整列表 ``。

    • 操作：分裂 (Split(L, X))，即将列表 L 根据元素 X 分裂成两部分：小于等于 X 的部分和大于 X 的部分 。我们的目标是最终将所有列表都分裂成单个元素的列表。

    • 一个简单的分析会认为，进行 n-1 次分裂，每次花费 O(log n)，总成本是 O(n log n) ``。

    • 然而，通过摊还分析 (Amortized Analysis)，我们可以证明更优的性能 。我们定义一个势函数 Phi = n - log2 n。通过计算势能的变化，可以得出结论：单次分裂的摊还成本为 O(1) 。因此，执行 n-1 次分裂的总摊还成本是*O(n)**。这是指针搜索树能够实现的重要效率提升。

5. 指针搜索树的实现

指针搜索树通常不是从零开始构建，而是通过增强 (augmenting) 现有的平衡搜索树结构来实现 。虽然AVL树或红黑树可以用于此目的，但笔记中特别提到了 **(a,b)-树**，也称为 **B树 (B-tree)**。B树在数据库和文件系统中非常常用 ``。

(a,b)-树 的特点： ``

  • 键（实际数据）通常只存储在叶子节点中 ``。

  • 所有叶子节点都位于相同的深度 ``。

  • 键值是从左到右排序的 ``。

  • 内部节点用于导航和指导搜索路径 ``。

  • 内部节点的度数 (degree) 介于 a 和 b 之间 ，其中 a 和 b 是预定义的整数参数（例如 (2,4)-树，意味着度数在2到4之间）。

在 (a,b)-树 中的基本操作：

  • 搜索 (Search)： 成本是 O(log n) ``。

  • 插入 (Insert)： 插入新叶子后，如果父节点的度数超过 b，需要进行分裂 (split) 操作 。分裂可能会向上层传播，甚至导致根节点分裂。但通过摊还分析，单次插入的摊还成本是 O(log n)，其中分裂的摊还次数是 O(1) ``。

  • 删除 (Delete)： 删除叶子后，如果父节点的度数低于 a，可能需要借用 (borrow) 兄弟节点的子节点，或者与兄弟节点合并 (merge) 。合并操作也可能向上层传播。同样，通过摊还分析，单次删除的摊还成本也是 O(log n)，其中合并的摊还次数是 O(1) ``。

为了实现指针搜索树，我们通常会扩展 (2,4)-树，为同一层级的节点添加双向链表，这就是所谓的“层级链接” ``。

  • FST 中的指针搜索 (Finger Search)： 假设我们从节点 x 开始，搜索 y。算法会首先从 x 向上遍历，直到找到一个包含 y 或其相关范围的子树，然后向下搜索 。这种搜索的成本正是 O(log d)，其中 d 是 x 和 y 之间的元素数量。

  • FST 中的分裂 (Split/Fork) 和 合并 (Join)：

    • 单点分裂 (Split(T,X))： 将树 T 分裂成两棵树 T_{<=X} 和 T_{>X}。这需要沿着从根到 X 的路径向上遍历，并在路径上的内部节点处进行分裂 。成本为 O(log n)。

    • 合并 (Join(T1,T2))： 将两棵树 T1 和 T2 合并成一棵。假设 T1 中的键都小于 T2 中的键，操作涉及将一棵树的右路径连接到另一棵树的根或左路径上 。成本为 O(log n)。

    • 两点分裂 (2-pivot Split(T,X,Y))： 这是一个更高级的分裂操作，可以将树 T 分裂成三部分：[X,Y] 内部的部分和 [X,Y] 外部的两个部分 。其成本是 O(log min{d, n-d})，其中 d 是 X 和 Y 之间的元素数量n-d 是外部的元素数量。这个操作比单点分裂更强大，因为它能一次性提取出中间的子区间。

第二部分：乔丹序列 (Jordan Sequences)

接下来，我们转向乔丹序列。这个概念在计算几何中有着重要的应用，并且其处理算法巧妙地利用了我们刚才学习的指针搜索树。

1. 乔丹序列的定义与问题

想象一条乔丹曲线 (Jordan curve) 与一条水平线 (horizontal line) 相交 。这条曲线可能有自交点。我们沿着水平线从左到右给所有的交点编号。然后，我们沿着乔丹曲线本身，从起点（假设在水平线下方）开始，依次读出它遇到的交点编号，从而得到一个序列 。这个序列就是所谓的**乔丹序列 (Jordan Sequence)**。

核心问题是：给定一个这样的序列 X_1, X_2, ..., X_n，我们如何验证它是否是一个有效的乔丹序列，并对它进行排序 ？更令人惊讶的是，我们希望在 *O(n) 的时间复杂度**内完成这个任务。这对于一般的排序问题来说是不可思议的，因为传统的比较排序下界是 Omega(n log n)。这表明，乔丹序列具有某种特殊的结构，使得我们可以避开一般的比较排序限制。

笔记还提到一个有趣的结论：n 个交点的乔丹序列的数量小于 5^n ``。

2. 乔丹序列的应用

乔丹序列在计算机图形学 (Computer Graphics) 中有实际应用 ``：

  • 例如，它可以用于查找多边形与其边界线的交点 ``。

  • 或者，确定一个多边形在给定窗口内的可见部分 ，这可以通过沿着多边形边缘找到与窗口边界的交点并进行乔丹排序来完成。

3. 乔丹序列的算法

解决乔丹序列问题的算法非常巧妙，它的核心思想是利用两棵树来表示乔丹序列的结构 ：一棵**上树 (Upper Tree)** 和一棵**下树 (Lower Tree)**。

  • “凹凸” (Bumps)： 乔丹序列中的每对相邻交点 (X_{2i-1}, X_{2i}) 可以看作是一个“凹凸” 。这些“凹凸”有特殊的性质，它们**不能相互交叉**。

算法步骤概述 ``：

  1. 输入： 乔丹曲线与水平线的交点序列 X_1, X_2, ..., X_n ``。

  2. 构建： 算法的目标是逐步构建上树、下树，并维护一个沿水平线排序的交点列表 。如果在构建过程中发现任何结构性冲突，则该序列不是一个有效的乔丹序列。

  3. 初始化：

    • 创建上树和下树的根节点，通常表示为 {-∞, +∞} ``。

    • 创建一个排序列表，最初包含 (-∞, X_1, +∞) ``。

  4. 处理 X_i： 算法会迭代处理序列中的每个交点 X_i ``。

    • 如果 i 是偶数，则将新的“凹凸” {X_{i-1}, X_i} 添加到上树中 ``。

    • 如果 i 是奇数，则将 {X_{i-1}, X_i} 添加到下树中 ``。

    • 核心处理逻辑： 对于每个 X_i，算法需要执行以下关键操作 ``：

      • 在当前维护的排序列表中，找到 X_{i-1} 的右侧邻居 X ``。

      • 找到上树中包含 X 的父凹凸 {L, R} ``。

  5. 五种情况 (Five Cases) ``： 算法根据 X_{i-1}、X_i 以及当前父凹凸 {L, R} 的相对位置，分为五种主要情况（Case A 到 Case E），每种情况对应不同的处理方式：

    • A型和D型： 这些情况表示当前的 X_i 无法正确地融入现有结构，因此序列不是一个有效的乔丹序列，算法停止 ``。

    • B型、C型和E型： 这些是合法的乔丹序列进展情况。算法会根据具体情况，对上树或下树进行结构调整，例如：

      • 将新凹凸 {X_{i-1}, X_i} 设置为 {L, R} 的右侧或左侧兄弟 ``。

      • 或者，在更复杂的情况下（E型），可能需要移除 {L,R} 的某些子树，并用新的节点替换 ``。

      • 同时，在每一步中，X_i 也会被插入到排序列表中 ``。

4. 数据结构与运行时间

为了实现上述算法，高效的数据结构是必不可少的：

  • 排序列表： 用于维护沿水平线排序的交点。它通常实现为双向链表，支持在给定元素之后 O(1) 时间内插入新元素 ``。

  • 兄弟列表 (Lists of Siblings)： 在上树和下树中，每个父节点下的子凹凸（兄弟节点）列表是动态变化的。这些兄弟列表正是通过我们之前讲解的指针搜索树 (Finger Search Trees) 来实现的 ``！

    • 指针搜索树在这里的应用非常关键，因为它能够高效地支持兄弟列表上的插入 (insert)、指针搜索 (finger search) 以及特别是两点分裂 (2-pivot split) 操作 。两点分裂操作使得算法能够高效地移除子树。

整体运行时间： ``

  • 将新凹凸插入为右侧或左侧兄弟的成本是 O(1) ``。

  • 涉及两点分裂的操作成本为 O(log min{d, t-d})，其中 t 是列表长度，d 是分裂点 ``。

  • 最关键的： 整个乔丹排序算法的总摊还时间复杂度为 O(n) 。这是通过重用我们之前在“可分裂列表集合”应用中讨论的摊还分析得出的。简而言之，每次处理一个 X_i 的摊还成本是 O(1) ``，因此处理 n 个交点的总成本就是线性的 O(n)。

推荐文章

高级数据结构课程讲义 4