跳至主要內容

替罪羊树（2026.4.2）

Minecraftbucuo2026/4/2大约 8 分钟

替罪羊树（2026.4.2）

视频教程链接：替罪羊树

在平衡树的大家族中，替罪羊树独树一帜。它不依赖复杂的旋转操作（如左旋、右旋）来维持平衡，而是采用一种简单粗暴却极具美感的策略：当树变得不平衡时，直接将不平衡的子树“拍扁”再重新构建。这种“不破不立”的思想，正是替罪羊树的核心魅力所在。

核心定义与平衡因子

替罪羊树的平衡性由一个关键参数——平衡因子 α\alpha 来定义。对于树中的任意节点 xx，其左右子树的大小必须满足以下条件：

max⁡(node_size(left),node_size(right))≤α×node_size(x)\max(node\_size(left), node\_size(right)) \le \alpha \times node\_size(x)

  • α\alpha 的取值：通常在 [0.5,1.0][0.5, 1.0] 之间。

    • 如果 α\alpha 取值过小（如接近 0.5），树会非常平衡，但会导致频繁重构，影响效率。
    • 如果 α\alpha 取值过大（如接近 1.0），重构次数减少，但树的高度可能失控。
    • 实践中，α\alpha 常取 0.7 或 0.75。

  • 替罪羊节点：当插入或删除操作破坏了上述平衡条件时，我们会沿着操作路径向上回溯，找到 最浅的（深度最小的） 不满足平衡条件的节点。这个节点就是“替罪羊”，我们将以它为根的整个子树进行重构。

懒惰删除与节点维护

替罪羊树在删除节点时采用 “懒惰删除” 策略。它并不会立即从树中物理移除节点，而是将节点的计数 key_cnt 减一。当 key_cnt 降为 0 时，该节点在逻辑上被视为已删除。这些被标记的节点会在后续的重构过程中被真正清理掉。

为了支持懒惰删除，每个节点需要维护两个计数：

  1. num_size：以该节点为根的子树中数值的总个数（包含重复值）。
  2. node_size：以该节点为根的子树中不同数值的节点个数（即 key_cnt > 0 的节点数）。

核心操作详解

替罪羊树的基本操作（如查询排名、第 k 大值、前驱、后继）与普通二叉搜索树（BST）完全相同。其独特之处在于插入和删除后的平衡维护。

重构：灵魂操作

重构操作分为两步：拍扁（Inorder） 和 重建（Build）。

  1. 拍扁：对需要重构的子树进行中序遍历，将所有有效（key_cnt > 0）节点按顺序存入一个临时数组 tmp 中。
  2. 重建：取数组的中间元素作为新的根节点，然后递归地对左右两部分数组进行同样的操作，构建左右子树。这样构建出的新子树是一棵完全二叉树，高度达到最优。

代码实现：

// 收集需要重构的节点
void inorder(const int i) {
    if (i == 0) return;
    inorder(left[i]);
    if (key_cnt[i] > 0) tmp[++tmp_cnt] = i; // 只收集有效节点
    inorder(right[i]);
}

// 重建：根据有序数组构建完全二叉树
int build(const int l, const int r) {
    if (l > r) return 0;
    const int mid = (l + r) >> 1;
    const int t = tmp[mid];
    left[t] = build(l, mid - 1);
    right[t] = build(mid + 1, r);
    up(t); // 更新节点信息
    return t;
}

// 重构主函数
void rebuild() {
    if (top == 0) return; // 没有找到替罪羊，直接返回
    tmp_cnt = 0;
    inorder(top); // 拍扁
    if (tmp_cnt <= 0) return;
    // 将重建后的子树接回原树
    if (father == 0) head = build(1, tmp_cnt); // 替罪羊是根节点
    else if (side == 1) left[father] = build(1, tmp_cnt); // 替罪羊是左儿子
    else right[father] = build(1, tmp_cnt); // 替罪羊是右儿子
}
插入

插入操作首先按照普通 BST 的规则找到位置并插入新节点。在递归回溯的过程中，检查当前节点是否满足平衡条件。如果发现不平衡，就记录下这个“替罪羊”节点及其父节点信息，在插入完成后统一进行重构。

代码实现：

void insert(const int i, const int f, const int s, const int num) {
    if (i == 0) {
        // 找到空位，创建新节点
        if (f == 0) head = init(num);
        else if (s == 1) left[f] = init(num);
        else right[f] = init(num);
    } else {
        if (num == key[i]) key_cnt[i]++;
        else if (num < key[i]) insert(left[i], i, 1, num);
        else insert(right[i], i, 2, num);
        up(i); // 更新节点信息
        // 检查是否需要重构
        if (!balance(i)) {
            top = i; // 记录替罪羊
            father = f;
            side = s;
        }
    }
}
删除

删除操作首先找到目标节点，然后将其 key_cnt 减一，并更新路径上所有节点的 num_size 和 node_size 计数。同样，在回溯过程中，如果发现某棵子树不平衡，也会记录下“替罪羊”，在删除完成后触发重构，以清理垃圾节点并恢复平衡。

代码实现：

void remove(const int i, const int f, const int s, const int num) {
    if (key[i] == num) {
        key_cnt[i]--; // 懒惰删除
    } else if (key[i] > num) {
        remove(left[i], i, 1, num);
    } else {
        remove(right[i], i, 2, num);
    }
    up(i); // 更新节点信息
    // 检查是否需要重构
    if (!balance(i)) {
        top = i;
        father = f;
        side = s;
    }
}

复杂度分析

尽管重构操作看起来很“暴力”，但替罪羊树的整体性能依然优秀。

  • 查询操作：由于树的高度被 ALPHA 因子严格控制，查询操作的最坏时间复杂度为 O(log⁡n)O(\log n)。
  • 插入/删除操作：单次插入或删除操作可能会触发一次 O(k)O(k) 的重构（kk 为重构子树的大小）。然而，通过均摊分析可以证明，每次操作分摊下来的时间复杂度仍然是 O(log⁡n)O(\log n)。这是因为一次大规模的重构操作，其“代价”可以被之前多次不触发重构的廉价操作所分摊。

总结与应用

替罪羊树以其独特的“暴力重构”思想，在平衡树中占据了一席之地。它的优点非常突出：

  1. 实现简单：无需处理复杂的旋转逻辑，代码量少，易于理解和调试。
  2. 性能可靠：均摊 O(log⁡n)O(\log n) 的复杂度保证了其在大多数场景下的高效性。
  3. 易于扩展：其思想可以应用到其他数据结构中。

总而言之，替罪羊树是“优雅暴力”的完美诠释，它用最直接的方式解决了平衡问题，展现了算法设计中简洁与力量的结合。

完整参考代码

// https://www.luogu.com.cn/problem/P3369   P3369 【模板】普通平衡树
#include <bits/stdc++.h>
constexpr int N = 1e5 + 10;

class ScapegoatTree {
public:
    explicit ScapegoatTree(const int n) : right(n), left(n), key(n), key_cnt(n), num_size(n), node_size(n), tmp(n) {

    }

    void insert(const int num) {
        top = father = side = 0;
        insert(head, 0, 0, num);
        rebuild();
    }

    int getRank(const int num) {
        return small(head, num) + 1;
    }
    // 获取最大的小于num的数
    int pre(const int num) {
        const int kth = getRank(num);
        if (kth == 1) return INT32_MIN;
        return index(kth - 1);
    }
    // 获取最小的大于num的数
    int post(const int num) {
        const int kth = getRank(num + 1);
        if (kth == num_size[head] + 1) return INT32_MAX;
        return index(kth);
    }
    // 获取从小到大排序后排名第x的数字
    int index(const int x) {
        return index(head, x);
    }

    void remove(const int num) {
        if (getRank(num) != getRank(num + 1)) {
            top = father = side = 0;
            remove(head, 0, 0, num);
            rebuild();
        }
    }

private:
    int index(const int u, const int x) {
        if (num_size[left[u]] >= x) return index(left[u], x);
        if (num_size[left[u]] + key_cnt[u] < x) return index(right[u], x - num_size[left[u]] - key_cnt[u]);
        return key[u];
    }

    void remove(const int i, const int f, const int s, const int num) {
        if (key[i] == num) {
            key_cnt[i]--;
        } else if (key[i] > num) {
            remove(left[i], i, 1, num);
        } else {
            remove(right[i], i, 2, num);
        }
        up(i);
        if (!balance(i)) {
            top = i;
            father = f;
            side = s;
        }
    }

    void insert(const int i, const int f, const int s, const int num) {
        if (i == 0) {
            if (f == 0) head = init(num);
            else if (s == 1) left[f] = init(num);
            else right[f] = init(num);
        } else {
            if (num == key[i]) key_cnt[i]++;
            else if (num < key[i]) insert(left[i], i, 1, num);
            else insert(right[i], i, 2, num);
            up(i);
            if (!balance(i)) {
                top = i;
                father = f;
                side = s;
            }
        }
    }

    // 统计小于num的元素个数
    int small(const int u, const int num) {
        if (u == 0) return 0;
        if (key[u] >= num) return small(left[u], num);
        return key_cnt[u] + num_size[left[u]] + small(right[u], num);
    }

    void up(const int i) {
        num_size[i] = num_size[left[i]] + num_size[right[i]] + key_cnt[i];
        node_size[i] = node_size[left[i]] + node_size[right[i]] + (key_cnt[i] > 0);
    }

    [[nodiscard]] bool balance(const int i) const {
        return ALPHA * node_size[i] >= std::max(node_size[left[i]], node_size[right[i]]);
    }

    // 收集需要重构的节点
    void inorder(const int i) {
        if (i == 0) return;
        inorder(left[i]);
        if (key_cnt[i] > 0) tmp[++tmp_cnt] = i;
        inorder(right[i]);
    }

    void rebuild() {
        if (top == 0) return;
        tmp_cnt = 0;
        inorder(top);
        if (tmp_cnt <= 0) return;
        if (father == 0) head = build(1, tmp_cnt);
        else if (side == 1) left[father] = build(1, tmp_cnt);
        else right[father] = build(1, tmp_cnt);
    }

    int build(const int l, const int r) {
        if (l > r) return 0;
        const int mid = (l + r) >> 1;
        const int t = tmp[mid];
        left[t] = build(l, mid - 1);
        right[t] = build(mid + 1, r);
        up(t);
        return t;
    }

    int init(const int num) {
        key[++cnt] = num;
        key_cnt[cnt] = num_size[cnt] = node_size[cnt] = 1;
        return cnt;
    }

    std::vector<int> right;
    std::vector<int> left;
    std::vector<int> key;
    std::vector<int> key_cnt;
    std::vector<int> num_size;
    std::vector<int> node_size;
    std::vector<int> tmp;
    int cnt{}, top{}, father{}, head{}, side{}, tmp_cnt{};
    static constexpr double ALPHA = 0.7;
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    ScapegoatTree scapegoat_tree(N);
    for (int i = 1; i <= n; i++) {
        int op, x;
        std::cin >> op >> x;
        if (op == 1) {
            scapegoat_tree.insert(x);
        } else if (op == 2) {
            scapegoat_tree.remove(x);
        } else if (op == 3) {
            std::cout << scapegoat_tree.getRank(x) << "\n";
        } else if (op == 4) {
            std::cout << scapegoat_tree.index(x) << "\n";
        } else if (op == 5) {
            std::cout << scapegoat_tree.pre(x) << "\n";
        } else {
            std::cout << scapegoat_tree.post(x) << "\n";
        }
    }
    return 0;
}

最后更新于：2026-04-02

最近更新:
贡献者: 杨必胜