データ構造における動的フィンガー探索木とは？基本概念と代表的な構成を解説

動的フィンガー探索木とは

フィンガー探索とは、あらかじめ保持しておいた位置（フィンガー）から目的の要素までの距離 d を基準に探索を行う手法です。先頭や根から探索を開始する通常の方法と比べ、d が小さい場合に大幅な高速化が期待でき、ソート済みリストのマージや計算幾何アルゴリズムなど、近接した位置への連続アクセスが発生する場面で特に威力を発揮します。

動的なフィンガー探索データ構造には、このフィンガー探索に加えて、フィンガーで示された位置への要素の挿入・削除も効率的に行えることが求められます。

フィンガー探索木の基本性質

フィンガー探索木はB木の変種として定義され、移動可能なフィンガーを定数個だけ維持するという前提のもとで、O(log d) 時間のフィンガー探索と O(1) 時間の更新（挿入・削除）を実現できます。

フィンガーを d 位置分たどる操作には O(log d) 時間しかかかりません。つまり、探索対象が前回アクセスした位置の近くにあるほど高速に処理できる点が最大の特長です。

代表的な構成方式とその特性

AVL木・赤黒木を用いた構成

AVL木や赤黒木といった平衡二分探索木を用いた従来の構成では、扱えるフィンガーの本数が固定の定数個に限られるか、あるいは更新が償却定数時間でしか行えないという制約がありました。

その後、任意の本数のフィンガーを扱え、かつ最悪計算時間でも更新可能な構成が考案されています。一方で、任意の位置への更新を最悪 O(1) 時間で実行できるものの、探索は O(log n) 時間に限られる探索木の研究も存在します。

さらに、O(log d) 時間の探索に加え、挿入・削除を O(log d n) 時間で実行できる構成や、最悪の場合でも挿入は定数時間・削除は O(log d n) 時間で処理できるフィンガー探索木も提案されています。

レベルリンク型(2,4)木に対する省メモリな代替案

レベルリンク付き (2,4) 木の代替として、空間的に効率の良い構成も知られています。この方式では単一のフィンガーのみを許容しながら、(2,4) 木と同等の性能を維持できます。

特長は、レベルリンクや親ポインタを一切必要としない点です。代わりに、手（hand）と呼ばれる O(log n) 空間の特殊なデータ構造をフィンガー専用に作成することで、フィンガーを効率的に移動できるようにしています。

スプレー木によるアプローチ

スプレー木は自己調整二分探索木の一種で、探索・挿入・削除を償却 O(log n) 時間でサポートすることで知られています。実は、スプレー木は効率的なフィンガー探索木として実装できることが示されています。

O(n) の初期化コストを支払う前提のもとでは、直前のアクセス位置から距離 d 離れた点へのアクセス（探索・挿入・削除のいずれも含む）の償却コストは O(log d) となります。ただし、この性質が成立するのは、常に直前にアクセスした要素を指す単一のフィンガーが存在する場合のみである点に注意が必要です。

計算モデルとの関係

上記の構成はいずれも、要素に対して許される操作が2つの要素の比較のみであるポインタマシン上で適用可能です。

一方、ランダムアクセスマシン（RAM）モデルにおいては、更新が定数時間・探索が O(log d) 時間となるフィンガー探索木が開発されています。この結果は、小さな木構造を表として事前計算するタブラリングの手法によって達成されたものであり、それでも要素の比較のみで動作します。