スキップリストと確率的平衡

連結リストに「飛び越し」を足す

ソート済みの連結リストは、順序こそ保つものの探索は O(n) です。先頭から1つずつ辿るしかなく、二分探索のような飛び越しができません。配列なら添字でジャンプできますが、リンクリストには添字がない。これがスキップリスト（skip list, William Pugh, 1990年）が解こうとした問題です。

発想はシンプルで、上位に「間引いた」リンクリストを重ねる。最下層（レベル0）は全ノードを含む通常のソート済みリスト。その上のレベル1は2つに1つ、レベル2はさらにその半分…と、上に行くほど疎なリストを積みます。探索は最上層の粗いリストで大きく飛び、行き過ぎたら1つ下の層に降りて細かく辿る。これを繰り返せば、各層で対象範囲を半分に絞り込めます。

レベル3:  HEAD ───────────────────────────────→ NIL
レベル2:  HEAD ──────────→ 17 ──────────────────→ NIL
レベル1:  HEAD ──→ 9 ───→ 17 ──────→ 31 ────────→ NIL
レベル0:  HEAD → 6 → 9 → 12 → 17 → 25 → 31 → 38 → NIL

19 を探す: L3でNIL手前まで→L2の17で止まる→L1の17→31の手前→
          L0で17の次25を見て「19は無い」と確定。

各層で半分に絞れるなら層の数は約 log2(n)、各層で辿る歩数も平均的に定数。よって探索は期待 O(log n) になります。これは平衡木が回転で達成するのと同じオーダーを、回転なしのリンクリストだけで得ている点が肝です。計算量記法の前提は計算量（Big-O）を参照してください。

平衡を「決定的」でなく「確率的」に保つ

ここで難問が1つあります。「2つに1つを上層へ」を厳密に維持しようとすると、挿入・削除のたびに全体のインデックスを振り直す羽目になり、結局 O(n) かかってしまう。決定的に間引きを保つのは高くつくのです。

Pugh の発想の核心は、間引きをサイコロに任せることでした。ノードを挿入するとき、そのノードを何層まで積むかをコイン投げで決めます。確率 p（典型的には p = 1/2）で「もう1段上げる」を繰り返し、裏が出たら止める。

function randomLevel():
    level = 1
    while random() < p and level < MAX_LEVEL:
        level = level + 1
    return level

この手続きでは、レベルが k 以上になる確率は p の (k-1) 乗。つまりレベル k のノードは期待的に全体の p の (k-1) 乗の割合だけ存在します。p = 1/2 なら、レベル0が全ノード、レベル1がその半分、レベル2が4分の1…と、期待値として理想的な間引きが自動的に実現されます。誰も明示的にバランスを取らないのに、確率の法則が平衡を生む。これが「確率的平衡（probabilistic balancing）」です。

挿入と削除 ― 各層の「直前ノード」をつなぎ替えるだけ

挿入は2段階です。まず探索と同じ要領で目的位置まで降りつつ、各層で「挿入位置の直前ノード」を記録します（update 配列）。次に randomLevel() で新ノードの層数を決め、記録した直前ノードのポインタを、新ノードを挟むようにレベル0から決めた層まで付け替えます。

function insert(key):
    update[] = 各レベルでkey直前のノードを探索しながら記録
    lvl = randomLevel()
    new = ノード(key, lvl)
    for i in 0 .. lvl-1:
        new.next[i]      = update[i].next[i]
        update[i].next[i] = new        # 局所的なポインタ付け替えのみ

ポイントは、触れるのは新ノードが属する層の直前ノードだけで、木のような広域のリバランスが一切起きないこと。削除も対称で、各層で対象の直前ノードのポインタを「対象の次」へ繋ぎ替えるだけです。回転も色塗りもない。この操作の局所性こそ、スキップリストの実装が平衡木より格段に短く書ける理由です。

最悪計算量と、それを恐れない理由

スキップリストの最悪計算量は O(n) です。理論上は、すべてのノードがレベル0にしか積まれない（全部コイン投げで即裏が出た）並びがあり得て、その場合はただの連結リストに退化します。にもかかわらず実用上これが問題にならないのは、その事象の確率が指数的に小さいからです。

n 個の要素で探索が O(log n) を大きく超える確率は n に対して急速にゼロへ近づきます。クイックソートの最悪 O(n^2) が現実にはまず起きないのと同じ理屈で、確率的アルゴリズムの「最悪」は敵対的入力でも避けられる点が決定版アルゴリズムと異なります。配列をソートしてから挿入しても、層数は入力順でなく乱数で決まるため偏りません。性能のばらつきを期待値で評価する考え方はならし計算量とも通じます。

なぜ並行処理で有利なのか

スキップリストが現代的に重要なのは、並行（concurrent）環境での扱いやすさです。平衡木のリバランスは、回転が木の広い範囲のポインタを同時に書き換えるため、複数スレッドで安全に更新するには広いロックや精緻なロックフリー設計が要ります。回転の途中で他スレッドが読むと木が不整合に見えるからです。

対してスキップリストの更新は、各層で「直前ノードの1本のポインタ」を差し替えるだけの局所操作です。これは CAS（compare-and-swap）一発で原子的に行いやすく、レベル0から上へ順に繋げば、探索中のスレッドからは常に整合した状態に見えます。実際、Java の ConcurrentSkipListMap はロックフリーのスキップリストで、ソート済みの並行マップを提供します。この性質はロックフリープログラミングの典型的な題材です。

まとめ

スキップリストは、ソート済み連結リストに確率的に間引いた上位層を重ねるだけで、平衡木と同じ期待 O(log n) を回転なしに実現するデータ構造です。要は「決定的に平衡を作り込む代わりに、コイン投げで期待的に平衡を生む」という発想の転換にあります。最悪 O(n) という弱点は確率が指数的に小さいため実用上無視でき、その代わりに実装の単純さと更新の局所性ゆえの並行化のしやすさという、平衡木にはない実利が得られます。これが、順序付き集合・マップを支える基盤として、データ構造の重要な選択肢にスキップリストが並ぶ理由です。