algorithm - 順序付けされたツリーと順序付けられていない（ルート化された）ツリーの違い

Question

私はRobertSedwickによるアルゴリズムを読んでいます。この本のいくつかの定義を以下に示します。

ツリー（順序付けられたツリーでもあります）は、一連の互いに素なツリーに接続されたノード（ルートと呼ばれます）です。このようなシーケンスはフォレストと呼ばれます。

ルートツリー（または順序付けされていないツリー）は、ルートツリーのマルチセットに接続されたノード（ルートと呼ばれる）です。（このような多重集合は、順序付けられていないフォレストと呼ばれます。

上記のテキストに関する私の質問は

1. 私は上記の定義を理解するのに苦労しています。誰でも例を挙げて説明してもらえますか？
2. ばらばらな木とは、作者とはどういう意味ですか？
3. 作成者は、多重集合の根付きツリーとはどういう意味ですか？

お時間を割いていただきありがとうございます

Answer 1

1. この定義によるツリーは、多かれ少なかれ、ツリーによって通常理解されるものです。つまり、(サブ) ツリーの順序付けられたシーケンスに接続されたノードです。これは再帰的な定義です。シーケンスが空の場合、ノードはリーフと呼ばれ、そうでない場合、シーケンス内の各ツリーは「(サブ)ツリーの順序付けられたシーケンスに接続されたノード」でもあります。
2. 作成者が不整合とは、サブツリーに共通のノードがないことを意味します。
3. この定義は、根付きツリーのサブツリーが特定の順序ではなく、繰り返される可能性があることを意味します。マルチセットは、倍数を許可するセットのようなものです。

順序付けられたツリー (最初の定義の「ツリー」) には特定の順序でサブツリーがあり、サブツリーは互いに素でなければならないため、サブツリー シーケンスに同じツリーを 2 回含めることはできません。ルート ツリーにはこれらの制限はありません。この定義により、ルートは循環に似た構造でサブツリーを 2 回持つ場合があります。

この定義が理にかなっているのかどうか、またはその理由を確認するためのセドウィックの本はありません。より一般的な定義または根付きツリーでは、マルチセットではなく、サブツリーに通常のセットを使用します。おそらくその意図は、ノードとその子の間の複数のリンクを許可する一方で、兄弟と従兄弟の間のリンクなど、他の種類のサイクルを許可しないことです。