提醒

此文章用对话形式。

后缀平衡树（Size Balanced Tree）超详细对话讲解

一、开场：后缀平衡树到底是什么？

学生：老师，我听说过平衡树，AVL、红黑树、替罪羊树……但后缀平衡树是什么？它和“后缀”有关吗？和后缀数组、后缀自动机有关系吗？

老师：你这个问题非常关键。
后缀平衡树 = Size Balanced Tree，简称 SBT。

它不是处理字符串后缀的数据结构！
它就是一种靠子树大小来维持平衡的二叉搜索树，名字里的“后缀”其实是早期翻译问题，真正核心是：

Size（子树大小） Balanced（平衡） Tree

所以你可以直接理解成：
靠“子树大小”来自动保持平衡的二叉搜索树。

学生：哦！原来和字符串后缀没关系啊，那我放心了。那它为什么要叫后缀平衡树？

老师：历史原因。最早 Size Balanced Tree 被翻译成“后缀平衡树”，后来大家叫顺口了，就一直这么叫。
你只要记住：

• SBT = 基于 size 的平衡树
• 不处理后缀
• 是一种超级快、好写、常数极小的平衡树

---

二、SBT 核心思想：一句话讲完

学生：那它怎么平衡？和 AVL、红黑树区别在哪？

老师：
所有平衡树，本质都是：
不让某一侧树太高，保证高度始终是 O(log n)

SBT 的平衡规则超级简单：

对每个节点：
左孩子的大小 ≤ 右兄弟的大小
右孩子的大小 ≤ 左兄弟的大小

用符号写就是：

• size[left[x]] ≤ size[right[right[x]]]
• size[right[x]] ≤ size[left[left[x]]]

只要不满足，就旋转。

学生：就这么简单？

老师：对！SBT 是所有平衡树里规则最少、代码最短、速度最快的之一。

---

三、SBT 节点结构（C++ 版）

学生：那节点怎么定义？

老师：非常干净：

struct Node {
    int ch[2];   // 0左 1右
    int key;     // 权值
    int size;    // 子树大小
} tr[N];
int root, tot;

就这四个东西。

---

四、SBT 最核心操作：维护 size & 旋转

学生：旋转和普通 BST 一样吗？

老师：完全一样，左旋、右旋。
只是 SBT 旋转后必须立刻更新 size。

void pushup(int x) {
    tr[x].size = tr[tr[x].ch[0]].size + tr[tr[x].ch[1]].size + 1;
}

旋转我就不贴长篇了，你只要记住：
旋转 = 结构调整 + pushup

---

五、SBT 真正灵魂：maintain 维护

学生：老师，SBT 最关键的是什么？

老师：就是这个 maintain 函数。
它负责检查当前节点是否平衡，不平衡就旋转修正。

void maintain(int &x) {
    if (x == 0) return;

    // 左孩子 > 右兄弟
    if (tr[tr[tr[x].ch[0]].ch[0]].size > tr[tr[x].ch[1]].size)
        right_rotate(x);
    // 右孩子 > 左兄弟
    else if (tr[tr[tr[x].ch[0]].ch[1]].size > tr[tr[x].ch[1]].size)
        left_rotate(tr[x].ch[0]), right_rotate(x);
    // 对称右边
    else if (tr[tr[tr[x].ch[1]].ch[1]].size > tr[tr[x].ch[0]].size)
        left_rotate(x);
    else if (tr[tr[tr[x].ch[1]].ch[0]].size > tr[tr[x].ch[0]].size)
        right_rotate(tr[x].ch[1]), left_rotate(x);
    else return;

    // 修正完继续维护
    maintain(tr[x].ch[0]);
    maintain(tr[x].ch[1]);
    maintain(x);
}

学生：这四行判断就是全部平衡规则？

老师：对！
这就是 SBT 的全部精华。

---

六、插入：SBT 最简单的操作

学生：插入怎么写？

老师：普通 BST 插入，最后加一句 maintain。

void insert(int &x, int key) {
    if (!x) {
        x = ++tot;
        tr[x].key = key;
        tr[x].size = 1;
        return;
    }
    if (key < tr[x].key) insert(tr[x].ch[0], key);
    else insert(tr[x].ch[1], key);
    pushup(x);
    maintain(x);
}

学生：就这？

老师：就这。

---

七、删除：SBT 也超级短

学生：删除会不会很难？

老师：和普通 BST 一样，找到节点删：

• 叶子直接删
• 一个孩子替换
• 两个孩子找前驱/后继替换
  最后 pushup + maintain

void remove(int &x, int key) {
    if (!x) return;
    if (tr[x].key == key) {
        if (!tr[x].ch[0] || !tr[x].ch[1]) {
            x = tr[x].ch[0] | tr[x].ch[1];
        } else {
            int y = tr[x].ch[1];
            while (tr[y].ch[0]) y = tr[y].ch[0];
            tr[x].key = tr[y].key;
            remove(tr[x].ch[1], tr[y].key);
        }
    } else if (key < tr[x].key) {
        remove(tr[x].ch[0], key);
    } else {
        remove(tr[x].ch[1], key);
    }
    if (x) pushup(x), maintain(x);
}

学生：真的比红黑树简单太多！

---

八、SBT 能干嘛？（所有平衡树能干的它都行）

学生：SBT 可以实现哪些功能？

老师：全部：

• 插入 / 删除
• 查第 k 小
• 查某个数的排名
• 查前驱 / 后继
• 区间第 k 小（配合权值线段树）
• 可持久化平衡树（SBT 也能持久化）

它是竞赛里最实用的平衡树之一。

---

九、SBT 优点总结（超级重要）

学生：老师，最后帮我总结一下 SBT 好在哪？

老师：

1. 代码极短
   比 AVL 短，比红黑树短太多。

2. 常数极小
   速度经常比替罪羊树快。

3. 逻辑清晰
   只有一个 maintain，四条规则。

4. 不会退化
   严格保证树高 O(log n)。

5. 万能
   能做所有 BST 功能。

---

十、你最关心的一句话总结

学生：我现在彻底懂了！

老师：
最后给你一句最精髓的总结：

后缀平衡树（SBT）= 依靠子树大小维持平衡的二叉搜索树，
代码短、速度快、逻辑简单、竞赛神器，
和字符串后缀没有任何关系！

---

如果你愿意，我可以马上给你：

• 完整可直接交题的 SBT 模板（C++）
• 或者 用对话形式继续讲：可持久化 SBT
• 或者 对比 SBT vs KMP vs 后缀数组 vs 后缀自动机

你想要哪个？