什么是「替罪羊树」？

「替罪羊」这个名字非常有趣（以至于一开始我并不觉得这是什么好懂的东西）。名字的来源大概是由于它在删除时候需要用被删除节点的：左子树最后一个节点/右子树第一个节点来顶替这个节点。数据结构圈居然还有这么脑洞的名字（好像还有一个东西叫做朝鲜树来着？）

替罪羊的精华在于，它相较于其他大多数的平衡树而言，并不需要旋转操作。它维护平衡的方式是非常暴力美学的回收点并重构。

重构前奏

我们先来考虑一下两颗树在内容相同的情况下，怎么样的才算是更加「平衡」。显而易见，形象的来说，更接近于满二叉树的二叉搜索树更加平衡。

那么什么时候两颗二叉搜索树会内容相同呢？

注意到二叉搜索树的性质：任意一个节点记为$a$，其左儿子记为$l$，右儿子记为$r$，那么必有$l_{val}≤a_{val}≤r_{val}$。也就是说，一颗二叉搜索树的中序遍历的权值是单调的。这也说明若两颗二叉搜索树内容相同，当且仅当其中序遍历相同。

于是我们发现可以先把这颗不太平衡的二叉搜索树压成中序遍历后的序列，然后再由这个序列重新构造出一个内容相同的更加平衡的二叉搜索树。

这个过程就叫做「拍扁」

重构

 1 void hit(int x)
 2 {
 3     if (!x) return;
 4     hit(a[x][0]);
 5     sv[++cntSv] = x;
 6     hit(a[x][1]);
 7 } 9 int build(int l, int r)
10 {
11     if (l > r) return 0;
12     int mid = (l+r)>>1, tmp = sv[mid];
13     a[tmp][0] = build(l, mid-1);
14     a[a[tmp][0]].fa = tmp;
15     a[tmp][1] = build(mid+1, r);
16     a[a[tmp][1]].fa = tmp;
17     change(tmp);
18     return tmp;
19 }
20 inline void rebuild(int x)
21 {
22     cntSv = 0;
23     hit(x);
24     int fa = a[x].fa, d = (a[fa][1]==x), nd = build(1, cntSv);
25     a[a[fa][d]=nd].fa = fa;
26     if (x==root) root = nd;
27 }

那么重构这么做就好了。

何时重构？

我们现在知道了如何重构，但是何时重构呢？

阈值重构

最朴素的想法就是制定一个阈值，当插入次数超过阈值时就重构一遍。

这种方法并不需要任何思维难度，但是缺点也显而易见：遇上特定数据时效率会大打折扣（luogu4169 [Violet]天使玩偶/SJY摆棋子的point#11就是一个卡替罪羊树非子树重构的数据）。

子树比例重构

回到替罪羊的特点：它维护平衡的操作是不依靠旋转的。

这就意味着，替罪羊树不一定每时每刻都那么平衡。但是它相较于需要旋转的平衡树来说，节省了每次旋转的花费。

换句话说，替罪羊树允许一定程度上的不平衡。但当不平衡的程度过大时，我们就需要重构一部分子树了。

通常来说，这个比例值取在0.5-0.9之间。不同取值的实际效果主要吃数据，一般取0.75就无大碍了。

插入

那么介绍了子树比例重构，与之密切相关的就是插入操作了。

替罪羊的插入需要写成迭代的形式，因为要在插入之后判断是否需要重构。

 1 void insert(int x)
 2 {
 3     if (!root){
 4         root = ++cnt;
 5         a[root].val = x, a[root].tot = 1, a[root].fa = 0;
 6         return;
 7     }
 8     int nd = root;
 9     for (;;)
10     {
11         a[nd].tot++;
12         int fa = nd, d = (x >= a[nd].val);
13         nd = a[nd][d];
14         if (!nd){　　　　　　//找到了一个可以插入的位置
15             nd = ++cnt, a[fa][d] = nd;
16             a[nd].tot = 1, a[nd].val = x, a[nd].fa = fa;
17             break;
18         }
19     }
20     int rec = 0;
21     for (int i=cnt; i; i = a[i].fa)　//需要找到一个最高的不满足条件的点进行重构
22         if (std::max(a[a[i][0]].tot, a[a[i][1]].tot)*5 >= a[i].tot*4)
23             rec = i;
24     if (rec) rebuild(rec);
25 }

删除

替罪羊的删除似乎有两种？

一种就是「替罪羊」做法；另一种是干脆把要删除的点打个标记，统计时候跳过就好了。

以下介绍「替罪羊」做法：

 1 void erase(int k)
 2 {
 3     if(a[k][0]&&a[k][1])
 4     {
 5         int tmp = a[k][0];
 6         while(a[tmp][1]) tmp = a[tmp][1];
 7         a[k].val = a[tmp].val;
 8         k = tmp;
 9     }
10     int s = a[k][0]?a[k][0]:a[k][1];　　　　　　//s=0表示左儿子;s=1表示右儿子
11     int f = a[k].fa, d = (a[f][1]==k);
12     a[f][d] = s, a[s].fa = f;
13     for(int i=f; i; i=a[i].fa)
14         a[i].tot--;
15     if(root==k) root = s;
16 }

这里写了个迭代。

替罪羊树板子

P3369 【模板】普通平衡树（Treap/SBT）

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 x 数
删除 x 数(若有多个相同的数，因只删除一个)
查询 x 数的排名(排名定义为比当前数小的数的个数 +1 。若有多个相同的数，因输出最小的排名)
查询排名为 x 的数
求 x 的前驱(前驱定义为小于 x ，且最大的数)
求 x 的后继(后继定义为大于 x ，且最小的数)

输入输出格式

输入格式：

第一行为 n，表示操作的个数,下面 n 行每行有两个数 opt 和 x ， opt 表示操作的序号(1≤opt≤6 )

输出格式：

对于操作 3,4,5,6 每行输出一个数，表示对应答案

题目分析

那么就直接上代码吧。

  1 #include<bits/stdc++.h>
  2 const int maxn = 100003;
  3 
  4 int n,cnt,root,sv[maxn],cntSv,sum,lim;
  5 struct node
  6 {
  7     int son[2],tot,val,rnd,fa;
  8     int &
  9     operator [](const int a)
 10     {
 11         return son[a];
 12     }
 13 }a[maxn];
 14 
 15 template <typename T> void printe(const T x)
 16 {
 17     if(x>=10)printe(x/10);
 18     putchar(x%10+'0');
 19 }
 20 template <typename T> inline void print(const T x)
 21 {
 22     if(x<0)putchar('-'),printe(-x);
 23     else printe(x);
 24 }
 25 char tz()
 26 {
 27     static char tr[10000],*A=tr,*B=tr;
 28     return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;
 29 }
 30 inline int read()
 31 {
 32     char ch = tz();
 33     int num = 0;
 34     bool fl = 0;
 35     for (; !isdigit(ch); ch = tz())
 36         if (ch=='-') fl = 1;
 37     for (; isdigit(ch); ch = tz())
 38         num = (num<<1)+(num<<3)+ch-48;
 39     if (fl) num = -num;
 40     return num;
 41 }
 42 inline void change(int x)
 43 {
 44     a[x].tot = a[a[x][0]].tot+a[a[x][1]].tot+1;
 45 }
 46 void hit(int x)
 47 {
 48     if (!x) return;
 49     hit(a[x][0]);
 50     sv[++cntSv] = x;
 51     hit(a[x][1]);
 52 }
 53 int build(int l, int r)
 54 {
 55     if (l > r) return 0;
 56     int mid = (l+r)>>1, tmp = sv[mid];
 57     a[tmp][0] = build(l, mid-1);
 58     a[a[tmp][0]].fa = tmp;
 59     a[tmp][1] = build(mid+1, r);
 60     a[a[tmp][1]].fa = tmp;
 61     change(tmp);
 62     return tmp;
 63 }
 64 inline void rebuild(int x)
 65 {
 66     cntSv = 0;
 67     hit(x);
 68     int fa = a[x].fa, d = (a[fa][1]==x), nd = build(1, cntSv);
 69     a[a[fa][d]=nd].fa = fa;
 70     if (x==root) root = nd;
 71 }
 72 inline void insert(int x)
 73 {
 74     if (!root){
 75         root = ++cnt;
 76         a[root].val = x, a[root].tot = 1, a[root].fa = 0;
 77         return;
 78     }
 79     int nd = root;
 80     for (;;)
 81     {
 82         a[nd].tot++;
 83         int fa = nd, d = (x >= a[nd].val);
 84         nd = a[nd][d];
 85         if (!nd){
 86             nd = ++cnt, a[fa][d] = nd;
 87             a[nd].tot = 1, a[nd].val = x, a[nd].fa = fa;
 88             break;
 89         }
 90     }
 91     int rec = 0;
 92     for (int i=cnt; i; i = a[i].fa)
 93         if (std::max(a[a[i][0]].tot, a[a[i][1]].tot)*5 >= a[i].tot*4)
 94             rec = i;
 95     if (rec) rebuild(rec);
 96 }
 97 int getpl(int x)
 98 {
 99     int tmp = root;
100     while(tmp){
101         if(x==a[tmp].val) return tmp;
102         int d = (x>=a[tmp].val);
103         tmp = a[tmp][d];
104     }
105     return tmp;
106 }
107 void erase(int k)
108 {
109     if(a[k][0]&&a[k][1])
110     {
111         int tmp = a[k][0];
112         while(a[tmp][1]) tmp = a[tmp][1];
113         a[k].val = a[tmp].val;
114         k = tmp;
115     }
116     int s = a[k][0]?a[k][0]:a[k][1];
117     int f = a[k].fa, d = (a[f][1]==k);
118     a[f][d] = s, a[s].fa = f;
119     for(int i=f; i; i=a[i].fa)
120         a[i].tot--;
121     if(root==k) root = s;
122 }
123 inline int find(int x)
124 {
125     int nd = root, ret = 1;
126     while (nd)
127     {
128         if (x <= a[nd].val)
129             nd = a[nd][0];
130         else{
131             ret += a[a[nd][0]].tot+1;
132             nd = a[nd][1];
133         }
134     }
135     return ret;
136 }
137 inline int ask(int x)
138 {
139     int nd = root;
140     while (nd)
141         if (x <= a[a[nd][0]].tot)
142             nd = a[nd][0];
143         else{
144             x -= a[a[nd][0]].tot;
145             if (x==1) return a[nd].val;
146             x--;
147             nd = a[nd][1];
148         }
149 }
150 inline int pre(int x)
151 {
152     int ret = -2e9, nd = root;
153     while (nd)
154         if (x > a[nd].val) ret = std::max(ret, a[nd].val), nd = a[nd][1];
155         else nd = a[nd][0];
156     return ret;
157 }
158 inline int suf(int x)
159 {
160     int ret = 2e9, nd = root;
161     while (nd)
162         if (x < a[nd].val) ret = std::min(ret, a[nd].val), nd = a[nd][0];
163         else nd = a[nd][1];
164     return ret;
165 }
166 int main()
167 {
168     n = read();
169     for (int i=1; i<=n; i++)
170     {
171         int tt, x;
172         tt = read(), x = read();
173         if (tt==1) insert(x);
174         if (tt==2)
175         {
176             int p = getpl(x);
177             if (p) erase(p);
178         }
179         if (tt==3) print(find(x)),putchar('
');
180         if (tt==4) print(ask(x)),putchar('
');
181         if (tt==5) print(pre(x)),putchar('
');
182         if (tt==6) print(suf(x)),putchar('
');
183     }
184     return 0;
185 }

替罪羊的其他例题同「treap」那一篇的例题介绍。其实这些题用任何一种平衡树都可以，只不过不同平衡树维护平衡的操作不一罢了。

好像替罪羊树的效率非常之高？

END