木構造とは

木構造とは、階層をもったデータ構造です。
1つのノードが複数の子要素をもち、1つの子要素が複数の孫要素を持つような形で階層が深くなるにつれ、枝分かれしていきます。
図を逆にした時に木の様子に似ているためこのように呼ばれているみたいです。

1つ1つの要素はノード(Node)と呼ばれ、ノード同士は親子関係を持ちます。
親がないノードは根(root)と呼ばれ、子がないノードは葉(reef)と呼ばれています。

イラストは2つの子を持っていますが、3個以上の子を持つような多分木などもありますが、代表的なものは子の数が2個に制限されている二分木です。

ちなみに、木構造はある子要素への道は1つしかありません。
しかし、ノードへの道が2通り以上ある場合は、木構造ではなくグラフ構造と呼ばれます。

木構造の例

木構造は、大量の情報と関連性を扱う場合に有効です。
具体的な例を挙げるとディレクトリの構成も木構造になっています。
rootがあり、子にhomeやetcやuserがあります。さらにhomeの子にも複数のディレクトリがあります。
ファイルは葉にあたり、ディレクトリはNodeになります。

DNS(Domain Name System)なども木構造です。
DNSはたくさんのコンピュータの名前を含む名前空間を階層的にドメインに分割して管理しています。

wrsdu1715.co.jpという名前の場合、jp配下にcoという子要素がありcoの子要素にwrsdu1715があるといったイメージです。

木構造の探索方法

木構造で表されたデータを処理するには、ノードを順番にたどる必要があります。
探索する方法は、幅優先探索と深さ優先探索があります。

幅優先探索

根から開始して、同じ階層にあるNodeを探索していく方法です。
同じ階層にあるノードをrootに近い方から探索するため、最短経路や最小手数などを求める時などに有効です。

深さ優先探索

幅優先は階層ごとでしたが、深さ優先は縦方向にNodeを探索していく方法です。
rootから深さを優先して探索して、遷移を繰り返すことですべての状態を列挙できます。
例えばスタートからゴールまでたどり着けるかなどの問題を解くことができます。

まとめ

木構造にはさまざまな種類がありますがよく使われるのは二分木だと思います。
あまり意識してないですが日常で使うところでよく使われているので木構造の特徴は理解できてよかったです。
アルゴリズムでも使われていたり二分探索木などもよく使われるでしょう。
簡単でしたがざっと木構造とは説明させていただきました。