プログラミング言語 C

ある入力中の すべての単語を 計算処理する方法を 考えてみよう。
単語リストは 前もって わかっているわけではないので、それを つごうよく 分類しておいて 二分探索することは できない。
しかし だからといって 単語が来るたびに、その存在の有無を 線形探索するわけにはいかない - 時間が かかりすぎるからである (正確にいうと 実行時間の期待値は 入力語数の 二乗で 増加していく)。
任意の単語リストを 効率よく 処理するためには データを どのように 構築すれば よいのだろうか ?
一つの解は、単語が来たとき それを 順番になるよう 適当な位置に 入れて、単語の集合が 常時 分類されている状態にしておく やり方である。
しかし 線形の配列で 単語を シフトしながら、これを 実行する方法は、時間が かかりすぎて いい方法とはいえない。
そこで 二本木 (binary tree) と呼ばれる データ構造を 使うことにしよう。

ノードの構造は、次の 四つの成分をもつ 構造体として 表される。

1. struct Tnode {
2. char *word;
3. int cnt;
4. struct Tnode *left;
5. strucr Tnode *right;
6. };

ノード内の 再帰的宣言は 不思議に思うかもしれないが まちがいではない。なぜなら、
struct Tnode *left;
での left は Tnode のポインタの宣言であって 構造体自身では ないからである。

この tree は 単語ごとに 一つのノードを もっている。
各ノードには 左の子ノードへのポインタと、右の子ノードへのポインタ がある (もちろん、単語へのポインタと あと カウンタも)。
次に来た 単語が すでに tree に あるかどうかを 探すには root から 出発して そのノードに 格納されている 単語と比較する。このとき 二つが一致すれば (カウントされて) そこで止まる。
その単語が tree に 格納された 単語より 小さければ 探索は 左の子ノードに対して 続けられ、反対に 大きければ 右の子ノードが 調べられる。
求める方向に 子ノードが なければ その単語は tree に 含まれていないことになり、その場所が 新しい単語の おさまる位置となる。(P168-170)