根付き木
木構造とは節点(node) と、節点同士を結ぶ辺(edge) で表されるデータ構造です。 図1のように、木の節点は円、辺は線で表されます。
図1 木の例
図2のように、根(root) と呼ばれる他と区別された１つの節点を持つ木を根付き木(rooted tree)と呼びます。
図2 根付き木の節点の種類
根付き木の節点には親子関係があります。根付き木$T$の根$r$から節点$x$に至る経路上の最後の辺が節点$p$と節点$x$を繋ぐとき、$p$を$x$の親(parent)、$x$ を $p$の子(child)と呼びます。
同一の親を持つ節点を兄弟(sibling)と呼びます。 例えば、図2の木では、節点2の親は0（根）、兄弟は1と3になります。
図2の木のように、根は親を持たない唯一の節点です。子を持たない節点は外部節点(external node) または葉(leaf )と呼ばれます。葉でない節点を内部接点(internal node)と呼びます。
根付き木$T$の節点$x$の子の数を$x$の次数(degree)と呼びます。例えば図2の木では、節点2の次数は3で、節点2は節点6、7、8 の３つの子を持ちます。子を持たない場合、次数は0 になります。
根$r$ から節点$x$ までの経路の長さを$x$ の深さ(depth) と呼びます。また、節点$x$ から葉までの経路の長さの最大値を節点$x$ の高さ(height) と呼びます。根の高さが最も高くなり、それを木の高さと呼びます。例えば、図の節点8 の深さと高さはそれぞれ2、1 で、木の高さは3 です。
Reference
|
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ)AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。 |