后缀平衡树

What · 是什么

后缀平衡树（Suffix Balanced Tree）是用平衡二叉搜索树维护字符串所有后缀的字典序有序集合的数据结构：树中每个节点对应一个后缀，中序遍历即后缀数组。特点：支持在字符串**开头**动态插入/删除字符（前端动态维护），复杂度 O(log n) 每次插入/删除；不依赖字符集大小；若用可持久化平衡树则可持久化。构造方法有四档：①暴力比较后缀大小，单次 O(n) 比较，总 O(n² log n)；②利用 cS 与 S 的关系：先比较首字符，若相同则比较去掉首字符后的两个串（它们已在树中），用平衡树求排名 O(log n)，单次插入 O(log² n)；③给每个节点维护实数区间 tag（根对应 (0,1)，左子树 (l,tag)，右子树 (tag,r)），O(1) 比较两个节点后缀大小，总 O(n log n)；④先建后缀数组再建平衡树。经典应用：维护字符串尾部插入/删除+询问串出现次数（用反串后缀平衡树）。

Why · 为什么

How · 实现

伪代码

# 做法3: 实数 tag 后缀平衡树 (插入 cS)
def insert(node cS):
    在 BST 中按 tag 二分找到位置
    若首字符不同 => 直接比出大小
    若相同 => 比较 tag[S] (S 已在树中)
    创建节点, 分配 tag = 父区间中点
    (树高失衡时按需重构, 如替罪羊)

# 中序遍历 => 后缀数组
# 头删: 直接删对应节点
# 问串 t 出现次数: 排名(t) - 排名(t的前驱) (用后缀平衡树)

Python 实现

import random


class ScapegoatNode:
    __slots__ = ("ch", "tag", "val", "k")

    def __init__(self, val, tag, k):
        self.ch = [None, None]   # 0=left, 1=right
        self.tag = tag           # 实数区间中点 (做法3: O(1) 比较)
        self.val = val           # 当前后缀字符串 (存储, 简化)
        self.k = k               # 插入序号 => 对应原串位置


class SuffixBST:
    """做法3 (tag) 后缀平衡树, 用替罪羊(重构)保持平衡.
    演示: 只支持在开头插入字符 (动态维护后缀集合), 中序遍历=后缀数组.
    注意: 实际 O(1) 比较应直接比较 tag; 此处存储字符串仅用于可读性.
    """

    def __init__(self):
        self.root = None
        self.s = ""
        self.k = 0

    def _insert(self, node, val, lo, hi):
        if node is None:
            return ScapegoatNode(val, (lo + hi) / 2, self.k)
        if val < node.val:
            node.ch[0] = self._insert(node.ch[0], val, lo, node.tag)
        else:
            node.ch[1] = self._insert(node.ch[1], val, node.tag, hi)
        return self._rebalance(node)

    def _rebalance(self, node):
        def size(x):
            if x is None:
                return 0
            return 1 + size(x.ch[0]) + size(x.ch[1])
        l, r = size(node.ch[0]), size(node.ch[1])
        if max(l, r) > 0.8 * (l + r + 1):
            return self._rebuild(node)
        return node

    def _rebuild(self, node):
        def collect(x, out):
            if x is None:
                return
            collect(x.ch[0], out)
            out.append(x)
            collect(x.ch[1], out)
        arr = []
        collect(node, arr)
        return self._build(arr, 0.0, 1.0)

    def _build(self, arr, lo, hi):
        if not arr:
            return None
        mid = len(arr) // 2
        nd = arr[mid]
        nd.tag = (lo + hi) / 2
        nd.ch[0] = self._build(arr[:mid], lo, nd.tag)
        nd.ch[1] = self._build(arr[mid + 1:], nd.tag, hi)
        return nd

    def insert_char(self, c):
        """在字符串开头插入字符 c (新增一个后缀)."""
        self.s = c + self.s
        self.root = self._insert(self.root, self.s, 0.0, 1.0)
        self.k += 1

    def inorder(self):
        """中序遍历 => 后缀数组 (按字典序的后缀起始位置列表)."""
        out = []

        def dfs(x):
            if x is None:
                return
            dfs(x.ch[0])
            out.append(x)
            dfs(x.ch[1])
        dfs(self.root)
        return [(len(self.s) - 1 - nd.k) for nd in out]


if __name__ == "__main__":
    random.seed(3)
    for _ in range(200):
        n = random.randrange(1, 30)
        t = ''.join(random.choice('abc') for _ in range(n))
        sb = SuffixBST()
        for c in t:
            sb.insert_char(c)
        order = sb.inorder()
        s = sb.s
        expected = sorted(range(len(s)), key=lambda i: s[i:])
        assert order == expected, (s, order, expected)

    sb = SuffixBST()
    for c in "abab":   # 头插 => 最终串 "baba"
        sb.insert_char(c)
    s = sb.s
    order = sb.inorder()
    assert order == sorted(range(len(s)), key=lambda i: s[i:]), (s, order)

    print("suffix-bst tests passed")

易错点

• tag 浮点精度耗尽导致比较错误，用大区间/定点数
• 只支持头部增删；尾部增删需转反串
• 插入用字符串暴力比较（做法1）会退化 O(n²)，要用 tag/排名优化
• 树失衡后 tag 区间会耗尽，需重构重新分配
• 与后缀数组互为中序遍历，别把方向搞反

例题

信源

• OI Wiki✓ https://oi-wiki.org/string/suffix-bst/
• Wikipedia✓ https://en.wikipedia.org/wiki/Suffix_array