データ構造（ツリー）の世界観

データ構造（ツリー）に関する世界観です。

ツリー

ツリーは階層的なデータ構造で、ルート（根）からノード（節）が作られ、最終的にリーフ（葉）にたどり着く。

また、ノードは子孫を持つことができ、祖先をもつこともある。

サブツリーは、ひとつのノードからの以下の全ての子孫のこと。

ツリーの中身を辿って移動していく操作のことを「トラバース」と呼ぶ。

ツリーの種類として、二分木・バイナリツリーがある。これは全ての枝の分岐が2つ以下のツリーのこと。探索などによく使われる。

二分木には、完全二分木（根から葉までがすべて等しい深さとなっている）や二分探索木（左の子は必ず親より小さく、右の子は必ず親より大きい）、ヒープ木などがある。

ヒープは完全二分木の一種で、「常に子が親より大きい」の場合と、「常に子が親より小さい」の場合のどちらかになるように整列される。最大値または最小値を求めるのに適している。

また、ツリーの応用例として、構文の意味と構造を解析する構文解析ツリーや、HTMLやXMLのドキュメント要素をツリー構造にしたDOMツリーなどがある。

2023.02.06編集

データ構造を用いたテクニックとして、たとえばテキスト内の単語の数を数えるなどといった問題を解決する場合、単語が既に出現した単語であるかどうか、全単語さかのぼって検索するのは時間がかかります。

このような時、二分木を用いて、ひとつの単語（たとえばopen）があった時、その単語よりもアルファベット順に前の単語（たとえばcat）があれば、それをopenのツリーの下の左の要素とし、アルファベット順に後の単語であれば、ツリーの下の右の要素とします。

このようにすることで、アルファベット順に前か後どちらかの単語がでてきたら、もう一方の木を検索することが必要なく、最短で一致する単語を検索できます。

このツリーを常に保持し、整理された状態を維持することで、とても効率的に単語を検索できます。

ほかにも、ポインタを上手く使うことで、データの構造が効率的になることがあります。

テキストを行単位で整理するのであれば、文字列（行）へのポインタの配列を作り、行を入れ替える際にはポインタだけを交換すればいいのです。

ポインタを使うもうひとつの例として、データ構造とは関係ありませんが、関数ポインタを使うことで、「場合によって別の関数を呼び出す」ことができ、これはソートのプログラムなどで、場合によって別のアルゴリズムでソートを行う場合などに有用です。

（詳しくはプログラミング言語C（K&R）が参考になります。）

実際のところ、C言語でツリーを作るのは意外と簡単です。

要するに、親要素へのポインタと、子要素へのポインタ（二分木であれば右と左の二つ）、そして要素が値を保持するためのデータ変数を、構造体として持てばいいだけだからです。

連結リスト、双方向リスト、グラフなども、同様の方法で作れます。単にポインタの参照の仕方が変わるだけです。

ただし、トラバース（木を辿っていく操作）を作るのは少し難易度が高めかもしれません。ひとつひとつ子を参照するのは簡単ですが、右と左のどちらに子があるのかを判断するのが難しいでしょう。

ハッシュテーブルも難易度が高めですが、配列の中にリストへのポインタを格納するようにすれば作れます。あるいは、キーのハッシュ値を配列の添え字にする方法でも作れます。

詳しい作り方は、以下の書籍に書かれているので、参照してください。

2024.08.15