后缀树的相关证明

——《高级数据结构》
1.后缀树中的节点个数至多为2m-1，其中m为字符串的长度。
证明：由后缀树的定义我们知道一共有m个叶节点，并且每个内部节点至少有2个孩子节点。假设总共有n个节点，则内部节点的个数为n-m。于是，我们可以得到如下的不等式：2（n-m）+1<=n;即n<=2m-1。因此，后缀树的压缩存储方式导致其节点个数也是与m呈线性关系。
2合理选取边标记的表示方式可以使得至多花费O（m）的空间复杂度来存储。
证明：如果我们直接按照定义，用字符串存边的话，那么存储可能要花费O（m的2次方）的空间复杂度，读者可以自行构建串“abcde”的后缀树然后加以检验。然而，由于子串是原串的连续一部分，所以保存好原串之后，每个标记只需要用一对数（u，v）来表示该子串对应的是原串的那一部分。所以，存储空间复杂度就与边数呈线性关系，即与点数呈线性关系，也就是O（m）。
3.如果新增一个对应标记为ap的节点v到当前树中，要么标记p对应节点已经在树中，要么接下来一次扩展会生成路径标记为p的节点。
证明：根据扩展规则，只有规则2会产生新的节点。也就是说路径ap对应的位置之后还有不同于当前添加的字符，假设为c。所以在下一次扩展，查找到串p的位置时，其后面也有字符c。如果p位置为边内部，那么会新建节点；如果是一个节点，那么肯定是内部节点。综上所述，命题成立。
4.一个新建节点在下一次扩展完之前或有一个后缀链。
证明：由命题1可知，新建一个节点之后，在下一次扩展的时候会找到或者创建其后缀链指向的节点，而每个阶段最后一次扩展不会产生新的节点（因为最后一次扩展只添加一个字符）。综上所述，我们完美的维护了后缀链，并且每次查询时后缀链总是存在的。
5.任意节点v的深度至多比其后缀链指向节点s(v)的深度大1.
对于节点v的所有祖先，它们都有自己的后缀链，由于v的祖先的路径标记为v的路径标记的前缀，所以v的祖先的后缀链指向节点的路径标记也是s(v)的路径标记的前缀。也就是说，v的祖先的后缀链指向节点s(v)的祖先，除非v的某个祖先没有后缀链。因此，不难发现，v的深度至多比s（v）的 深度大1.