1. 序章

このチュートリアルでは、スキップリストについて説明します。スキップリストは、バランスツリーの一般的な確率的代替手段です。 スキップリストがどのように機能するかを説明し、スキップリストに挿入、検索、削除の3つの標準操作を実装する方法を示します。

2. 動機

番号付きの並べ替えられたリンクリストを想像してみましょう。

その中の数値を検索すると、最悪の場合(検索された値がリストの最大値よりも大きい場合)にすべての要素をトラバースします。 最初のノードから開始し、最後のノードへのすべてのポインターに従います。

次に、他のすべてのノードの2ノード先にポインタを追加しましょう。

最初のノードから始めて、一度に2つのノードをスキップできるため、最悪の場合、探している番号を見つけるか、リストにないことを確認する前に、複数のノードにアクセスすることはありません。

4つおきのノードにその4つ前のノードにポインタを与えるとどうなりますか? その場合、最悪の場合にアクセスするノードの数は約になります。 一般に、すべてのノードの前にノードノードへのポインターがある場合、最悪の場合の検索シナリオで調べる必要のあるノードの数を。に減らします。

それがスキップリストの背後にある主な考え方です。 これらには複数のフォワードポインタを持つノードが含まれているため、高速ルックアップが可能です。 フォワードポインタを持つノードは、レベルノードと呼ばれます。 ノードの半分はレベル1、ノードはレベル2、レベル3、ノードはレベルなどです。

3. 確率的構造としてのスキップリスト

ただし、上記のスキップリストの場合、削除と挿入は実用的ではありません。 要素を削除または挿入した後、適切な位置にある新しいノードを指し続けるようにポインタを更新する必要があります。

オーバーヘッドを回避する方法は、変更をローカルに保つことです。 上位ノードの位置を修正しない場合は、これを行うことができます。 たとえば、新しいノードのレベルをランダムに決定できるため、上位レベルのノードが必ずしも互いに()ノードであるとは限りません。 代わりに、レベルポインタは、リスト内の次のレベルノードを指します。 このように、挿入および削除によって、挿入されたノードの直後のノードを指すポインター以外のポインターが再配置されることはありません。 同様の理由が削除にも当てはまります。

検索の対数の複雑さを維持するために、上記の例eと同じレベルのサイズの比率を維持できます。 これを行うには、level-()ノードをリストに挿入しながらそのレベルに進める確率を設定します。 その場合、レベルにほぼノードがあります。

したがって、スキップリストは、ノードのレベルがランダムに決定されたマルチレベルのリンクリストです。

3.1. レベルを設定する方法

事前にレベルを制限しない場合、レベルは、挿入中にノードを進めるために選択したチャンスにのみ依存します。 上記の例のように使用する必要はありません。 任意の確率を使用できますが、検索の時間計算量は引き続きです。

新しいノードのレベルを選択するための擬似コードは次のとおりです。

3.2. 期待されるレベル

ノードは、最初にレベルノードになることなくレベルに到達することはできません。 したがって、ノードがレベルにある確率はです(最初のレベルを決定するためにサイコロを投げないため、1を引きます)。 そこから、ノードのレベルから1を引いた値が、「成功確率」として幾何分布に従うことがわかります。 したがって、ノードのレベルの期待値は次のとおりです。

(1)  

3.3. ポインタの数

ノードを持つ単一リンクリストにポインタがあります。 それらの1つは頭を指しており、残りはノード間のリンクを形成しています。 すべてのノードのレベルがであるため、レベル1のポインターがあることがわかります。

2番目のレベルでは、レベル2ノードの予想数と同じ数のポインターが必要です。 同じことがより高いレベルにも当てはまります。 したがって、予想されるポインタの数は次のとおりです(の場合)。

   

最大レベルをに設定すると、ポインターの数は上から。によって制限されます。 はに依存しないため、スキップリストの予想されるメモリの複雑さはであり、リンクリストのスペースの複雑さと同じです。 さらに、単一リンクリストが持つポインタの2倍を超えて使用することはないことがわかります(以降)。

3.4. インフラストラクチャ

次の属性を持つデータ構造のノードを検討します。

  • :含まれる値
  • :さまざまなレベルでの後継者へのポインタの配列

同様に、リストは2つの属性を持つデータ構造であると想定します。

  • –リストの現在の最大レベル
  • –レベルでのヘッドへのポインターの配列

4. スキップリストに挿入する方法

値のあるノードをスキップリストに挿入するには、次の3つのことを行う必要があります。

  • それを配置する場所を見つける
  • そのレベルを選択してください
  • 新しいノードを指すポインタを更新します

新しいノードのレベルを選択する方法については、すでに説明しました。 それを配置する場所を見つけるために、最上位のヘッドノードから開始し、のように2つの連続するノードに到達するまでポインターをたどります。 そのようなノードが存在し、現在のレベル(つまり、最上位レベル)より大きくない場合は、を指すように更新し、新しいノードをを指すように設定する必要があります。 次に、最下層に到達するまで手順を繰り返します。

新しいノードのレベルがリスト全体の現在の最大レベルよりも高い場合は、新しいレベルを挿入する必要があります。 これを行うには、新しいノードをヘッドとして設定します。

4.1. 擬似コード

挿入の擬似コードは次のとおりです。

4.2. 例

このスキップリストに番号を挿入するとします。

これらのポインタに従って、配置する場所を見つけます。

また、レベル2ノードとして設定することを選択したとしましょう。 挿入後のリストは次のようになります(新しいノードと新しいポインターは赤で表示されます)。

4.3. 複雑

挿入と削除の複雑さは、検索の複雑さによって支配されます。理由を確認するために、新しい要素を挿入する前に、それを配置する場所を見つける必要があることに注意してください。 ノードの削除についても同じことが言えます。 削除する前に見つける必要があります。

5. スキップリストを検索する方法

スキップリストで値を検索する方法を見てみましょう。 リストに挿入するのと似ていますが、ポインタを更新する必要はありません。 トップレベルから始めて、より大きい値が見つかるまで、ポインターをたどることができます。 前者の場合、対応するノードを返します。 後者では、1レベル下に移動し、手順を繰り返します。 より大きい最下位ノードを検出またはカスケードすると、検索は終了します。値がリストにある場合は、その直前のノードに含まれている必要があります。それ以外の場合は、を返します。

5.1. 擬似コード

検索の擬似コードは次のとおりです。

5.2. 例

上記のリストで17を検索する際の手順は次のとおりです。

5.3. 予想される複雑さ

予想される検索の複雑さを、予想される検索パスの長さとして表します。左上のノード(レベルは)で始まり、ゴールノード(下のレベル)で終わります。

パスを逆に分析することで、予想される長さを簡単に導き出すことができます。 これを2つの部分に分割します。

  • トップレベルへのパス
  • 左上のノード(最上位のヘッド、)と最初の一番上のノードを逆に接続するパス

最初の部分の予想される長さとします。 スキップリストは非決定論的であるため、可能な構造を期待します。したがって、最上位のノードレベルから、確率で1レベル上に戻るか、確率で左に移動できます。

   

(すでにトップレベルにいる場合はトップレベルに移動する必要はありません)ので、次のようになります。

   

さまざまなレベルのノードの数を分析したときに、2番目の部分はすでに解決しました。 したがって、トップレベルにはノードが含まれていると予想されます。 したがって、検索の予想される複雑さの合計は次のとおりです。

(2)  

5.4. スキップリストの対数的に予想される複雑さを取得する方法

アイデアは、定数になるような方法で選択することです。 したがって、次の対応する方程式を解きます。

   

したがって、式の最初の部分( 2 )はになり、2番目の部分はになります。 したがって、の対数を。に設定すると、予想される複雑さの合計は対数になります。

この分析では、それがリストの最大レベルであり、常にトップレベルのヘッドから検索を開始すると仮定しました。

5.5. スキップリストの最悪の場合の複雑さ

最悪の場合、スキップリストは単一リンクリストに縮退し、最大値よりも大きい値を探しています。 したがって、リスト全体をトラバースするため、最悪の場合の複雑さはです。

それは悲観的な結果ですが、スキップリストはそれでも報われます。 理由は、ランダムなピボット選択を使用したQuicksortの場合と同様です。 理論的には最悪のパフォーマンスが低下する可能性がありますが、まれにしか発生しません。 実際には、スキップリストは非常に効率的です。 対数的に予想される複雑さはそれを示しています。

6. スキップリストから要素を削除する方法

削除は挿入と検索に似ています。 まず、削除する値を含むノードを見つけます。 その過程で、どのノードがそれを指しているかを記憶します。 ノードが見つかったら、そのノードをその先行ノードからリンク解除し、適切なレベルでノードの後続ノードをポイントします。

7. 結論

この記事では、スキップリストを紹介しました。スキップリストの3つのアルゴリズム、挿入、検索、削除を紹介しました。 また、リストを非決定論的なデータ構造として分析し、検索の対数的に予想される複雑さを取得する方法を示しました。

検索の複雑さが挿入と削除の複雑さを支配するため、後者の2つの操作も対数にすることができます。最悪の場合の複雑さは線形ですが、スキップリストを使用すると最悪のシナリオとして効果があります実際にはありそうにありません。