木の紹介

ツリー*は、個々の要素またはノード間の階層関係を表す離散構造です。親が2つ以下の子を持つツリーは、バイナリツリーと呼ばれます。

ツリーとそのプロパティ

定義-ツリーは、接続された非循環無向グラフです。 $ G $の頂点のすべてのペア間に一意のパスがあります。 N個の頂点を持つツリーには、$（N-1）$個のエッジが含まれます。 0度の頂点は、ツリーのルートと呼ばれます。 1次の頂点はツリーの葉ノードと呼ばれ、内部ノードの次数は少なくとも2です。

例-以下はツリーの例です-

ツリー

木の中心とバイセンター

木の中心は、最小の離心率を持つ頂点です。ツリー$ G $の頂点$ X $の離心率は、頂点$ X $とツリーの他の頂点との間の最大距離です。最大の離心率は木の直径です。ツリーの中心が1つだけの場合、それは中央ツリーと呼ばれ、ツリーの中心が1つだけの場合、バイセントラルツリーと呼ばれます。すべてのツリーは、中央または双方向です。

木の中心と双心を見つけるアルゴリズム

ステップ1 *-指定されたツリーから次数1のすべての頂点を削除し、入射エッジも削除します。

ステップ2 *-単一の頂点またはエッジで結合された2つの頂点のいずれかが残るまで、ステップ1を繰り返します。単一の頂点が残っている場合、それはツリーの中心であり、エッジで結合された2つの頂点が残っている場合、それはツリーのバイセンターです。

問題1 *

次のツリーの中心/バイセンターを見つけます-

ツリー1

溶液

最初に、我々は次数1のすべての頂点を削除し、またそれらの入射エッジを削除し、次のツリーを取得します-

Tree1ソリューション

再び、我々は次数1のすべての頂点を削除し、またそれらの入射エッジを削除し、次のツリーを取得します-

頂点を削除するツリー1のソリューション

最後に、単一の頂点「c」を得て、アルゴリズムを停止します。単一の頂点があるため、このツリーには1つの中心「c」があり、ツリーは中心ツリーです。

問題2 *

次のツリーの中心/バイセンターを見つけます-

tree2

溶液

最初に、我々は次数1のすべての頂点を削除し、またそれらの入射エッジを削除し、次のツリーを取得します-

ツリー2ソリューション

再び、我々は次数1のすべての頂点を削除し、またそれらの入射エッジを削除し、次のツリーを取得します-

頂点を削除するツリー2ソリューション

最後に、2つの頂点「c」と「d」が残ったため、アルゴリズムを停止します。エッジで結合された2つの頂点が残っているため、このツリーはバイセンター「cd」を持ち、ツリーはバイセントラルです。

ラベル付きの木

定義-ラベル付きツリーは、頂点に1〜nの一意の番号が割り当てられているツリーです。一般式を推測するために、nの小さな値に対してそのようなツリーを手で数えることができます。 n個の頂点のラベル付きツリーの数は$ n ^ \ {n-2} $です。グラフが同型であり、2つのツリーの対応するポイントが同じラベルを持つ場合、2つのラベル付きツリーは同型です。

例

2つの頂点を持つラベル付きツリー 3つの頂点を持つ3つのラベル付きツリー

ラベルなしの木

定義-ラベルのないツリーは、頂点に番号が割り当てられていないツリーです。 n個の頂点のラベル付きツリーの数は$ \ frac \ {（2n）！} \ {（n + 1）！n！ } $（n ^ th ^カタロニア語番号）

例

ラベルのないツリー 3つの頂点のあるラベルのないツリー image:/discrete_mathematics/images/unlabeled_tree_4_vertex.jpg with unlabeled_tree_4_vertex.jpg頂点]

根付きツリー

根付きツリー$ G $は、ツリーのルートと呼ばれる特別なノードを持つ接続された非循環グラフであり、すべてのエッジはルートから直接または間接的に発生します。順序付けされたルート付きツリーは、各内部頂点の子が順序付けられているルート付きツリーです。根付きツリーのすべての内部頂点がm個以下の子を持つ場合、m-aryツリーと呼ばれます。根付きツリーのすべての内部頂点に正確にm個の子がある場合、完全なm-aryツリーと呼ばれます。 $ m = 2 $の場合、ルートツリーはバイナリツリーと呼ばれます。

ルートツリー

二分探索ツリー

二分探索木は、次のプロパティを満たす二分木です-

頂点$ Vの左サブツリーの$ X $、Value（X）\ le Value（V）$
頂点$ Vの右サブツリーの$ Y $、Value（Y）\ ge Value（V）$

したがって、内部ノード$ V $の左サブツリーのすべての頂点の値は$ V $以下であり、内部ノード$ V $の右サブツリーのすべての頂点の値は$ V $以上です。ルートノードから最も深いノードへのリンクの数は、バイナリ検索ツリーの高さです。

例

バイナリ検索ツリー

BSTでキーを検索するアルゴリズム

BST_Search(x, k)
if ( x = NIL or k = Value[x] )
   return x;
if ( k < Value[x])
   return BST_Search (left[x], k);
else
   return BST_Search (right[x], k)

バイナリ検索ツリーの複雑さ

	Average Case	Worst case
Space Complexity	O(n)	O(n)
Search Complexity	O(log n)	O(n)
Insertion Complexity	O(log n)	O(n)
Deletion Complexity	O(log n)	O(n)

Discrete-mathematics-introduction-to-trees

目次