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

Question

后缀树中的最大和最小节点数是多少？我该如何证明呢？

Answer 1

假设输入文本N长度为字符，包含根节点和所有叶子节点的最小节点数为 ，包含根节点和叶子节点N+1的最大节点数为2N-1。

最小证明：每个后缀必须至少有一个叶子节点，并且有N后缀。不需要任何内部节点，例如：如果文本是唯一符号序列abc$，则没有分支，因此在生成的后缀树中没有内部节点：

因此，最小值是总和节点中的N叶子、0内部节点和1根节点N+1。

最大证明：叶节点的数量永远不能大于，因为叶节点是后缀结束的地方，并且长度为 的字符串中N不能有多个不同的后缀。（事实上​​，你总是有完全不同的后缀，因此叶节点是完全不同的。）根节点总是完全是，所以问题是内部节点的最大数量是多少。每个内部节点都会在树中引入一个分支（因为后缀树的内部节点至少有 2 个子节点）。每个新分支最终必须导致至少一个额外的叶节点，因此如果您有内部节点，则必须至少有NNNN1KK+1叶节点，并且根节点的存在需要至少一个额外的叶（除非树是空的）。但是叶子节点的数量是有界的N，所以内部节点的最大数量是有界的N-2。这总共产生了N叶、1根和最多的N-2内部节点2N-1。

要看到这不仅是一个理论上的上限，而且一些后缀树实际上达到了这个最大值，请考虑一个只有一个重复字符的字符串：'aaa$'。确认其后缀树有 7 个节点（包括根和叶）：

总结：很明显，唯一真正的变量是内部节点的数量；1对于所有后缀树，根和叶的数量是恒定的N，而内部节点的数量在0和之间变化N-2。