はじめての C

「二分木」

二分探索法 - binary search - は、役にたつ 強力な アルゴリズムです。ただし、リストの中を 自在に 動ける - jump around - ように するための、二分探索法に 適した データ構造 - data structure - を 選択しておく、という 規制が あります。

リンクリストは 実用的で、どの箇所が 必要になっても、捜しだすまで 連続して ポインタを 追跡します。

配列は もっとも シンプルな 選択に なります。というのも、すでに 言語に 組み込まれており、使い方も やさしくて コンパクトだからです。それに 検索も 高速で、どこの 配列であっても 効率的に 取りだすことが できるという 利点が あります。

二分探索の 代わりに 配列を 利用すると、新しい項目の 挿入や 削除が 必要な際には その魅力が 半減してしまいます。

コンピュータサイエンスを 学生が 学び始めたときなど、配列の 要素の移動、すなわち その挿入 あるいは 削除の 処理については、操作が expensive に なると いうので、できるだけ 避けるようにと いわれます。

データ構造の リンクだと、挿入や 削除には 適しています。ただし より速く 動けるような やり方で リンクを おこなう 必要が あります。

それで、少し detail を 足すという 追加策を 設けないと、そのままでは 目標に 達しないだろうと 思います。

構造体を 効率的に 検索できるよう リンクするのではなく、それぞれの ノードを、その値より 大きいか 小さいかによって、別の ノードへ リンクできれば、ということが 言えるのです。

二分木探索の 基本的な 仕組みとして、0 または それ以上の ノードの 集合が あり、それぞれの ノードが ポインタによって、左側の分肢 - subtree - と 右側の分肢に 繋がっています。

左側の 分肢は 常に その値が 親 - parent - より 小さく、右側の 分肢は 常に その値が 親よりも 大きくなっています。

それぞれの 分肢も、そこが null で なければ、自分自身の 二分木を もっています。

つまり、二分木は 再帰的に - recursively - 定義されているのです。

二分木は、一見すると、シンプルな データ構造です。リンクリストのように、そこで 動く 基本となる コードも 簡単だし、追跡も 容易です。しかし もし 他に、つりあい - balancing - のような 要件が 加えられたときには、複合的 - complex - に なって、非常に 高速に なります。

この tutorial では つりあいに ついては 扱いません。将来 連載することに 期待してもらえれば ...