后缀平衡树简介

在我们学习认识后缀平衡树之前，一定要先了解什么是重量平衡树？所谓的重量平衡树是保证操作影响的最大子树大小是最坏的或均摊的或期望的O(logn)。

那什么是后缀平衡树？后缀平衡树是一种动态维护后缀排序的数据结构。具体而言,它支持在串S的开头添加/删除一个字符。

后缀之间的大小由字典序定义，后缀平衡树就是一个维护这些后缀顺序的平衡树，即字符串T的后缀平衡树是T所有后缀的有序集合。后缀平衡树上的一个节点相当于原字符串的一个后缀。特别地，后缀平衡树的中序遍历即为后缀数组。

后缀平衡树的优点：

（1）后缀平衡树的思路比较清晰，相比后缀自动机等后缀结构更好理解，会写平衡树就能写。

（2）后缀平衡树的复杂度不依赖于字符集的大小

（3）后缀平衡树支持在字符串开头删除一个字符

（4）如果使用支持可持久化的平衡树，那么后缀平衡树也能可持久化

后缀平衡树的应用：

（1）字符串匹配

（2）给定S和数个T,每次询问T在S中出现了几次。

（3）因为已经后缀排序,只要找到第一个严格小于T的最后一个后缀和严格大于T的第一个后缀即可。

（4）匹配时直接暴力。总复杂度为O((|S|+∑|T|)log|S|)。

关于后缀平衡树的一些知识点都已经罗列出来了，这些都是最需要掌握的基础知识，便于大家在做题中，及时作出正确的判断。