なにこれ

前回の続き。

今回はスキップリストを用いて、SSetインターフェースとListインターフェースを実装します。

SSetインターフェース

Setインターフェースとは、重複がない要素の集まりを指します。ここで要素に順序付けない場合をUSet、順序付ける場合をSSetとします。

2・3章で扱った配列や連結リストは、いずれも各ノードを順に辿るという処理が必要でした。

そこで、①1つ1つ辿らずにスキップできるようにする②スキップ具合はランダムに任せるとしたのがスキップリストです。

f:id:frogdusk:20190717122209p:plain

底辺はSLListのように単方向にポインタを持った構造ですが、ポインタに高さという概念が入ります。

そして同じ高さ同士は単方向に繋がります。
最初にある番兵(sentinel)は最大の高さを持っており、各ノードは追加される際に高さをランダムに選びます。

裏が出るまでコインを投げ続けた回数を高さにします。
1/2で0, 1/4で1...となり、高さの期待値は1になります。

実装上はどうするかというと、2進数で32桁の値をランダムに取得し、先頭から1が連続する回数を数えています。
(自分で実装したらrandom.random() <= 0.5を32回繰り返すと書いちゃいそう。学び。)

z = random.getrandbits(32)
k = 0
while z & 1:
    k += 1
    z = z // 2
return k

通常1つ1つ辿ればO(n)かかっていたところが、O(logn)で済むようになります。

探索では、「sentinelの一番高いところから辿り、同じ高さのnextの値を見て、行き過ぎた！となったら1段低く下がり、そうでないならそのノードに進む」ことを繰り返します。
(順序付けられたSSetだから実現できることです)

Listインターフェースの場合は、SSetインターフェースのように値比較で進むべきかを判断できません。
そこで高さ同士のインデックス距離を別途管理します。