数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法学研究数据结构中的随机化手指搜索树
确定性搜索树的两种随机化替代方案是随机二叉搜索树、treap 和跳表。treap 和跳表都被定义为优雅的数据结构，其中随机化简化了简单而高效的更新操作。
在本节中，我们将解释 treap 和跳表如何都能够实现为高效的手指搜索树，而无需更改数据结构本身。两种数据结构都支持手指搜索，预期时间复杂度为 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) 的预期手指搜索时间。
更新于：2020年1月7日
浏览量 136
广告