LoginSignup
1
0

More than 1 year has passed since last update.

木構造とは

Posted at

木構造とは

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

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

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

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

木構造.png

木構造の例

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

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

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

木構造の探索方法

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

幅優先探索

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

深さ優先探索

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

まとめ

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

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0