木構造の解説

枝分かれしながら、データが増えていくデータ構造を木構造といいます。

木構造を図で示すと以下のようになります。

木は節点(node)とそれらを結んでいる枝(branch)によって構成されます。
節点はデータを表し、枝はその節点との関係にあたります。

分岐元の節点を親といい、枝をたどった先の節点を子といいます。

また、一番先頭の接点を根(root)と呼び、子を持たない接点のことを葉(reef)といいます。

深さと高さ

根からある節点に至るまでに通る枝の数をその頂点の深さ(depth)といい、
根から最も深い節点までの深さを木の高さ(height)>といいます。

図でいうと、木の高さは2になります。

2分木と2分探索木

木のうちで、各々の節点から出る枝の数が2本以下であるものを2分木といいます。

また、各々の節点のデータが比較可能で、
親と子の関係に規則がある(親と子に大小の関係あるなど)木のことを2分探索木(binary search tree)といいます。

この規則を元にし、アルゴリズムでは木が利用されます。