スキップリストのフィンガー探索：データ構造の特性と仕組みを徹底解説

スキップリストは、確率的に階層を構築することで平衡木に匹敵する高速な探索を実現する連結リスト型のデータ構造です。本記事では、スキップリストにおける「フィンガー探索（finger search）」の仕組みと、その基盤となる重要な特性についてわかりやすく解説します。

スキップリストにおけるフィンガー探索の基本

スキップリストでは、要素 b を含むノードを出発点として、別の要素 a に対するフィンガー探索を行うことができます。具体的には、そのノードの位置から探索をそのまま継続するだけでよく、必ずしもリストの先頭からやり直す必要はありません。

ここで重要なのは探索の方向です。a < b の場合は探索は後方（左方向）へ進み、a > b の場合は前方（右方向）へ進みます。

後方探索と前方探索の違い

後方への探索は、通常のスキップリスト探索と対称的な動作となるため、比較的単純に処理できます。一方、前方への探索は実際にはより複雑になります。

通常、スキップリストの探索が高速に動作するのは、リスト先頭のセンチネル（番兵）ノードが最も高いノードとして扱われているためです。しかし、フィンガー（探索の出発点）が高さ1のノードに関連付けられているケースでは、探索中に上位レベルへ登る操作が必要になることがあります。これは通常の探索では決して発生しない現象であり、前方探索が複雑になる理由のひとつです。

スキップリストの主要な特性

スキップリストが注目される最大の理由は、以下の優れた計算量特性にあります。

• 空間計算量： 期待線形空間（expected linear space）のみを必要とする
• レベル数： 期待 O(log n) のレベル（層）を持つ
• 探索： 期待 O(log n) 時間での検索をサポートする
• 挿入・削除： 指定位置への挿入・削除を期待 O(1) 時間でサポートする

フィンガー探索の拡張と実装の詳細

スキップリストには多様な特性や拡張が研究されており、期待 O(log d) 時間（d は出発点から目的の要素までの距離）でフィンガー探索を実現する擬似コードも提案されています。距離が短いほど高速に探索できる点が、通常の探索との大きな違いです。

後方フィンガー探索用のデータ構造

後方フィンガー探索を効率的に行うため、ノード V へのフィンガーは、期待 O(log n) 空間の専用の「フィンガーデータ構造」として格納されます。このデータ構造は、各レベル i ごとに、V の左側に存在するノードへのポインタを保持します。ここで、レベル i のポインタは V 自身、あるいは V より右側のノードを指します。フィンガーを移動させる際には、このポインタ列を対応するように更新する必要があります。

後方フィンガー探索の手順

後方フィンガー探索は、次の2段階で実行されます。

1. 開始ノードの特定： フィンガーデータ構造内のノードをレベルの昇順に走査し、探索キー y より左側に位置する最も低いレベルのノードを見つけます。
2. 下方への探索： 特定したノードから下位レベルへ向かって探索を進めます。この処理は、標準的なスキップリスト探索と同様の流れで行われます。

この仕組みにより、既知の位置から近い要素を効率よく検索でき、全体の探索コストを大幅に削減できます。