静态手指定理 - 假设 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，因此可以得出 (2, 4) 树具有... 阅读更多

动态手指搜索数据结构除了手指搜索外，还应执行由手指给定位置的元素插入和删除。手指搜索树被定义为 B 树的一种变体，它支持在 O(log d) 时间内进行手指搜索，并在 O(1) 时间内进行更新，假设仅维护 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 树是一棵二叉树... 阅读更多