ファイルシステムやインターネットのドメイン名などは、いずれも木構造を用いて管理されています。
２分木というデータ構造
p５６４の図をみる。
木構造は以下の各要素で構成されています。
- 根（ルート）
- 枝（ブランチ）
- 節（節点、ノード）
- 葉（リーフ）
こっちにも図が書いてある。
節から伸びる枝が２本以下であるものを２分木という。
左右それぞれ左部分木、右部分木という。
完全２分木
葉以外の節が全て２つの子を持ち、根から葉までの深さが一様に等しい２分木のこと。
- 1つの
親に対して常に2つの子を持ち、枝分かれの最初から最後までに挟む要素の数が全部同じなツリー構造のこと
出典 https://wa3.i-3-i.info/word14924.html - 2分木の木構造のうち、頂点（根）から最底辺（葉）に至る
全てのノードが2つの子ノードを持ち、また、すべての葉が根から等しい距離にある構造のことである。
完全2分木は、左右のノードの数が等しい、木構造の深さをnとすればノードの数は2nとなる、あるいは、完全2分木を2分探索木として探索（検索）する場合、深さの数だけ探索可能であることがあらかじめ保証されている、といった特徴がある。
完全2分木においては、全ての葉は根から同じ深さ（レベル）にある。ただし例外的に、深さが1だけ異なる葉が存在し、その1だけ深い葉が木全体の左側に詰めてあるタイプの2分木も、完全2分木とみなされる。
出典 https://www.sophia-it.com/content/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%88%86%E6%9C%A8
２分探索木
親に対する左部分木と右部分木の関係が、「左の子＜親＜右の子」となる２分岐を２分探索木という。
子はその部分木に含む全ての節を指す。
「左の子＜親＜右の子」はデータ量を示す。
左の子より右の子の方がデータ量を多く持っている。
気づき
２分木探索木は少し難しい。
もう少し問題を解きたい。