総合情報論 (環境情報学科1年次後期配当金曜日３限) 大城クラス

●木構造(tree structure)は，非常に重要なデータ構造である。

　グラフ(graph)とは“特定の事物間を関係を表す線で結んだもの”である。グラフでは，この事物にあたるものを一般に“頂点(node，ノード)”と呼ぶ。

　下図のように文字通り頂点間の関係が木のような構造を持っているグラフを木構造(tree)と呼ぶ(慣例的に通常の木とは上下逆さに図示す)。このような木の構造は，世の中に非常に多く見いだすことができる。例えば，多くのコンピューターが採用している“ディレクトリ構造”を持つファイルシステムなどが木の構造を持っている。

　木の頂点には大きく分けて，木の終端に位置する“葉(leaf)”と，そうでないものの2種類がある。前者を終端頂点(terminal node)，後者を非終端頂点(nonterminal node)と呼ぶ。下図では，○が終端頂点，●が非終端頂点です。
　一番上にある非終端頂点を“根(root，ルート)”と呼ぶ。木の構造で注目して欲しいのは，下図に示すように部分的な木(部分木)の集まりによって構成されていることである。下図の木のうち，青い枠で囲まれたところが部分木である。
　各頂点には，根からどれだけ何頂点はなれているかを表す「深さ」がある。下図では
　　　頂点c，e，f，jの深さは2
　　　頂点d，gの深さは3
である。根から最も離れている葉までの深さを，その木の高さと言う。下図の木の高さは3である。

　木について考えるとき，木の頂点間の関係を定義しておくと便利である。
　木の頂点間の関係で基本となるのは，“親と子”関係である。これは，下図のように家系図がちょうど木の構造になることから，木の頂点間の関係を親子関係になぞらえて表現しているわけである。線で直接結ばれている2つの頂点のうち，根に近い方(図では上の方)を“親(parent)”，葉に近い方を“子(child)”と呼ぶ。根は木構造の中で親を持たない唯一の頂点で，その他の頂点は必ず親を1個だけ持っている。その他，同じ親の子同士の関係を“兄弟”と呼ぶこともある。上図ではbはcの親，dはcの子，eとfはcの兄弟である。兄弟の間に何かしらの順序関係が存在する木を順序木(ordered tree)と呼ぶ。下図の家系図などは兄弟の間にまさに“生まれの早い遅い”という順序関係が存在するので，順序木の一種と言える。

　全ての頂点が最高でもn個の子しか持たない順序木をn分木と言う。そのため，全ての頂点が最高でも2個の子供しか持たない順序木は2分木(binary tree)と呼ばれる。前述したように，2分木は順序木であるので，その子が左側にあるか右側にあるかで意味が違ってくると言うことに注意。
　また，木の高さがkのとき，全ての葉の深さがk個またはk-1個となっている2分木は，完全2分木(complete binary tree)と呼ぶ。下図の木は葉の深さが3か2の2分木なので，完全2分木の一種と言える。