替罪羊树是什么？它如何通过重建子树保持平衡？

简化版

替罪羊树是一种不靠旋转、而靠「找失衡祖先并重建子树」保持平衡的 BST。插入后如果深度过大，就向上找第一个不满足大小平衡的节点作为替罪羊，把它的子树中序拉平再重建成平衡 BST。

详细版

替罪羊树维护一个平衡参数 α，常见取值如 2/3。某个节点若任一孩子子树大小超过 α * size(node)，说明它大小不平衡。

插入步骤：

按普通 BST 插入；
如果插入深度没有超过允许高度，结束；
否则沿父指针向上找第一个大小不平衡的祖先；
对该祖先整棵子树做中序遍历，得到有序数组；
用数组重建一棵尽量平衡的 BST，接回原父节点。

单次重建可能 O(k)，但摊还下来插入仍可保持 O(log n) 级别。它的特点是实现思路直接，不需要在每个节点维护高度或颜色。

完整版教学

一、替罪羊树为什么叫这个名字

替罪羊树的思路很有画面感：插入导致树太深时，不是沿途做很多小旋转，而是向上找一个「应该为失衡负责」的祖先节点，把它整棵子树推倒重建。这个祖先就像替罪羊，承担局部重建的代价。

它仍然是 BST，中序顺序不变。重建只是把某个子树的节点按有序数组重新搭成更矮的形状，因此搜索语义不会改变。

记忆钩子：AVL/红黑树是小修小补，替罪羊树是找到责任区域后整体翻新。

二、它用什么标准判断不平衡

替罪羊树常用子树大小而不是高度做平衡标准。设参数 α 在 (0.5,1) 之间，若某节点的左子树或右子树大小超过 α * size(node)，就认为该节点大小不平衡。

例如 α=2/3，某节点总大小 12。如果它某个孩子子树大小达到 9，则 9 > 8，超过 2/3 * 12，这个节点就过于偏向一边。重建它的子树能显著降低高度。

三、为什么插入深度过大时一定能找到替罪羊

如果插入后的深度超过理论允许高度，说明从根到新节点这条路径太长。若路径上每个祖先都满足大小平衡，那么子树规模会按至少一定比例缩小，路径长度不可能超过 O(log n)。既然实际超过了，就必然存在某个祖先违反大小平衡。

这个推理是替罪羊树正确性的核心。它不是随便找个祖先重建，而是通过深度超界证明一定有一个大小不平衡的节点可找。

四、重建子树怎么做

重建分两步：先中序遍历收集节点，再用有序数组递归取中点建树。因为中序数组有序，所以重建后仍是 BST；因为每次取中点，所以高度接近 log k。

TreeNode build(List<TreeNode> nodes, int l, int r) {
    if (l > r) return null;
    int m = (l + r) >>> 1;
    TreeNode root = nodes.get(m);
    root.left = build(nodes, l, m - 1);
    root.right = build(nodes, m + 1, r);
    return root;
}

实际实现还要清理旧左右指针、维护 parent 和 size。否则旧指针可能残留，形成错误结构。

五、和旋转型平衡树相比有什么取舍

替罪羊树不需要在每次插入时做复杂旋转分类，也不需要颜色。它只在发现深度过大时重建一段子树。缺点是单次操作可能突然很贵，比如重建一个大小为 1000 的子树就是 O(1000)。

结构	平衡方式	单次更新体验	实现特点
AVL	旋转 + 高度	稳定 O(log n)	维护高度
红黑树	旋转 + 变色	稳定 O(log n)	case 较多
替罪羊树	子树重建	摊还好，单次可能大	思路直接

所以替罪羊树适合能接受摊还复杂度、希望逻辑相对直观的场景。

六、删除时为什么还要关注全局大小

替罪羊树删除后通常不会每次立即重建，而是维护当前节点数 n 和历史最大节点数 q。如果删除太多导致 n < α * q，说明树里可能存在大量结构浪费，再整体重建并更新 q=n。这是一种延迟清理策略。

这样做避免每次删除都大动干戈。它和哈希表扩缩容有点像：不是删一个就缩一次，而是达到阈值后统一整理，靠摊还分析保证长期成本。

七、常见误区与追问

误区：替罪羊树通过旋转恢复平衡。 它的标志是失衡后重建子树，不是局部旋转。
追问：为什么深度过大一定能找到替罪羊？ 若所有祖先都大小平衡，路径长度会被限制在 O(log n)。
误区：重建会改变 BST 的有序性。 中序拉平再按中点重建，中序顺序保持不变。
追问：单次重建很贵怎么办？ 单次可能 O(k)，但重建触发有间隔，插入可做摊还分析。
误区：替罪羊树不需要维护任何信息。 至少需要子树大小或能计算大小，还常需要父指针和全局计数。

八、加强记忆

替罪羊树的路线是「插入先普通，太深找祖先，整段子树重建」。它用大小平衡而不是高度或颜色判断失衡；用中序数组保证重建后仍是 BST；用摊还思想接受偶尔较贵的重建。把它和 AVL/红黑树对比记：前者是局部旋转维护，替罪羊树是局部推倒重来。

简化版

详细版