はじめての C

lang

「二分木 続き 10」

skip list は、ランダム数 = 乱数を 使うことで、効率のよい 構造を つくりあげる、確率的な - probabilistic - データ構造です。

その方法は、(以前 つくった) ランダムに構築する - randomized - 二分木と 同じく、乱数を その 挿入 algorithm で 使っています。

skip list は とても シンプルな リンクリストですが、次のノードを ポインタで 指すかわりに、次のノードへの ポインタの 配列を もっています。

しかし、より高い レベルでの ポインタは、さらに リストの 下側のノードを 指し示しています。 skip は 次のような 図で あらわすことが できます ▽


4) ------> 6 -----------------------------------------------> ~
3) ------> 6 -----------------------------------> 25 -------> ~
2) ------> 6 ------> 9 -------> 17 -------------> 25 -------> ~
1) -> 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26 -> ~

これは よくできた skip list で、矢印(->)は リンク先を あらわし、N) は 1 から 4 までの レベルナンバーで、1 が lowest, 4 が highest (レベル) と なります。 チルド(~)は、リストの終わりか null を あらわしています。

検索では、次のポインタを 追跡していき、必要なときには 下のレベルへ 移動することで、とても 効率よく 行えます。 例えば、上の skip list で 19 を 捜す 検索だと、次のように 通路 - path - を たどっていきます ▽


Level 4 -- 6
Level 2 -- 9
Level 2 - 17
Level 1 - 19

完全に つりあいのとれた 二分木だと ▽


     12
  6        21
1   7   17    25
     9    19    26

同じように 検索すると、通路を 12, 21, 17, 19 と たどっていきます。

同じ 検索では、skip list (リンクリストですよ !) は、完全な 二分木と まったく同じだけの step 数で、かたずけてくれるのです。

このことは、特に そんな木を つくるのが 難しく、リンクリストを 使って 何か 簡単に 動かせないか、と 考えたときに、非常に 役にたちます。

skip list だと、どうして 構築 - build - や 検索が やさしくなるのでしょうか ?

普通の リンクリストほどは やさしくは ありませんが、つりあいのとれた 二分木よりは ずっと 簡単です。 では 始めてみましょう。

はじめに、ノードへの 定義が 必要となります ▽

struct Skip {
struct Skip **forward;
int level;
int data;
};

とても シンプルですが、skip list を 保守するには、挿入 algorithm で ルーティンで ランダムに 確定するために、ノードには どれだけの レベルが いるのかを 知る 必要が あります。

space を 確保するため、skip の ポインタには 動的な 割り当て 配列 - dynamically allocated array - を 使うことにしましょう。

レベルを 最大値に 設定することでも 同じく、簡単に 配列を つくって 使うことが できます。

しかし、1つの ノードが 使用できる リンクを 1つしか もてないとすると、例えば、14個分の 余分な ポインタを 設ける意味が ありませんね。

この algorithm だと、どちらが より満足できるかで 選んだとしても、その いずれの方法でも うまく 動いてくれるでしょう。

次は、新しいノードが 設定できるよう、ランダムな レベルを 選択するための、何らかの コードを セットアップする 必要があります。

ここに 示すのは、シンプルな algorithm で、skip list を 紹介した 論文に 載っていたものです (Skip List: A probablistic Alternative to Balanced Trees, William Pugh) ▽

int random_level(void)
{
int lvl;

lvl = 0;
while (rand() < RAND_MAX/2 && lvl < MAX_LEVEL)
lvl++;

return lvl;
}

また、状態を シンプルに 保つためと、modularized since we are good little structured programmers*1 ためには、make_node 関数も 必要です ▽

int make_node(struct Skip **node, int level, int data)
{
int i

*node = malloc(sizeof(**node));
if (*node == NULL)
return 0;
(*node)->forward = malloc(sizeof(*(*node)->forward) * level);
if ((*node)->forward == NULL)
return 0;
for (i = 0; i < level; i++)
(*node)->forward[i] = NULL;
(*node)->data = data;
(*node)->level = 0;

return 1;
}

このコードでは 割り当てを 行っていて - allocate -、null に skip への ポインタの 配列を 取り込むことで、新しいノードの データと レベルとを セットしています。

*1:訳せません ...