スキップリストとは何か、またO(log n)の検索をどのように実現するか？

Question

Accepted Answer

**スキップリスト**は、複数の**「高速レーン」**レベルで拡張された順序付きリンクリストです。上位レベルは多くのノードをスキップするため、検索は下降して右に移動し、**O(log n)**の期待時間を実現します。これは、バランスツリーに対する確率的でより単純な代替案です。 ## 構造 ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (full list) ``` 各ノードは確率 `p`（通常0.5）で上位レベルに昇格されるため、平均的には各レベルは下位のレベルの半分のノード数を持ちます。 ## 検索 ```text search(25): start top-left, move RIGHT while next <= target, else drop DOWN a level. Repeat to level 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # coin flips decide a node's height return lvl ``` ## 計算量 | 操作 | 期待値 | スペース | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## バランスツリーとのトレードオフ - **長所:** 赤黒木やAVLよりはるかに実装が簡単；回転操作がない；簡単なロックフリー版（Redis ソート済みセット、Java `ConcurrentSkipListMap`で使用）。 - **短所:** 確率的保証（最悪ケースではない）；ノードごとに余分なポインタ。 ## なぜ重要なのかスキップリストは、ツリーと同等のO(log n)の順序付き操作をはるかに少ないコードで実現し、ロックフリー並行処理も容易です。そのため、Redisなどの実際のシステムで採用されています。これは**ランダム化**を使用して複雑な決定論的バランシングロジックを置き換える優れた例です。