プログラミング作法 第２章 アルゴリズムとデータ構造 ２．８ ツリー
ツリーは階層的データ構造であり、それぞれの項目が値を持ち、ゼロ個以上のほかの項目を指し、ほかの１個だけの項目によって指されるような項目の集合を記憶する。唯一の例外はツリーのルートで、ルートを指す項目は存在しない。
ここでは、それぞのノードに２つのリンクがある二分探索木(binary search tree)の原理を取り上げよう。これは一番簡単に実装できるし、そのわりにはツリーの基本的な性質を明らかにできるからだ。二分探索木の１つのノードは、値と、自分の子を指す２つのポインタleftとrightを持つ。そのノードの子が２個未満だと、子ポインタがヌルになる可能性もある。二分探索木の場合には、ノードに存在する値によってツリーが決定される。ある特定のノードの左側にあるすべての子はそれより低い値を持ち、右側にあるすべての子は高い値を持つからだ。
typedef struct Nameval Nameval; struct Nameval { char *name; int value; Nameval *left; /* より小さい */ Nameval *right; /* より大きい */ };より小さいとより大きいのコメントは、このリンクの性質を表している。つまり左の子にはこれより小さな値が、右の子には大きな値が記憶されているという意味だ。
二分探索木(これ以降この節では単に「ツリー」と表記)を作成するには、左右のどちらか適切なほうの枝をたどりながらツリーを再帰的に降りていき、新しいノードをリンクするのにふさわしい場所を見つける必要がある。この新しいノードは、名前と値と２個のヌルポインタによってきちんと初期化されたNameval型のオブジェクトでなければならない。新しいノードはリーフ(leaf:葉)として追加される。これはつまり、まだ子が１個もないという意味だ。
子が１個もない。leftとrightが両方ともNULL。
ルートからリーフまでの個々の経路がほぼ同じ長さのツリーを、バランス木(balanced tree)という。バランス木のメリットは、ツリーで項目を検索する作業がＯ(logn)の処理で済む点にある。二分探索の場合にはステップごとに候補の数が半減していくからだ。
項目が到着するたびにツリーに挿入していると、ツリーがバランスしなくなる可能性がある。現実にはひどくアンバランスになることもある。たとえばすでにソートされた形で要素が到着したりしたら、コードは常にツリーの一方の枝を降りていくことになる。すると事実上rightのリンクを直線的に降りていくリストになってしまい、リストに内在するありとあらゆる性能上の問題が生じる。しかし要素がランダムな順番で到着するならそんなことはまず起こらないので、ツリーは多少なりともバランスする結果になる。
バランスすると保証されたツリーを実現するのは大変だ。それが多くの種類のツリーが存在するひとつの理由でもある。
ツリーを検索する関数lookupについて
それまでに項目が見つからなかった場合のlookupの最後の動作は、自分自身の呼び出しの結果を返すことだ。これは末端再帰(tail recursion)と呼ばれる事態だ。
さて、いったんツリーをたどれるようになったら、当然それ以外の一般的な処理を実行することになる。リスト管理のところで出てきたテクニックを一部利用して、たとえばそれぞれのノードで関数を呼び出す汎用ツリー走査ルーチンを書くことも可能だ。ただし今回の場合には、判断を下さなければならないことがある。この項目に対する作業をいつ実行し、ツリーのほかの部分をいつ処理すればいいのだろうか。
左部分木に行ってから右部分木に行くまでのちょうど中間の時点で処理を実行するやり方を、間順走査(in-order traversal)という。
/* applyinorder:treepに対してfnを間順実行 */ void applyinorder() { 左側の木を降りる(); (*fn)(); 右側の木を降りる(); }この処理順が使われるのは、ノードをソートされた順序で処理する必要がある場合だ。
後順走査(post-order traversal)は、子を訪れてから現在のノードに対する処理を実行することを言う。
/* applypostorder:treepに対してfnを後順実行 */ void applypostorder() { 左側の木を降りる(); 右側の木を降りる(); (*fn)(); }後順走査は、ノードに対する処理がその下にある部分木に依存するケースで使われる。その例としては、ツリーの高さの計算(２個の部分木それぞれの高さのうち大きいほうをとり、それに１を加算する)やグラフィックス描画パッケージでの木のレイアウト(ページ上にそれぞれの部分木の領域を割り当て、それらを組み合わせてこのノード用の領域とする)、記憶領域の合計の計算などがある。
３番目の選択肢は前順走査(pre-order traversal)だが、めったに使われないのでここでは割愛する。
現実に二分探索木が使われる場面はそれほどないが、枝分かれの非常に多いＢ木は２次記憶上で情報を管理する手法として使われている。日常的なプログラミングでよく使われるツリーの一例としては、文や式の構造を表現するツリーがある。
mid = (low + high) / 2;
たとえばこの文は、下の図の解析木(parse tree)によって表現できる。このツリーを評価するには、後順走査を実行し個々のノードで適切な処理をすればいい。
問題２−１１
lookupとnrlookupの性能を比べた場合、比較処理の回数は同じだが、関数の呼び出し手続きの分だけ、繰り返しに比べて再帰のほうが性能が落ちることになる。
問題２−１２
Namevalのツリーを使った場合、ツリーに登録した時点で二分探索木の性質に基づいてデータがソートされている状態になる。間順走査を使ったソートルーチンは、データを順に追いかけて配列に記録する方式をとればいい。以下のようになる。
typedef struct btsort {
int value[10]; /* データの格納場所 とりあえず固定領域で10とする */
int num; /* 実際に格納されているデータ数 */
} Btsort;
/* データはツリーに登録済みであるとする
* ツリーのルートはNameval treerootとする
*/
void sort(void)
{
Btsort dim;
memset(&dim, 0, sizeof(Btsort);
/* 間順走査を実行し、dim.value[]に値をセットする */
applyinorder(&treeroot, sortindim, &dim);
}
void sortindim(Nameval *treep, void *arg)
{
Btsort *btp = (Btsort *)arg;
btp->value[btp->num] = treep->value;
++(btp->num);
}計算量はツリーに登録する時点で発生し、Ｏ(logn)になる。性能の悪化は、ソート済みのデータが与えられるなどして、アンバランスなツリーが構築されたさいに起こると考えられる。ライブラリ標準のクイックソートと比べて、性能が劣るとは考えられない。
問題２−１３
Namevalのツリーの正しさは、ツリーの左右と値の大小関係にある。そこに注目してテストプログラムを書く。
まず、あるノードを取得する。そのノードと比べて、左側のノードのほうが値が小さく、右側のノードのほうが値が大きいことを確認する。これをツリーにそって行えばよい。
