静态手指定理 - 假设 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) 树具有... 阅读更多

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

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

多路树被定义为可以有多个子节点的树。如果多路树最多可以有 m 个子节点，则此树称为 m 阶多路树（或 m 路树）。与已研究的其他树一样，m 路树中的节点将由 m-1 个键字段和指向子节点的指针组成。5 阶多路树为了使 m 路树的处理更容易，将在每个节点内的键上施加某种约束或顺序，从而产生 m 阶多路搜索树... 阅读更多

基本概念多维二叉搜索树（简称k-d树）被定义为一种用于存储多键记录的数据结构。这种结构已被用于解决统计和数据分析中的一些“几何”问题。k-d树（k维树的简称）被定义为一种用于组织k维空间中点的空间划分数据结构。数据结构k-d树被应用于多种应用，例如涉及多维搜索键的搜索（例如范围搜索和最近邻搜索）。k-d树被视为二叉空间划分树的特例。非正式描述k-d树是一种二叉树... 阅读更多