データ構造の一種で、ある節(要素)が複数の子を持つことができ、その子が同じように複数の子を持つことができる構造のことです。
ある要素が複数の子を持つことができる一方で、1つの子が複数の親を持つことはできません(それができる場合は、グラフ構造である)。
それぞれの要素は節(ノード)と呼ばれます。一番上位にあたる節(つまり親がいない節)を根と呼び、一番下位にある節(つまり子がいない節)を葉と呼びます。また、根から一番遠い葉までの距離(通過する節の数)を使って、木構造の高さ(深さ)を表します。
木構造の解説が、アルゴリズムとデータ構造編【データ構造】第7章にあります。
節の配置の仕方に一定のルールを定めることで、さまざまなタイプの木構造を実現できます。節の探索・挿入・削除の実行効率(計算量)やメモリの消費量などに違いがうまれるため、目的に合わせた使い分けがなされます。
たとえば、1つの節に対する子の数を2つ以下に限定した二分木(バイナリツリー)があります。ここにさらに、「左の子の値<親の値<右の子の値」といった大小関係を持つルールを加えることで、探索効率の良い二分探索木が実現できます(二分探索の手法を使えるようになる)。
二分探索木の解説が、アルゴリズムとデータ構造編【データ構造】第8章にあります。
そのほか、どの葉も深さが可能なかぎり一定になるように構築していく平衡木や、親が子よりも大きいか等しい(あるいは小さいか等しい)というルールを徹底して構築するヒープなど、多種多様な亜種が存在します。
ヒープの解説が、アルゴリズムとデータ構造編【データ構造】第9章にあります。
Programming Place Plus のトップページへ
はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
X で ポスト/フォロー | LINE で送る | noteで書く |
RSS | 管理者情報 | プライバシーポリシー |