こんにちは、まさとです。
今回は前回に引き続き
データ整理に欠かせない
ツリー構造について解説していきます。
また知らない言葉だ、、
ツリー構造は名前の通り木のような
ものなのでイメージしやすいはずですよ！
このツリー構造は実は今までの記事でも出てきていて
ファイルシステムなんかがこのツリー構造です。
興味があったら下の記事を見てみてください！
そもそもツリー(木)構造とは
名前の通り木のような構造になっています。
ツリー構造は階層構造を持つデータで広く用いられる他
データの探索や整列などの用途にも使われるデータ構造です。
ではどんなものなのかみていきましょう。
ツリー構造は上のように木に対応した
名前が付けられています。
また上図のような木構造のうち
節から伸びる枝が2本以下であるものを
2分木といいます。
二分技は左右の子に対するポインタを
データに付加することで
次のような配列構造として表すことができます。
また子を3つ以上持つことができるものを
「多分木」
と呼んだりもします。
完全2分木
葉以外の節が全て2つの子を持ち
根から葉までの深さが全て等しい
2分木のことを完全2分木と呼びます。
2分探索木
親に対する左部分木と右部分木の関係が
「左の子 < 親 < 右の子」
となる2分木を2分探索木と呼びます。
言葉で説明するとわかりにくいかと思いますので
図にして解説していきますね！
この2分探索木を使うことで
データの探索を簡単にすることができます。
最後に
いかがだったでしょうか。
今回の内容をまとめます。
- そもそもツリー構造とは
- 完全2分木とは
- 2分探索木とは
お疲れ様でした。
名前の通り木に似ていたね！
今までの配列やリストとかに比べても
比較的わかりやすかったかと思います！
他も全部わかりやすい名前に
してくれたらいいのにね
今回はツリー構造について
解説してきました。
どんな構造だったか
完全2分木とは
2分探索木とは
ということがわかるようにしておいてくださいね！
以上、まさとでした。
