木構造 | Programming Place Plus　用語集

名称

データ構造の一種で、ある節（要素）が複数の子を持つことができ、その子が同じように複数の子を持つことができる構造のことです。

ある要素が複数の子を持つことができる一方で、１つの子が複数の親を持つことはできません（それができる場合は、グラフ構造である）。

それぞれの要素は節（ノード）と呼ばれます。一番上位にあたる節（つまり親がいない節）を根と呼び、一番下位にある節（つまり子がいない節）を葉と呼びます。また、根から一番遠い葉までの距離（通過する節の数）を使って、木構造の高さ（深さ）を表します。

節の配置の仕方に一定のルールを定めることで、さまざまなタイプの木構造を実現できます。節の探索・挿入・削除の実行効率（計算量）やメモリの消費量などに違いがうまれるため、目的に合わせた使い分けがなされます。

たとえば、１つの節に対する子の数を２つ以下に限定した二分木（バイナリツリー）があります。ここにさらに、「左の子の値＜親の値＜右の子の値」といった大小関係を持つルールを加えることで、探索効率の良い二分探索木が実現できます（二分探索の手法を使えるようになる）。

そのほか、どの葉も深さが可能なかぎり一定になるように構築していく平衡木や、親が子よりも大きいか等しい（あるいは小さいか等しい）というルールを徹底して構築するヒープなど、多種多様な亜種が存在します。