在虚拟树中，一些边被视为实线，一些被视为虚线。通常的伸展操作仅在实线树中执行。为了在虚拟树中的节点 y 上进行伸展操作，实现了以下方法。该算法查看树三次，每次遍历一次，并对其进行更改。在第一次遍历中，仅在实线树中进行伸展操作，从节点 y 开始，从 y 到整个树根的路径变为虚线。此路径通过拼接变为实线。现在，在节点 y 上进行最终的伸展操作将使 y 成为树的根。… 阅读更多

对于给定的森林，我们创建一些给定的边为“虚线”，其余边保持为实线。每个非叶节点仅与一条到其子节点的“实线”边相关联。所有其他子节点将通过虚线边连接。更具体地说，在任何给定的树中，最右边的链接（到其子节点）应保持为实线，而所有其他到其其他子节点的链接都创建为“虚线”。结果，树将被分解成一系列实线路径。实线路径的根将连接到其他… 阅读更多

静态手指定理 - 假设 f 被视为称为手指的特定元素。然后，以下表达式是伸展序列成本的上限 O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j注意 - |f-i| 表示项目在项目 i 和手指之间的对称排序中的距离。其中 m 表示对最多包含 n 个节点的树进行更新或访问操作的次数。观察到，至少在摊销意义上，在从未超过 n 的树上进行前 m 次操作所需的时间… 阅读更多

动态最优性猜想除了伸展树的已证明性能保证之外，还有一个未经证实的猜想引起了极大的兴趣。动态最优性猜想表示此猜想。设任何二叉搜索树算法（如 B）通过遍历从根到 y 的路径来访问元素 y，其成本为 d(y)+1，并且在访问之间可以在树中进行任何旋转，每次旋转的成本为 1。设 B(s) 为 B 执行访问序列 s 的成本。那么伸展树执行相同访问的成本为 O[n+B(s)]。有… 阅读更多

自适应合并排序自适应合并排序执行合并排序所执行的有序子列表的合并。但是，初始子列表的大小取决于元素列表中是否存在排序，而不是具有大小为 1 的子列表。例如，考虑图中的列表。它包含 2 个有序子列表。子列表 1 包含元素 16、15、14、13。子列表 2 包含元素 9、10、11、12。子列表 1 是有序的，但顺序相反。因此，子列表 1 反转，如图所示。一旦找到子列表，合并过程就开始了。自适应合并排序开始合并子列表。自适应合并… 阅读更多

在跳表中，可以从包含元素 b 的节点开始对元素 a 进行手指搜索，只需从此处继续搜索 a 即可。请注意，如果 a < b，则搜索向后进行，如果 a > b，则搜索向前进行。向后情况与跳表中的正常搜索对称，但向前情况实际上更复杂。通常，跳表中的搜索预计会很快，因为列表开头的哨兵被视为最高的节点。但是，我们的手指可能与… 阅读更多

确定性搜索树的两种随机化替代方案是随机二叉搜索树、treap 和跳表。treap 和跳表都被定义为优雅的数据结构，其中随机化有助于简单高效地进行更新操作。在本节中，我们将解释 treap 和跳表如何都可以在不更改数据结构的情况下实现为高效的手指搜索树。这两种数据结构都支持手指搜索，消耗预期 O(log d) 时间，其中期望值取自算法在构建数据结构期间创建的随机选择。跳表在跳表中，可以… 阅读更多

在本节中，我们将解释 (2, 4) 树如何通过引入层级链接来支持高效的手指搜索。本节中解释的想法也适用于更通用的高度平衡树类，表示为 (a, b) 树，其中 b ≥ 2a。(2, 4) 树被定义为高度平衡的搜索树，其中所有叶子都具有相同的深度，并且所有内部节点都具有二、三或四个度。元素存储在叶子中，内部节点仅存储搜索键以指导搜索。由于每个内部节点的度至少为二，因此可以得出 (2, 4) 树… 阅读更多

除了手指搜索之外，动态手指搜索数据结构还应该执行在由手指给出的位置插入和删除元素的操作。手指搜索树被定义为支持手指搜索的 B 树的变体，时间为 O(log d)，更新时间为 O(1)，假设仅维护 O(1) 个可移动手指。遍历手指 d 个位置需要 O(log d) 时间。手指搜索树（即 AVL 树、红黑树）的构造要么考虑固定数量的手指，要么仅支持摊销常数时间内的更新。支持任意数量的手指并在最坏情况下更新的构造… 阅读更多

数据结构上的手指搜索被定义为结构支持的任何搜索操作的扩展，其中给出了对数据结构中元素的引用（手指）以及查询。虽然元素的搜索时间最常表示为数据结构中元素数量的函数，但手指搜索时间被视为元素与手指之间距离的函数。在一组 m 个元素中，两个元素 a 和 b 之间的距离 d(a, b) 是它们在秩中的差值。如果元素 a 和… 阅读更多