Skip Lists: A Probabilistic Alternative to Balanced Trees(1990)
May 6, 2023Skip Listsは、バランス木の代用になるアルゴリズムである。 Skip listsのノードは、ランダムに選ばれた後続のノードへのポインタをもつ。 ランダムに参照するノードを選ぶことで、バランス木よりも単純なアルゴリズムで、計算量を均衡をでき、さらに最悪計算量をより小さくできる。
Skip listsは、キーを指定した検索、挿入、削除をもつ抽象データ構造である。
レベル\(i\)のノードは\(i\)個の後続のノードを参照し、ポインタには\(1,\dots ,i\)までの順番がついている。
以下は、論文にあるSkip listsの例である。
リストの先頭のノードは、挿入された値をもたずノードのレベルの最大値\(\textit{MaxLevel}\)個のポインタをもつ。
リストの末尾は、挿入されるキーよりも十分大きい値をキーにもつノード\(\texttt{NIL}\)がある。
ノードがもつポインタ数の最大が\(i\)であるとき、skip listsのレベルは\(i\)である。
レベル\(i\)のskip listsのヘッダにあるポインタのうち、\(i+1\)番目以降のポインタは、\(\texttt{NIL}\)を参照する。
初期状態のskip listsのノードは、headerと\(\texttt{NIL}\)のみである。 Skip listsのレベルは1であり、headerは\(\texttt{NIL}\)を参照するポインタを1つだけもつ。
検索するときは、各ノードにおいて、目的のキー未満のキーをもつノードへのポインタが見つかるまで降順に探す。 以下は検索の疑似コードである。
Search(list, searchKey)
x := list->header
-- loop invariant: x->key < searchKey
for i := list→level downto 1 do
while x→forward[i]->key < searchKey do
x := x->forward[i]
-- x→key < searchKey <= x->forward[1]->key
x := x->forward[1]
if x->key = searchKey then return x→value
skip listsに挿入したいキーがあれば、値を上書きするだけでよい。 以下は、挿入の疑似コードである。
Insert(list, searchKey, newValue)
local update[1..MaxLevel]
x := list->header
for i := list->level downto 1 do
while x->forward[i]->key < searchKey do
x := x→forward[i]
-- x->key < searchKey ≤ x->forward[i]->key
update[i] := x
x := x->forward[1]
if x->key = searchKey then x->value := newValue
else
lvl := randomLevel()
if lvl > list->level then
for i := list->level + 1 to lvl do
update[i] := list→header
list->level := lvl
x := makeNode(lvl, searchKey, value)
for i := 1 to lvl do
x->forward[i] := update[i]->forward[i]
update[i]->forward[i] := x
キーがなければ、新しいノードを挿入する。 コードにある\(\texttt{update}\)は挿入箇所以前のノードを格納する配列である。 \(i\)番目の要素は、\(i\)番目のポインタが挿入箇所以降のノードを参照する最も後ろにあるノードである。
以下は削除の疑似コードである。skip listのレベルと同じノードがなくなれば、listのレベルを下げる。
Delete(list, searchKey)
local update[1..MaxLevel]
x := list->header
for i := list->level downto 1 do
while x->forward[i]->key < searchKey do
x := x->forward[i]
update[i] := x
x := x→forward[1]
if x->key = searchKey then
for i := 1 to list->level do
if update[i]->forward[i] != x then break
update[i]->forward[i] := x->forward[i]
free(x)
while list->level > 1 and list->header->forward[list->level] = NIL do
list->level := list->level – 1
雑記
疑似コードを論文から引用したが、もとの挿入のコードには、後ろから3行目に未定義変数levelがある。
おそらくlvlの誤記であるので、上の引用では、修正したコードを掲載した。
バランス木よりも実装が単純と主張している。 ただし、アルゴリズムから自明であるものとして、バランス木との実装の複雑さの比較はない。
バランス木の代わりになると主張されているが、逆順の探索はできなさそう。