はじめての C
「二分木 続き 4」
データが ランダム順に 挿入されるのを 保証することで、二分木は 2つの 最悪のケースと なるのを 免れます。 これが、なぜ ランダム順での 入力を 試みたのかという (理由) なのです。
しかし、もし データが ランダムでは なかったときに、その木を さらに ランダムに 構築することが できれば いいですね。 それは 回転を 使うことで、できるのです。
分割アルゴリズムで、どんな風に ある (任意の) node を 取り上げ、それを 木全体の root に したのかを 思いだしてください。
このアルゴリズムと、木の root での 新しい ノードの挿入とを 組み合わせることで、可能になるのです ▽
int root_insert(struct Tree **tree, int key)
{
int rc;
if (*tree == NULL) {
*tree = new_node(key);
if (*tree == NULL)
rc = 0;
else
rc = 1;
}
else if (key < (*tree)->data) {
rc = root_insert(&(*tree)->left, key);
rotate_right(tree);
}
else if (key > (*tree)->data) {
rc = root_insert(&(*tree)->right, key);
rotate_left(tree);
}
else
rc = 0;
return rc;
}この関数を、以前 つくった norm_insert 関数と 比べてみると、再帰呼び出し後の 回転を 除けば、まったく 同じことに 気づきます。
root_insert 関数を partition (関数) と 比べると、partition では 挿入が なく、key による 比較の かわりに counting を 使ってること以外は、ほぼ 同じに見えます。
OK, これで 木の root への 挿入が できます。
でも、これが どうして、つりあいの とれた 二分木を 手に入れることに なるんでしょう ?
普通の 挿入と、root への 挿入とを ランダムに 選択することで、適正で 平均した ケースを 保つための 確率的な 方法が 使えます。
それが なぜ つりあいの とれた 木を 手に入れることに なるのか、まごついてるのなら、紙の上に 書くことで 試してみてください。
ソート順の 数を 選んで、root への 挿入と 通常の 挿入とを、ランダムに 選択してみるんです。
注意してほしいのは、つりあいが 完璧なことは めったに ありませんが、同じように、深刻で 最悪のケースも ほとんど ないということです。
そのコードは ▽
int insert(struct Tree **tree, int key)
{
if (rand() < RAND_MAX/2)
return root_insert(tree, key);
else
return norm_insert(tree, key);
}これは シンプルですね。
このコードでは 確率は 1/2 と なりますが、(関数) rand との 比較を 調整することで、それ以外の どんな (確率) であっても、weedle することが できます*1。
また、norm_insert の コードを insert (関数) へ 組み込み、root_insert を 特別な helper 関数と しています。
But I find the use of two insertion functions wrapped by a handler to be cleaner.*2
ランダムな 二分木を つくってみるときには、自分自身の 判断に 従うようにしてください。
これは 単に、ランダムな 木への 変換に 必要な ものなんです。
他の すべての 操作は、基本的な 二分木の 操作として 書くことが できます。
ランダムな 二分木は、次善の 策としての つりあいを とるために、簡単な 実装により 返り値を 1つ 受け入れることで、十分に シンプルになります。
優秀な random number generator *3 と その確率計算によって、たいていの 場合で、最適に 近い つりあいが 見込めます。
もちろん、最悪のシナリオとなる ケースの 可能性を 完全に 取り除きたいのでしたら、たとえば、前に つくった balance ルーティン のような 厳格な balancing algorithm の 使用が 必要となります。
しかし、もしも つりあいよりも 優れた 機能が 必要に なったら、どうするんでしょうか ?
いいですよ、そのためには、挿入と 削除のための ローカルな balancing algorithm という 恐ろしい 世界へと 入っていく 必要が あるのです。
