数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究数据结构中的手指搜索
数据结构上的手指搜索被定义为该结构支持的任何搜索操作的扩展，其中给定数据结构中一个元素的引用（手指）以及查询。虽然元素的搜索时间最常表示为数据结构中元素数量的函数，但手指搜索时间被视为元素与手指之间距离的函数。
在一组 m 个元素中，两个元素 a 和 b 之间的距离 d(a, b) 是它们的排名差。如果元素 a 和 b 分别是结构中第 i 大和第 j 大的元素，则排名差为 |i - j|。如果某些结构中的普通搜索通常需要 O(f(m)) 时间，则使用手指元素 b 进行元素 a 的手指搜索理想情况下应消耗 O(f(d)) 时间。请注意，由于 d ≤ m，因此在最坏情况下，手指搜索仅与普通搜索一样糟糕。但是，在实践中，这些退化的手指搜索比普通搜索执行更多的工作。例如，如果 f(n) 是 log(n)，并且手指搜索在最坏情况下执行的比较次数是普通搜索的两倍，则在 d > √n 时，手指搜索会更慢。因此，只有当可以合理地预期目标实际上靠近手指时，才应实现手指搜索。
实现
一些流行的数据结构支持手指搜索，而无需对实际结构进行任何额外更改。在通过缩小可以找到 a 的区间来执行元素 a 搜索的结构中，通常通过从 b 反转搜索过程来执行来自元素 b 的手指搜索，直到搜索区间足够大以包含元素 a，然后正常进行搜索。
排序链表
在链表中，通常以线性方式通过从一端遍历到另一端来搜索元素。如果链表已排序，并且我们有一个指向包含元素 b 的某些节点的引用，则可以通过从元素 b 开始搜索，在 O(d) 时间内找到元素 a。
排序数组
在排序数组 B 中，通常使用二分查找在 B 中搜索元素 a。手指搜索通过从 B[j] = b 执行单边搜索来执行。虽然二分查找在每次比较后将搜索空间减半，但单边搜索在每次比较后将搜索空间加倍。具体来说，在单边搜索的第 k 次迭代（假设 a>b）中，正在考虑的区间是 B[j, j+2k-1]。当 B[j + 2k-1] ≥ a 时，扩展停止，此时对该区间进行二分查找以查找元素 a。如果单边搜索消耗 k 次迭代来找到包含元素 a 的区间，则 d > 2k-2。对该范围进行二分查找也将消耗另外 k 次迭代。因此，从 b 对 a 进行手指搜索消耗 O(k) = O(log d) 时间
.
跳表
在跳表中，可以通过简单地从该点继续搜索，从包含元素 b 的节点对元素 a 进行手指搜索。请注意，如果 a < b，则搜索向后进行，如果 a > b，则搜索向前进行。向后案例与跳表中的普通搜索对称，但向前案例实际上更复杂。通常，跳表中的搜索预计会很快，因为列表开头的哨兵被认为是最高的节点。但是，我们的手指可能是一个高度为 1 的节点。因此，在尝试搜索时，我们可能很少攀升；这在正常情况下永远不会发生。但是，即使存在这种复杂情况，我们也可以实现 O(log d) 的预期搜索时间。
Treap
Treap 被定义为随机二叉搜索树 (BST)。在 Treap 中搜索类似于在任何其他 BST 中搜索元素。但是，Treap 具有以下属性：距离为 d 的两个元素之间的预期路径长度表示为 O(log d)。因此，要从包含元素 b 的节点对元素 a 进行手指搜索，可以从 b 元素向上遍历树，直到找到元素 a 的祖先，然后像往常一样进行正常的 BST 搜索。虽然计算节点是否是另一个节点的祖先并非易事，但可以增强树以支持此类查询，以提供预期的 O(log d) 手指搜索时间。
绳子和树
绳子（数据结构）的实现通常使用绳子位置迭代器来访问字符串。迭代器可以被认为是指向字符串某个特定字符的手指。与大多数平衡树一样，绳子需要 O(log(m)) 时间才能在给定树的根的情况下检索树中一个叶子中的数据。读取树的每个叶子似乎需要 O(m*log(m)) 时间。但是，通过存储一些额外的信息，可以实现迭代器以仅在 O(1) 时间内读取“下一个”叶子，并在仅 O(m) 时间内读取树的每个叶子。
333 次浏览
