在虚拟树中，一些边被视为实线，一些被视为虚线。通常的伸展操作只在实线树中执行。为了在虚拟树中的节点 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) 树具有…… 阅读更多

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

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