Interactive
スキップリスト可視化
スキップリストは、ソート済みの連結リストに「間引かれた近道レイヤー」を重ねるだけで、 平衡木と同じ期待O(log n)の検索・挿入を実現するデータ構造です。 各ノードがどのレイヤーまで昇格するかはコイン投げで決まり、 回転もリバランスも一切要りません。検索の経路と、挿入時のコイン投げを1歩ずつ動かして確認できます。
検索
挿入（コイン投げでレベルを決定）
各ノードはコイン投げ（確率p=0.5）で昇格し続け、裏が出るかレベル上限で止まる——だから上のレベルほどノード数が半分ずつ減っていく。 検索は最上位レベルから右へ進めるだけ進み、行き詰まったら1段下りるを繰り返すので、期待計算量は木の高さと同じO(log n)。回転もリバランスも要らないのに、平衡木と同じ速さが出る。
ここが分かる
- 検索は最上位レベルから開始し、次のノードが目標以下なら右へ、行き詰まったら1段下へを繰り返すだけ。単純な操作の繰り返しで、木構造と同じ効率が出る。
- 各ノードは確率p（既定0.5）でコイン投げを続け、表が出るたびに1レベル昇格する。だから上のレベルに行くほどノード数がおよそ半分ずつ減り、これが探索を「間引く」効果を生む。
- 平衡木（AVL・赤黒木）のような回転やリバランスの実装が要らないため、並行アクセス（ロックフリー実装）との相性が良く、Redisの Sorted Set 内部などで実用されている。