木構造【tree structure】ツリー構造

概要

木構造（tree structure）とは、データ構造の一つで、一つの要素(ノード)が複数の子要素を持ち、子要素が複数の孫要素を持ち、という具合に階層が深くなるほど枝分かれしていく構造のこと。木が幹から枝、枝から葉に分岐していく様子になぞらえた名称である。

木構造を構成する要素を「ノード」（node：節）と呼び、ノード間の繋がりを「エッジ」（edge）という。繋がったノード同士は親子関係を持ち、親を持たない始祖のノードを「根ノード」（root node：ルートノード）という。根ノードに近い側が「親ノード」（parent node）で、遠い側が「子ノード」（child node）である。

親は複数の子を持つことができるが、子はただ一つの親を持つ。親が共通の子ノード同士は「兄弟ノード」（sibling nodes）という。一つ以上の子を持つノード（いずれのノードの親であるノード）を「枝ノード」（branch node）「内部ノード」（internal node/inner node）「中間ノード」（intermediate node）「非終端ノード」（non-terminal node）などという。

子の無い末端のノードは「葉ノード」（leaf node：リーフノード）「終端ノード」（terminal node）「外部ノード」（external node/outer node）という。あるノードより根ノード側にあるノード群を「先祖ノード」（ancestor nodes）、葉ノード側にあるノード群を「子孫ノード」（descendant nodes）と呼ぶことがある。

根を基準に、あるノードまでのエッジの数を「深さ」（depth/level）という。根ノードの深さは0となる。また、あるノードを基準に、その子孫の葉ノードのうち最も深いものまでのエッジ数を「高さ」（height）という。根ノードの高さは最も深い葉ノードの深さに等しく、これが木構造全体の高さとなる。同じ深さにあるノードの数を「幅」（width）という。

現実の木は地中の根から上に向かって幹や枝を伸ばし、葉が上方にあるが、木構造を図示する際にはこれとは逆に、根ノードを図の最上部に描き、一段下に子ノード群、その下に孫ノード群、といった具合に下向きに広がるように描くことが多い。家系図の描き方と同じである。

木構造は子の数についての制約によって分類することが多い。例えば、子の数が2に制限されている木を「二分木」（二進木、バイナリツリー）と呼び、3つ以上の子を持つことができるものを「多分木」という。そのうち、子の数がN個（Nは3以上の自然数）に制限されている木を「N分木」（N進木）という。

他の性質による分類も用いられる。例えば、葉の深さがなるべく等しくなるように構築された木を「平衡木」（バランス木）と呼ぶ。二分木かつ平衡木であれば「平衡二分木」で、多分木の平衡木にはB木などがある。他にも用途によって様々な木構造が考案され、様々な場面に応用されている。

木の中で特定のノードおよびその子孫を「部分木」（subtree：サブツリー）という。複数の木からなる集合を「森」（forest：フォレスト）ということがある。

多分木 (multi-branch tree/multi-way tree)

木構造のうち、親ノードが3つ以上の子ノードを持つことができるもの多分木たぶんぎという。二分木ではノードに格納される値は一つだが、多分木ではノードに複数の値を格納し、子ノードの参照と対応付けた構造にする場合がある（B木など）。子の数に制約がなくいくつでもよい場合と、子が特定の数以下でなければならない「N分木」が含まれる。

N分木 (N進木/N-ary tree/N-way tree)

木構造のうち、親ノードが持つ子ノードの数がN個に制限されているものをN分木エヌぶんぎあるいはN進木エヌしんぎという。

Nは2以上の自然数を表し、Nが2であるような（2個以下の子しか持てない）ものは「二分木」と呼ばれるため、通常はNが3以上の木を総称してN分木という。例えば、子が必ず3つ以下のものは「三分木」、4つ以下のものは「四分木」である。“N”の代わりに“K”や“M”などの文字を用いて表記されることもあるが、意味は同じである。

N分木のうち、子を持つノードの子の数がすべてN個であるようなものを「全N分木」（full N-ary tree）、全N分木のうち、すべての葉の深さが揃っているものを「完全N分木」（perfect N-ary tree）という。また、最下層を除いてすべての階層がノードで満たされ、最下層の葉ノードが可能な限り左に寄せられているような木を “complete N-ary tree” と呼び、これを完全N分木とすることもある。

(2022.5.31更新)