はじめての C - sekiyo’s diary

「二分木続き」

二分木 2回目の tutorial では、前に書いたことのある、木を変質させる- degenerate - 2つの最悪のケースを回避するための、さまざまな手法を詳しく調べることにしましょう。

先に学んだアルゴリズムでは、入力時にそれが十分ランダムになってる場合に、良好な検索木 - good search tree - が実現されます。

復習をかねることにして、すでに知っている挿入のアルゴリズムだと、こうなります ▽

int norm_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 = norm_insert(&(*tree)->left, key);
else if (key > (*tree)->data)
rc = norm_insert(&(*tree)->right, key);
else
rc = 0;

return rc;
}

いくつか異なった変更が加えられてるのに注意してください。

再帰にダブルポインタが使われてるので、コードはより複雑に見えますが、それは錯覚にすぎません。

一回、構造体へのダブルポインタの間接参照と、メンバへのアクセスという考え - concept - が使えるようになれば、このコードが簡単にたどれます。

このスタイルを選んだのは、それがより簡潔な傾向をもっていて、その短さ - brevity - が、この tutorial で後で学ぶことになるコードでは役にたつからです。

もう一つ違ってるのは、(関数で) いろいろと返すかわりに、1つの返り値を使っていることです。

このアルゴリズムでほとんどの用途では十分です。しかし、入力データがソート順かまたは交互順のどちらかで入るとすると、次のような最悪のケースのうちの一つが生じることになります。

最悪のケース 1) データの到着がソート順だとすると、右 (あるいは左) の分肢が生成し、結果として全く役たたずのリンクリストとして構築されてしまいます ▽

0 .1 ..2 ...3 ....4 .....5 ......6

最悪のケース 2) データの到着が交互順 - altemating order - なら、木はジグザグに生成し、それだと前の場合と同じくらい悪いものになります。

問題は、常に 1方向のみの選択ということにあって、それが二分木の働きを無効にしてしまうのです ▽

0 .6 1 .5 2 .4 3

これらのケースと比較するため、最良のケースを示してみましょう ▽

...3 .1...5 0.2.4.6

変質した木は最悪ですので、普通に戻すためこの問題を解決する必要があります。

必要なのは、木を最悪のケースから最良のケースに近づけるようにしておけるアルゴリズムです。方法として、最悪のシナリオを心配せずに、二分木のすべての役にたつ性質を引き出せるようにします。

考え方としては十分シンプルに思えるのですが、実行上はとても難しくなります。

この tutorial では、検索時間を最適なものに近づけるよう保証された方法をもつ、5つの例題を追っていきます。

手順にしたがって root ノードからの木全体のつりあいをとり、random number generator を通してランダムな順での挿入をひきうけ、すべてのノードが 1つの root にむかって集中するようもってくることでそれ自身で編成される - self-organize - ようにし、複合 AVL アルゴリズムによる挿入での再均衡 - rebalance - を行って、最終的には、ひどく複雑なものとならない、つりあいのとれた二分木をもった、確率的な (見込みのある) - probabilistic - データ構造体として再現していきます。