替罪羊树
引入
替罪羊树 是一种依靠重构操作维持平衡的重量平衡树。替罪羊树会在插入、删除操作后，检测树是否发生失衡；如果失衡，将有针对性地进行重构以恢复平衡。
一般地，替罪羊树不支持区间操作，且无法完全持久化；但它具有实现简单、常数较小的优点。
基本结构和操作
替罪羊树的核心操作是重构、插入和删除操作。
节点信息
替罪羊树需要存储以下信息，用于树的自平衡操作：
- 树的结构信息：
id：已使用节点数目；rt：根节点；lc[x]，rc[x]：左、右子节点；tot[x]：以为根的子树大小（每个节点计数为 ）1； tot_active：整个树中未删除（即cnt[x] != 0）的节点的数目。
当使用替罪羊树实现平衡树时，还需要存储如下信息：
- 平衡树的节点信息：
val[x]：节点存储的值；cnt[x]：节点存储的值的计数（可能为）； sz[x]：以为根的子树存储的值的计数。
为了维护节点信息，可以实现 push_up 操作：
参考实现
应注意 tot[x] 和 sz[x] 的更新方式的不同。
重构操作
当树发生失衡时，需要对某个子树进行重构，使之尽可能平衡。重构分为两步：
- 对要重构的子树做中序遍历，将所有未删除节点存到序列中；
- 二分建树，即取中点为根，左右两侧递归地建子树，并更新节点信息。
参考实现如下：
参考实现
// Tree -> Array.
void flatten(int x) {
if (!x) return;
flatten(lc[x]);
if (cnt[x]) tmp[n_tmp++] = x;
flatten(rc[x]);
}
// Array -> Tree.
int build(int ll, int rr) {
if (ll > rr) return 0;
int mm = (ll + rr) / 2;
int x = tmp[mm];
lc[x] = build(ll, mm - 1);
rc[x] = build(mm + 1, rr);
push_up(x);
return x;
}
// Rebuild a subtree.
void rebuild(int& x) {
n_tmp = 0;
flatten(x);
x = build(0, n_tmp - 1);
}
建树时注意维护节点信息，包括叶子节点的信息。
单次重构的复杂度是
插入操作
插入操作时，可能会引起树的失衡。为了判断树的失衡，需要引入参数
如果新插入的节点的深度超过了
其中，
插入操作的具体步骤如下：
- 首先利用二分查找树的性质向下找到插入值的位置，下探时记录深度；
- 如果已经有节点，直接修改节点信息，否则新建节点；
- 如果新建节点过深，就需要自下而上回溯到根，更新节点信息，并记录第一个（或任意一个）子树失衡的节点；
- 如果存在失衡节点，重构失衡节点的子树。
参考实现如下：
参考实现
// Insert v into subtree of x.
bool insert(int& x, int v, int dep) {
bool check = false;
if (!x) {
x = ++id;
val[x] = v;
check = dep > std::log(tot[rt] + 1) / std::log(1 / ALPHA);
}
if (val[x] == v) {
if (!cnt[x]) ++tot_active;
++cnt[x];
} else if (v < val[x]) {
check = insert(lc[x], v, dep + 1);
} else {
check = insert(rc[x], v, dep + 1);
}
push_up(x);
if (check && (tot[lc[x]] > ALPHA * tot[x] || tot[rc[x]] > ALPHA * tot[x])) {
rebuild(x);
return false;
}
return check;
}
// Insert v into the tree.
void insert(int v) { insert(rt, v, 0); }
注意，单次插入至多引起一次重构。如果没有新增节点或是新增节点并没有过深，又或是本次回溯过程中已经执行过重构，就不需要继续判断失衡了。多余的重构可能会导致效率损失2。回溯过程中的第一个失衡节点，就是所谓的「替罪羊」。
删除操作
删除操作的处理则非常简单。替罪羊树的删除策略是「懒删除」，即节点为空时，不移除节点，而是留待后续处理。
当然，如果树中空节点过多，树的访问效率会大大下降。因此，替罪羊树维护两个计数，整个树中未删除节点的数目和整个树实际使用的节点数目。对于选定的阈值3
参考实现
// Remove v from subtree of x.
bool remove(int x, int v) {
if (!x) return false;
bool succ = true;
if (v < val[x]) {
succ = remove(lc[x], v);
} else if (v > val[x]) {
succ = remove(rc[x], v);
} else if (cnt[x]) {
--cnt[x];
if (!cnt[x]) --tot_active;
} else {
succ = false;
}
push_up(x);
return succ;
}
// Remove v from the tree.
bool remove(int v) {
bool succ = remove(rt, v);
if (!tot_active) {
rt = 0;
} else if (succ && tot_active < tot[rt] * ALPHA) {
rebuild(rt);
}
return succ;
}
时间复杂度
大小为
本节对替罪羊树的时间复杂度仅做简要论证，详细证明请参考原论文。
替罪羊树的时间复杂度的论证
由于采用懒删除的策略，未删除节点数目为
-
访问操作：访问操作的复杂度得以保证，是因为大小为
的替罪羊树的树高总是 的。 首先，区分两个概念：
‑重量平衡：所有节点处，左、右子节点的子树的大小均不超过该节点处子树的大小的 倍； ‑高度平衡：树的高度不超过 ，其中， 是树的大小。
‑重量平衡可以推出 ‑高度平衡，因为子节点深度每增加一，大小就减少到原来的 倍；反过来则不一定成立。更严格地说，每次操作结束后，替罪羊树都总是 ‑高度平衡的4，这就保证了访问操作的复杂度。 只有插入操作会改变树的结构，所以只需要说明每次插入操作后，替罪羊树都仍是
‑高度平衡的。如果新插入的节点过深，造成了整个树不再 ‑高度平衡，那么自该节点回溯至根时，至少会碰上一个节点，即「替罪羊」，它的子树不再 ‑重量平衡。将其重构后，子树的高度将降低至少一，故而新插入的节点将不再过深。 -
插入操作：插入操作的复杂度是均摊
的。 设在某次插入操作后，节点
处发生一次子树的重构，时间成本为 。因为节点 刚插入时，或者它刚刚经历了（自身或祖先节点的）上一次重构之后，它的左右子树至多只相差一个节点。而在这次重构之前，节点 处必然成立 这一条件保证左右子树的大小的差值至少为
的。因而，这两次重构之间，子树 中插入了 个节点。 利用摊还分析可知5，如果每次插入节点时，都在（可能的重构前）自根到该节点的路径上的每个节点都增加
的势能，那么到节点 处子树重构前，必然已经在节点 处累积了 的势能，足以用于偿还 处子树重构的成本 。因为树的深度都是 的，所以单次插入增加的势能是 的；这说明， 次插入操作中势能增加的总和是 的。由此，子树重构的总成本也是 的，单次插入操作（含重构）的均摊时间复杂度就是 的。 注意，分析中没有假定在节点
处的两次重构之间，子树 内部没有发生其它的重构。因此，只要只重构满足失衡条件的节点处的子树，就能保证复杂度正确。 -
删除操作：删除操作的复杂度也是均摊
的。 删除引起的重构会导致整个树不含空节点。而某次删除引起重构之前，整个树中已经有
个空节点，这意味着至少进行了 次删除操作。因为每次删除操作的寻址的复杂度是 的，且单次重构的复杂度是 ，所以这 次删除操作的实际时间成本为 的。故而，单次删除的均摊复杂度为
的。
平衡树操作
本节介绍用替罪羊树维护可重集的方法。
除上节介绍的操作外，其余操作均为平衡树的常见操作。但是，因为替罪羊树中可能存在空节点，这些操作也需要相应调整。
查询排名
利用二分查找树的性质向下查找节点位置，过程中记录路径左侧存储的值的数目即可。
参考实现
根据排名查询值
利用节点记录的子树存储值的数目信息向下查找即可。注意可能存在计数为零的节点。
参考实现
查询前驱、后继
以上两种功能结合即可。
参考实现
如果想直接实现，应注意处理计数为零的节点。
参考实现
本节的最后，给出模板题 普通平衡树 的参考实现。
参考实现
#include <cmath>
#include <iostream>
constexpr int N = 2e6;
constexpr double ALPHA = 0.7;
int id, rt, lc[N], rc[N], tot[N], tot_active; // Tree structure info.
int tmp[N], n_tmp; // Space for rebuilding trees.
int val[N], cnt[N], sz[N]; // Node info.
// Update node info from its children.
void push_up(int x) {
tot[x] = 1 + tot[lc[x]] + tot[rc[x]];
sz[x] = cnt[x] + sz[lc[x]] + sz[rc[x]];
}
// Tree -> Array.
void flatten(int x) {
if (!x) return;
flatten(lc[x]);
if (cnt[x]) tmp[n_tmp++] = x;
flatten(rc[x]);
}
// Array -> Tree.
int build(int ll, int rr) {
if (ll > rr) return 0;
int mm = (ll + rr) / 2;
int x = tmp[mm];
lc[x] = build(ll, mm - 1);
rc[x] = build(mm + 1, rr);
push_up(x);
return x;
}
// Rebuild a subtree.
void rebuild(int& x) {
n_tmp = 0;
flatten(x);
x = build(0, n_tmp - 1);
}
// Insert v into subtree of x.
bool insert(int& x, int v, int dep) {
bool check = false;
if (!x) {
x = ++id;
val[x] = v;
check = dep > std::log(tot[rt] + 1) / std::log(1 / ALPHA);
}
if (val[x] == v) {
if (!cnt[x]) ++tot_active;
++cnt[x];
} else if (v < val[x]) {
check = insert(lc[x], v, dep + 1);
} else {
check = insert(rc[x], v, dep + 1);
}
push_up(x);
if (check && (tot[lc[x]] > ALPHA * tot[x] || tot[rc[x]] > ALPHA * tot[x])) {
rebuild(x);
return false;
}
return check;
}
// Insert v into the tree.
void insert(int v) { insert(rt, v, 0); }
// Remove v from subtree of x.
bool remove(int x, int v) {
if (!x) return false;
bool succ = true;
if (v < val[x]) {
succ = remove(lc[x], v);
} else if (v > val[x]) {
succ = remove(rc[x], v);
} else if (cnt[x]) {
--cnt[x];
if (!cnt[x]) --tot_active;
} else {
succ = false;
}
push_up(x);
return succ;
}
// Remove v from the tree.
bool remove(int v) {
bool succ = remove(rt, v);
if (!tot_active) {
rt = 0;
} else if (succ && tot_active < tot[rt] * ALPHA) {
rebuild(rt);
}
return succ;
}
// Find the rank of v, i.e., #{val < v} + 1.
int find_rank(int v) {
int res = 0;
int x = rt;
while (x && val[x] != v) {
if (v < val[x]) {
x = lc[x];
} else {
res += sz[lc[x]] + cnt[x];
x = rc[x];
}
}
return res + sz[lc[x]] + 1;
}
// Find the k-th smallest element.
int find_kth(int k) {
if (k <= 0 || sz[rt] < k) return -1;
int x = rt;
for (;;) {
if (k <= sz[lc[x]]) {
x = lc[x];
} else if (k <= sz[lc[x]] + cnt[x]) {
return val[x];
} else {
k -= sz[lc[x]] + cnt[x];
x = rc[x];
}
}
return -1;
}
// Find predecessor.
int find_prev(int x) { return find_kth(find_rank(x) - 1); }
// Find successor.
int find_next(int x) { return find_kth(find_rank(x + 1)); }
int main() {
int n;
std::cin >> n;
for (; n; --n) {
int op, x;
std::cin >> op >> x;
switch (op) {
case 1:
insert(x);
break;
case 2:
remove(x);
break;
case 3:
std::cout << find_rank(x) << '\n';
break;
case 4:
std::cout << find_kth(x) << '\n';
break;
case 5:
std::cout << find_prev(x) << '\n';
break;
case 6:
std::cout << find_next(x) << '\n';
break;
}
}
return 0;
}
参考资料
- Galperin, Igal, and Ronald L. Rivest. "Scapegoat trees." Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. 1993.
- Scapegoat Tree - Wikipedia
- 替罪羊树 - riteme 的博客
-
也可以只统计未删除节点数目，此时不再需要统计
tot_active，而需要统计所有占用节点数目tot_max，代码相应调整即可。 ↩ -
根据后文的复杂度分析可知，这些效率损失仅意味着更大的常数因子，而复杂度依然是正确的。因为判断树深可能会涉及较多的浮点数对数运算，不判断树深只判断失衡的代码在某些数据中可能更快。 ↩
-
不必与上文插入操作时选取的参数相同。尽管原论文做了这样的假定，但是选取不同的参数只会导致单次操作的复杂度中常数项的变化，整体复杂度依然是正确的。 ↩
-
按原文定义，
指未删除节点的数目，故而只能保证树高不超过 ，这称为弱 ‑高度平衡。此处没有细究该常数项的差异。 ↩ -
有些文章会简单分析成
次插入对应一次重构，故而均摊复杂度为 。这样的思路可以辅助理解均摊复杂度为什么正确，但并不严谨。这是因为，一次插入可能对应着多个祖先节点的重构，故而当节点 发生重构时，子树内未引起重构的节点数目并不显然是 的。 ↩
创建日期: 2018年7月11日