数据结构中的随机手指搜索树
确定性搜索树的两个随机替代方案是随机二进制搜索树，挖掘和跳过列表。挖掘列表和跳过列表都被定义为优雅的数据结构，其中随机化有助于简单而有效的更新操作。
在本节中，我们将说明如何在不更改数据结构的情况下将挖掘列表和跳过列表都实现为有效的手指搜索树。两种数据结构都通过消耗期望的O（logd）时间来支持手指搜索，在这种期望中，期望值是在数据结构构建过程中对算法创建的随机选择的一种接管。
跳过列表
在跳过列表中，只需从这一点继续进行搜索，即可从包含元素b的节点中手指搜索元素a。注意，如果a<b，则搜索沿反向进行；如果a>b，则搜索沿向前进行。向后的情况与跳过列表中的常规搜索对称，但向前的情况实际上更复杂。通常，由于列表开头的哨兵被认为是最高的节点，因此在跳过列表中的搜索预计会很快。但是，我们的手指可能与一个高度为1的节点相关联。因此，我们在尝试搜索时可能很少攀爬；通常不会发生的事情。但是，即使有这种复杂性，我们也可以达到O（logd）期望的搜索时间。
挖土机
挖矿被定义为随机二叉树(BST)。搜索陷阱类似于在任何其他BST中搜索元素。但是，挖掘具有以下性质：两个距离元素之间的预期路径长度表示为O（logd）。因此，为了从包含元素b的节点中搜索元素a进行手指搜索，可以从b元素爬到树上，直到找到元素a的祖先为止，此时正常的BST搜索将以常规方式进行。在计算一个节点是否是另一个节点的祖先时，一个节点可能会扩充以支持这种形式的查询，以提供预期的O（logd）手指搜索时间。