フィンガーサーチツリー

コンピュータサイエンスにおいて、フィンガー探索木は、フィンガーと呼ばれる内部ノードへのポインターを保持するバイナリ探索木の一種です。フィンガーは、フィンガーに近い要素の検索、挿入、削除を高速化し、償却O (log n) の検索と償却 O(1) の挿入と削除を実現します。フィンガーツリーやスプレイツリーはどちらもフィンガー探索木を実装するために使用できますが、これらと混同しないでください。

Guibas ら^{[1] は、}B ツリーを基盤としてフィンガー検索ツリーを導入しました。元のバージョンでは、フィンガー検索を O(log d) 時間で実行できます。ここで、d はフィンガーと検索対象の間にある要素の数です。O(1) 個の可動フィンガーのみが維持される場合、更新には O(1) 時間がかかります。フィンガーを p 位置に移動するには、O(log p) の時間がかかります。Huddleston と Mehlhorn はこのアイデアをレベルリンク B ツリーとして改良しました。^[2]

Tsakalidisは、AVLツリーをベースにした、ツリーの端からの検索を容易にするバージョンを提案した。このバージョンでは、複数のツリーを使用することで、複数のフィンガーを持つデータ構造を実装することができる。^[3]

二分木でフィンガー検索を実行する理想的な方法は、フィンガーから始めてルートに向かって上向きに検索し、xとyの最小共通祖先[4] [5]（ターニングノード[3]とも呼ばれる）に到達してから、下向き^に^検索し^て目的の要素を見つけることです。ノードが別のノードの祖先であるかどうかを判断するのは簡単ではありません。

^{SeidelとAragon [5]}が提案したランダムツリー構造であるTreapsは、距離dの2つの要素の期待パス長がO(log d )であるという特性を持っています。フィンガーサーチでは、最小共通祖先(LCA)を素早く決定するためにポインタを追加するか、各ノードでサブツリーの最小値と最大値を維持することを提案しました。

フィンガーサーチツリーを詳細にカバーした章が執筆されています。^[4]その中で、Brodalは、追加の記録情報を必要とせずに、O(log d)時間でツリーのフィンガーサーチを実行するアルゴリズムを提案しました。このアルゴリズムは、最後の候補LCAから下方向に同時に検索することでこれを実現します。

参照

参考文献

^ Guibas, LJ ( 1977). 「線形リストの新しい表現」。第 9 回 ACM コンピューティング理論シンポジウム議事録 - STOC '77。pp. 49–60。CiteSeerX 10.1.1.527.7294。doi : 10.1145 /800105.803395。S2CID 2414154。
^ Huddleston; Mehlhorn, Kurt (1982). 「ソートされたリストを表現するための新しいデータ構造」. Acta Informatica . 17 (2): 157–184. doi :10.1007/BF00288968. S2CID 10397918.
^ ab Tsakalidis, Athanasios K. (1985). 「局所的検索のためのAVLツリー」.情報と制御. 67 (1–3): 173–194. doi : 10.1016/S0019-9958(85)80034-6 .
^ ab Brodal, Gerth Stølting (2005). 「11. フィンガーサーチ」(PDF)。Mehta, Dinesh P.、Sahni , Sartaj (編)。データ構造とアプリケーションのハンドブック。Chapman & Hall / CRC Press。ISBN 978-1584884354. 2013年1月1日閲覧。
^ ab Seidel, R. ; Aragon, CR (1996). 「ランダム化検索ツリー」. Algorithmica . 16 (4–5): 464–497. CiteSeerX 10.1.1.122.6185 . doi :10.1007/BF01940876. S2CID 9370259.

[1] ^ Guibas, LJ ( 1977). 「線形リストの新しい表現」。第 9 回 ACM コンピューティング理論シンポジウム議事録 - STOC '77。pp. 49–60。CiteSeerX 10.1.1.527.7294。doi : 10.1145 /800105.803395。S2CID 2414154。

[2] Huddleston; Mehlhorn, Kurt (1982). 「ソートされたリストを表現するための新しいデータ構造」. Acta Informatica . 17 (2): 157–184. doi :10.1007/BF00288968. S2CID 10397918.

[tsakalidis-3] Tsakalidis, Athanasios K. (1985). 「局所的検索のためのAVLツリー」.情報と制御. 67 (1–3): 173–194. doi : 10.1016/S0019-9958(85)80034-6 .

[brodal-4] Brodal, Gerth Stølting (2005). 「11. フィンガーサーチ」(PDF)。Mehta, Dinesh P.、Sahni , Sartaj (編)。データ構造とアプリケーションのハンドブック。Chapman & Hall / CRC Press。ISBN 978-1584884354. 2013年1月1日閲覧。

[treap-5] Seidel, R. ; Aragon, CR (1996). 「ランダム化検索ツリー」. Algorithmica . 16 (4–5): 464–497. CiteSeerX 10.1.1.122.6185 . doi :10.1007/BF01940876. S2CID 9370259.