jog*_*pan 13
假设N长度为字符的输入文本,包括根节点和所有叶节点的最小节点数是,包括根和叶N+1的最大节点数是2N-1.
最小证明:每个后缀必须至少有一个叶子节点,并且有N后缀.不需要任何内部节点,例如:如果文本是一系列唯一符号,abc$则没有分支,因此在结果后缀树中没有内部节点:
因此,总和节点中的最小值是N叶子,0内部节点和1根节点N+1.
最大证明:叶子节点的数量永远不会大于N,因为叶子节点是后缀结束的地方,并且N在长度的字符串中不能有多个不同的后缀N.(事实上,你总是有完全N不同的后缀,因此N叶节点恰好)的根节点是总是精确1的,所以问题是什么是内部节点的最大数目.每个内部节点在树中引入一个分支(因为后缀树的内部节点至少有2个子节点).每个新分支最终必须至少导致一个额外的叶子节点,所以如果你有K内部节点,那么至少必须有K+1叶节点和根节点的存在需要至少一个额外的叶子(除非树是空的).但叶子节点的数量是有界限的N,因此内部节点的最大数量受限N-2.这样可以精确地生成N叶子,1根和最大N-2内部节点2N-1.
要看到这不仅是一个理论上限,而且一些后缀树实际上达到了这个最大值,可以考虑一个只有一个重复字符的字符串:'aaa $'.确认此后缀树有7个节点(包括root和leaves):
总结:很明显,唯一真正的变量是内部节点的数量; 根和叶的数量是恒定的1,并N为所有后缀树,而内部节点的数量之间变化0和N-2.