algorithm - 后缀树中的最大和最小边数

Question

后缀树中的最大和最小边数是多少？我知道最大值是 2m-1，但我不明白为什么会这样。

Answer 1

首先，关于最大边数：

如果您认为边有两种形式，那就很容易理解了：通向叶节点的边和通向内部节点的边。在下文中，我将假设构建后缀树的字符串的N长度是字符。

1. 关于通向树叶的边缘。每个后缀必须恰好有一个叶子，并且每个叶子只有一个入站边（并且没有出站边）。所以必须有N边缘通向叶子。

2. 关于通向内部节点的边。与叶节点一样，内部节点也只有一个入站边。因此，要确定可能有多少条边通向内部节点，只需确定可以有多少个内部节点即可。那么，内部节点的最大可能数量是多少？

   为此，重要的是要看到内部节点仅在分支点处插入到后缀树中，即内部节点的出站边数始终至少为 2（如果只有一个出站边，则内部节点不会' t 已首先构建）。但是每个出站边最终都必须通向一个叶节点（可能在经过进一步的内部节点之后）。换句话说，每个插入到树中的内部节点都会使叶子节点的总数至少增加 1。此外，即使一棵没有任何内部节点的树，也必须至少有一条边从根节点出来（除非树是空的）。因此，在非空树中，叶子的总数L必须是

   L >= I + 1
   

   其中I是内部节点的数量。相反，内部节点的数量是

   I <= L - 1 = N - 1
   

   回到原来的问题，通向内部节点的边数，正如我们所说的，与内部节点的数量相同，因此也受N - 1.

我们得出结论，边的总数是通向叶子 ( N) 的边数加上通向内部节点 ( <=N-1) 的边数，因此它的最大值为

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

quod erat 示范。

---

关于最小边数：这遵循相同的原则，即我们计算通向叶子的边数和通向内部节点的边数，然后将它们相加。

导致叶子的节点数始终为N，即N最大和最小可能。

然而，通向内部节点的节点数量可能为零。例如，当输入字符串没有重复元素时，例如abcdef，恰好有N边，每个边都从根直接到叶。没有分支点，没有内部节点。因此，通向内部节点的最小边数为 0。

总之，最小边数是N + 0 = N。