データ構造におけるランダム化フィンガー検索ツリー：スキップリストとトレップの活用法

決定論的な探索木に対するランダム化された代替手法として、「トレップ（treap）」と「スキップリスト（skip list）」という2つのランダム化二分探索木が広く知られています。どちらもエレガントなデータ構造として定義されており、ランダム化の導入によってシンプルかつ効率的な更新操作が可能になっています。

本記事では、これらのデータ構造そのものを変更することなく、トレップとスキップリストを効率的なフィンガー検索木として実装する方法について解説します。両データ構造とも、期待計算量 O(log d) の時間でフィンガー検索をサポートします。ここでいう期待値は、データ構造の構築過程においてアルゴリズムが行うランダムな選択に基づいて算出されるものです。

スキップリストにおけるフィンガー検索

スキップリストでは、要素 b を格納するノードから要素 a のフィンガー検索を行う際、その地点から探索を続行するだけで実現できます。a < b の場合は後方方向へ、a > b の場合は前方方向へと探索が進みます。

後方への探索は、通常のスキップリスト探索と対称的な処理となります。一方、前方への探索は実際にはより複雑です。通常、スキップリストの探索が高速に動作するのは、リスト先頭のセンチネル（番兵）ノードが最も高いノードとして扱われているためです。しかし、フィンガー（探索開始点）が高さ1のノードに関連付けられているケースもあり得ます。この場合、通常の探索では発生しない「上位レベルへの移動」が必要になることがあります。

とはいえ、このような複雑さがあるにもかかわらず、期待 O(log d) の探索時間を達成できることが示されています。

トレップにおけるフィンガー検索

トレップは、ランダム化二分探索木（BST）として定義されるデータ構造です。トレップ内の探索は、一般的な二分探索木における要素探索と同様の手順で行えます。ただし、トレップには特筆すべき性質があり、距離 d だけ離れた2つの要素間の期待経路長が O(log d) で表されます。

この性質を利用すると、要素 b を格納するノードから要素 a へのフィンガー検索は次のように実現できます。まず b の位置から木を上方向に辿り、要素 a の祖先となるノードを探します。祖先が見つかった時点で、以降は通常の二分探索木と同じ要領で探索を続行します。

あるノードが別のノードの祖先であるかどうかの判定は自明ではないため、この種のクエリをサポートするよう木を拡張（オーグメント）することで、期待 O(log d) のフィンガー検索時間を実現できます。