algorithm - 接尾辞木のエッジの最大数と最小数

Question

接尾辞木のエッジの最大数と最小数はいくつですか？最大が2m-1であることは知っていますが、なぜそうなのかわかりません。

Answer 1

まず、エッジの最大数について：

エッジを2つのフレーバーであると考えると、非常に簡単に理解できます。リーフノードにつながるエッジと、内側ノードにつながるエッジです。以下では、接尾辞木が構築される文字列が文字長であると仮定しますN。

1. 葉につながるエッジについて。サフィックスごとに正確に1つのリーフが必要であり、すべてのリーフには1つのインバウンドエッジのみがあります（アウトバウンドエッジはありません）。Nしたがって、葉につながるエッジが必要です。

2. 内部ノードにつながるエッジについて。リーフノードと同様に、内部ノードにも、それぞれ1つのインバウンドエッジしかありません。したがって、内部ノードにつながるエッジがいくつあるかを判断するには、内部ノードがいくつあるかを判断するだけで十分です。では、内部ノードの可能な最大数はいくつですか？

   このため、内部ノードは分岐点で接尾辞木にのみ挿入されることを確認することが重要です。つまり、内部ノードのアウトバウンドエッジの数は常に少なくとも2です（アウトバウンドエッジが1つしかない場合、内部ノードは挿入されません。そもそも構築されています）。ただし、すべてのアウトバウンドエッジは、最終的にリーフノードにつながる必要があります（おそらく、さらに内部ノードを通過した後）。言い換えると、ツリーに挿入されたすべての内部ノードは、リーフノードの総数を少なくとも1つ増やします。さらに、内部ノードがまったくないツリーでも、ルートノードから少なくとも1つのエッジが出ている必要があります（ツリーが空）。したがって、空でないツリーでは、葉の総数は次のようにLなります。

   L >= I + 1
   

   ここIで、は内部ノードの数です。逆に、内部ノードの数は

   I <= L - 1 = N - 1
   

   元の質問に戻ると、内部ノードにつながるエッジの数は、前述したように、内部ノードの数と同じであるため、によっても制限されN - 1ます。

エッジの総数は、葉につながるエッジNの数（）と内部ノードにつながるエッジの数（）であると結論付け<=N-1ます。したがって、その最大値は次のように制限されます。

N + (N-1) = 2N - 1

quoderatdemonstrandum。

---

エッジの最小数について：これは同じ原則に従います。つまり、葉につながるエッジの数と内部ノードにつながるエッジの数を計算し、それらを合計します。

葉につながるノードの数は常にNです。つまりN、可能な限り最大および最小です。

ただし、内部ノードにつながるノードの数はゼロの場合があります。たとえば、入力文字列に、などの繰り返し要素がない場合、それぞれがルートからリーフまで、abcdef正確にエッジがあります。N分岐点も内部ノードもありません。したがって、内部ノードにつながるエッジの最小数は0です。

結論として、エッジの最小数はですN + 0 = N。