木の紹介

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

ツリーとそのプロパティ

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

Example −以下はツリーの例です−

木の中心とバイセンター

木の中心は、離心率が最小の頂点です。ツリー$ G $内の頂点$ X $の離心率は、頂点$ X $とツリーの他の頂点との間の最大距離です。最大離心率は木の直径です。ツリーに中心が1つしかない場合は中央ツリーと呼ばれ、中心が複数ある場合はバイセントラルツリーと呼ばれます。すべてのツリーは中央または双方向のいずれかです。

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

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

Step 2−エッジで結合された単一の頂点または2つの頂点が残るまで、手順1を繰り返します。単一の頂点が残っている場合、それはツリーの中心であり、エッジで結合された2つの頂点が残っている場合、それはツリーの二重中心です。

Problem 1

次の木の中心/双中心を見つける-

Solution

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

ここでも、次数1のすべての頂点を削除し、それらの入射エッジも削除して、次のツリーを取得します-

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

Problem 2

次の木の中心/双中心を見つける-

Solution

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

ここでも、次数1のすべての頂点を削除し、それらの入射エッジも削除して、次のツリーを取得します-

最後に、2つの頂点「c」と「d」が残っているため、アルゴリズムを停止します。エッジで結合された2つの頂点が残っているため、このツリーには2つの中心の「cd」があり、ツリーは2つの中心になっています。

ラベル付きツリー

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

例

ラベルのない木

Definition−ラベルのないツリーとは、頂点に番号が割り当てられていないツリーです。n個の頂点のラベル付きツリーの数は$ \ frac {（2n）！} {（n + 1）！n！} $（n^番目のカタラン数）

例

根付いた木

ルートツリー$ 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 $以下です。 $ 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)

二分探索木の複雑さ

	平均的なケース	最悪の場合
スペースの複雑さ	オン）	オン）
検索の複雑さ	O（log n）	オン）
挿入の複雑さ	O（log n）	オン）
削除の複雑さ	O（log n）	オン）