Finger search tree とは

コンピュータ科学では、指探索木は、指と呼ばれる内部ノードへのポインタを保持する二分探索木の一種です。指は、指の近くの要素の検索、挿入、削除を高速化し、償却されたO(log n)ルックアップを与え、償却O(1)の挿入と削除を行います。フィンガーツリーやスプレイツリーと混同してはいけませんが、どちらもフィンガーサーチツリーの実装に使用できます。
Guibas et al。 Bツリー上に構築して、指探索木を導入しました。元のバージョンでは、O(ログd)時間内の指の検索がサポートされています.dは指と検索ターゲットの間の要素の数です。更新は、O(1)の可動指のみが維持されているときにO(1)時間かかる。指の位置を移動するにはO(log p)時間が必要です。 HuddlestonとMehlhornは、このアイデアをレベル結合されたBツリーとして洗練させました。
Tsakalidisは、木の端からの検索を容易にするAVLツリーに基づくバージョンを提案した。そのようなツリーの複数を使用することによって、複数の指でデータ構造を実装するために使用することができます。
バイナリツリーで指の検索を実行するには、xとyの回転ノードとも呼ばれる最も共通の祖先に到達するまで、指から始めてルートを上方向に検索してから下に移動するのが理想的です私たちが探している要素を見つけることができます。あるノードが別のノードの祖先であるかどうかを判断することは、自明ではありません。
Treidelは、SeidelとAragonによって提案されたランダム化されたツリー構造で、距離dの2つの要素の予想される経路長がO(log d)であるという性質を持っています。指探索のために、彼らは、最小共通祖先(LCA)を迅速に決定するためのポインタを追加するか、またはすべてのノードにおいてそのサブツリーの最小値および最大値を維持するためのポインタを追加することを提案した。
指の探索木を網羅した本の章が書かれています。 Brodalは、余計な簿記情報を必要とせずに、O(log d)時間内にtreapsの指探索を行うアルゴリズムを提案した。このアルゴリズムは、最後の候補LCAから下方に同時に探索することによってこれを達成する。