先頭へ戻る

木構造 | Programming Place Plus 用語集

Programming Place Plus トップページ用語集

先頭へ戻る

名称

解説

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

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

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

木構造の解説が、アルゴリズムとデータ構造編【データ構造】第7章にあります。

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

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

二分探索木の解説が、アルゴリズムとデータ構造編【データ構造】第8章にあります。

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

ヒープの解説が、アルゴリズムとデータ構造編【データ構造】第9章にあります。


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー