データ構造内のランダム化されたフィンガー検索ツリー

決定論的探索木の2つのランダム化された代替案は、ランダム化された二分探索木、treaps、およびスキップリストです。 treapとスキップリストはどちらも洗練されたデータ構造として定義されており、ランダム化によってシンプルで効率的な更新操作が容易になります。

このセクションでは、データ構造を変更せずに、treapとスキップリストの両方を効率的なフィンガーサーチツリーとして実装する方法について説明します。どちらのデータ構造も、予想されるO（log d）時間を消費することでフィンガー検索をサポートします。この場合、データ構造の構築中にアルゴリズムによって作成されたランダムな選択に対して予想が引き継がれます。

スキップリスト

スキップリストでは、このポイントから検索を続行するだけで、要素bを含むノードから要素aを指で検索できます。 a bの場合、検索は順方向に進むことに注意してください。後方の場合はスキップリストでの通常の検索と対称的ですが、前方の場合は実際にはもっと複雑です。通常、スキップリストでの検索は、リストの先頭にある番兵が最も高いノードと見なされるため、高速であると予想されます。ただし、指を高さ1のノードに関連付けることができます。このため、検索中に登ることはめったにありません。通常は発生しない何か。ただし、この複雑さがあっても、O（log d）の予想検索時間を達成することができます。

Treaps

Treapは、ランダム化された二分探索木（BST）として定義されます。 Treapでの検索は、他のBSTでの要素の検索と似ています。ただし、Treapには、distanceの2つの要素間の予想パス長がO（log d）として示されるという特性があります。したがって、要素bを含むノードから要素aを指で検索するには、要素aの祖先が見つかるまで、b要素からツリーに登ることができます。その時点で、通常のBST検索が通常どおりに進行します。ノードが別のノードの祖先であるかどうかを計算するのは簡単ではありませんが、このフォームのクエリをサポートするようにツリーを拡張して、予想されるO（log d）フィンガー検索時間を提供することができます。