データ構造のスキップリスト

スキップリストでは、このポイントaから検索を続行するだけで、要素bを含むノードから要素aを指で検索できます。

a bの場合、検索は順方向に進むことに注意してください。

後方の場合はスキップリストでの通常の検索と対称的ですが、前方の場合は実際にはもっと複雑です。

通常、スキップリストでの検索は、リストの先頭にある番兵が最も高いノードと見なされるため、高速であると予想されます。

ただし、指を高さ1のノードに関連付けることができます。このため、検索中に登ることはめったにありません。通常は発生しない何か。

スキップリストの最も重要なプロパティは、期待される線形空間を必要とし、期待されるO（log n）レベルを含み、期待されるO（log n）時間での検索をサポートし、期待されるO（1）の特定の位置での挿入と削除をサポートすることです。 ）時間。

スキップリストが予想されるO（log d）時間で指検索をサポートする方法の擬似コードを含む、スキップリストのさまざまなプロパティと拡張機能について詳しく説明しました。後方指検索を容易にするために、ノードVへの指は期待されるO（log n）スペース指データ構造として格納され、各レベルiについて、レベルiポインターが指すVの左側のノードへのポインターを格納します。 VまたはVの右側のノード。指を動かすには、それに応じてこのポインタのリストを更新する必要があります。

後方指検索は、最初に検索キーyの左側にある指データ構造の最下位ノードを識別することによって実行されます。ここで、指データ構造のノードはレベルの昇順で考慮されます。

その後、検索は、標準のスキップリスト検索と同様に、識別されたノードから下に進みます。