はじめての C
int skip_delete(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) {
for (i = 0; i < (*list)->level; i++) {
if (update[i]->forward[i] != x)
break;
update[i]->forward[i] = x->forward[i];
}
free(x);
while *1。 でも、その推測を 再度 チェックしてみるのも 全然 悪くありません。当然、とても わかりやすいので、このコードについての 最初の 推測は たぶん 正しいはずです。
注意するのは、コードの中に ところどころに - every once in a while - なにか、マクロの MAX_LEVEL を こっそり 紛れ込ませたことです。
これって 何なんでしょう ?
skip list では、それぞれの ノードへの forward links (いわゆる レベルです) の 数を セットするのに 乱数が 求められています。 もし 単に なにか 乱数を 取り入れるだけだと、即刻 大きな問題を 起こしてしまいます。 それで、乱数の範囲を 与えることが 可能な、レベルの 最大限度を 決めておきます。 例えば、0-3 に 対する 可能な レベルの 合計は 4 に なります。
そのマクロの MAX_LEVEL は こう なります ▽
#define MAX_LEVEL 4とても シンプルですね ? さて、それは かってに 数を 選び出すほどには やさしくは ありません。
レベルの 最大限度では、リストの確率と、リストに 入ってるらしい ノードの 上限とが 基本に なっています。
例えば、確率が 1/2 で リストの上限が 65,536 項目だと、MAX_LEVEL は、およそ 16 くらいに なるでしょう。
ふぅ〜、この tutorial は 長かったです。 読む人と それに 自分自身の ためにも、実際に この tutorial を 書いたように、全てのコードを 書き、テストして、デバッグを 行うため、時間を つくらなければ なりませんでした。
でも、それだけの 価値は ありました。 というのも、好みの コンパイラで この tutorial から 直接 copy & paste できますし、それは 正確に 動くでしょうから。
つりあいのとれた 二分木を 使って 効率よく 検索する 場面で、いくらかでも (正しい) 判断が できるようになり、データ構造の 選択にも 目が開かれれば、と 期待しています。
1つの tutorial だと、十分に 教えられるのは 1つの 主題 - topic - の 解釈だけですので、完全なものを 考えるには 本に 頼ることになります。
ですから、より多くの 情報で topic を 検討するためには、ネットで 検索したり 近くの本屋に でかけるように してください。
ここでは、データ構造の 実際のセンスを 養えるように 試みました。 なぜなら、ぼくらは プログラマであって、数学の証明を 書くため ただ 座ってるだけの 理論家では ないからです。
ここに 書かれた ことから、実際に データ構造を 実装したり、それらを 保守するのに 役にたつことが わかるでしょう。
このアプローチが 参考に なればと 希望します ... ね。
*1:*list)->level > 1 && (*list)->forward[(*list)->level] == NULL)
(*list)->level--;
return 1;
}
return 0;
}
同じように、配列 update と (今度は 明らかに) 検索とが 使われています。
このコードの残りを 紙の上で 動かしてみて、どのように 動くのかを 見てください。
これを 受け取った ほとんどの 人にとって、ざっと 見ただけで すぐ この logic を 理解するのに 何の 問題も ないでしょう((ちょっと 難しいような 気が ...
