はじめての C
さて、skip list の 構築と 削除の 実際の algorithm ですが、ここが (一番) おもしろいところです。
もっとも 効率的とは いえませんが、これは もっとも シンプルなものの 1つです。
skip list の いいところの 1つは、それを 理解するのが とても やさしくて、コードも 簡単なので、試したり 速度を 最適化したりするのに、プログラマを ひどく オビエさせることが ない、という点です。
skip list の 検索コードは シンプルで、highest レベルから 始めて、count down していきます。
それぞれの レベルでは、それが null に 届くまで、または key より 大きな値と なるまで、前方に ポインタを たどります。
loop が 終わると、検索により item が 含まれているか そうでないかが (わかります)。 null への チェックを 忘れないよう。
コードは、▽
int skip_search(struct Skip **list, int search_key)
{
struct Skip *x;
int i;
x = *list;
for (i = (*list)->level - 1; i >= 0; i--) {
while (x->forward[i] != NULL && x->forward[i]->data < search_key)
x = x->forward[i];
}
x = x->forward[0];
if (x != NULL && x->data == search_key)
return 1;
return 0;
}どう、シンプルでしょ ? もちろん 二分木検索のほうが もっと シンプルです。 その裏付けが、挿入や 削除の ルーティンに あります。
OK、では どのように skip list では 挿入を おこなうのでしょう ?
これは 検索ほど シンプルでは ありません。 しかし、もう わかったでしょうが、必要とするものが どこかを 見つけるために、検索が 使われています ▽
int skip_insert(struct Skip **list, int search_key)
{
struct Skip *update[MAX_LEVEL] = {0};
struct Skip *x;
int i;
x = *list;
for (i = (*list)->level - 1; i >= 0; i--) {
while (x->forward[i] != NULL && x->forward[i]->data < search_key)
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x == NULL || x->data != search_key) {
int lvl = random_level();
if (lvl > (*list)->level) {
for (i = (*list)->level; i < lvl; i++)
update[i] = *list;
(*list)->level = lvl;
}
make_node(&x, lvl, search_key);
for (i = 0; i < lvl; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
return 1;
}
return 0;
}配列 update が、それぞれ 必要なレベルで、新しいノードを 挿入しようとする箇所の 左側の リンクを 保守 - save - しています。
update の 使い方が、この algorithm で 唯一 少しばかり ややこしい ところです。 でも それは、リストを 繋ぎあわせるのと、適切な ノードの挿入には 必要なのです。
がんばって、紙の上で この logic を たどってみてください。
しかし、ほんの ちょっと 複雑なのにも かかわらず、skip list での 挿入は、今まで 見てきた どの つりあいをとる方法よりも 簡単なのです。
基本的な 二分木では 挿入だけだと もっと 短いのですが、そこでは 再帰によって - recursively - のみ 実行が されています。
skip list は 反復で - iteratively - 書くことで、やさしく できるのです。 これは、関数呼び出しの overhead が 回避できるため、実行上の 利益 - boon - に なっています。
削除の ルーティンも 同じように シンプルに なります ▽
