什么是一个后缀树边的最大值和最小值是多少？ 我知道最大为2m-1，但我不明白为什么会这样。
Answer 1:
首先，关于边缘的最大数量：
这是很容易理解，如果你认为边缘作为两种风格来：导致内部节点的边，导致叶节点和边缘。 在下文中，我将假设后缀树构造的字符串是N长度字符。
关于导致叶子边缘 。 必须有每个后缀正好一片叶子，每片叶子都有唯一一个入站边缘（没有出境边缘）。 所以必须有
N边缘导致的叶子。关于导致内部节点的边 。 像与叶节点，内部节点，也只有一个每个入站边缘。 因此，以确定有多少边缘导致内部节点存在都不可能，只要确定内部节点有多少都可以。 那么，什么是内部节点的最大可能是多少？
对于这种重要的是要看到，内节点只插入后缀树在分支点，即内节点总是至少2的出站边缘的数量（如果只有一个出站边缘，内节点止跌”吨已经首先被构建）。 但是，每一个出站边缘必须最终导致叶节点（通过进一步内部节点会后可能）。 换句话说，插入到树中的每个节点内增加叶子节点的由至少1总数此外，即使树没有内部节点中都必须具有至少一个边缘走出去根节点的（除非树是空）。 因此，在一个非空的树，叶子的总数
L必须L >= I + 1其中
I是内部节点的数目。 相反地，内节点的数量是I <= L - 1 = N - 1返回到原来的问题，边缘导致内部节点的数目是，在我们说，同样作为内的节点的数量，因此，它也受约束
N - 1。
我们的结论是边缘的总数为边缘，导致叶（数量N ）加上边缘导致内部节点（数<=N-1因此，它的最大被结合
N + (N-1) = 2N - 1
它被证明。
关于最低的边数：这遵循了同样的原则，即我们计算的边缘，导致叶片数和边缘导致内部节点的数量，然后把它们相加。
节点导致叶片的数量始终是N ，即N是最大和最小的可能。
节点导致内部节点的数目，然而，可以是零。 例如，当输入字符串没有重复的元素，如abcdef ，恰好有N边缘，每个从根直到叶。 没有分支点，没有内部节点。 因此边缘的通向内部节点的最小数为0。
最后，边缘的最小数量是N + 0 = N 。
文章来源: Maximum and minimum number of edges in a suffix tree
