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

来一发$leafytree$题解。(今年论文新出的神秘数据结构) 当你写二叉平衡树的时候，因为每个节点的儿子数不同导致讨论冗杂，容易出错。并且常用的几个数据结构中，$treap$适用范围较小，$splay$常数巨大且不支持可持久化，替罪羊树等其余数据结构代码量大或复杂，细节多，不易实现。那么，有没有一种神奇的数据结构，能够解决这个问题呢? ~~你为什么不问问神奇海螺呢?~~ 答案就是$leafytree$。 $leafytree$是一种奇妙的数据结构。它由叶子节点和辅助节点组成。其主要信息存储在叶子节点上，辅助节点可以理解为线段树的非最后一层节点。这也是它名称的由来。每个辅助节点都有$2$个儿子节点，用来连接整棵树。这样存储可以轻易算出辅助节点共有$n-1$个($n$是叶子节点总数)。因此，它的空间复杂度为$2n$。使用时需要注意空间问题。~~然而1e5的数据只要用9M根本不方~~ #### 1.插入和维护平衡 $leafytree$和其它的二叉搜索树一样，需要保证左边的节点权值大于右边的节点。因此，我们可以选择递归的方法来插入节点。对每个节点其下辖存储区间内的最大值(即右端点)。每次插入时，将左子树的最大点和插入节点的权值作比较。选择节点所属范围的一边即可。插入的时候加入一个叶子节点的同时也会加入一个辅助节点。 然而极易发现，这种插入方法可以被轻松卡成一条链。这样明显是不行的。因此考虑使用一些方法来维护平衡。可以再次引入替罪羊树中的平衡因子思想，如果失衡到某一个子树的$size$比全树的$size$乘上平衡因子还要小，则认为其已经失衡，需要维护。 维护失衡的方法可以选择拍扁重建，也可以选择$rotate$。因为拍扁重建和替罪羊树基本一样，所以在此不再介绍。 考虑用$rotate$来维护平衡。 定义一个节点的平衡度为$\displaystyle\frac{size[l]}{size[x]}$(假设此时左子树比右子树小)。考虑单旋和双旋对平衡度的影响。 例如单旋:(如下图，设$size[Y]>size[a]$)   设$X$旋转前的平衡度为$\rho_1$,$Y$旋转前的平衡度为$\rho_2$，旋转后分别为$\gamma_1$和$\gamma_2$。 通过简单计算可以知道: $\gamma_1=\displaystyle\frac{\rho_1}{\rho_1+(1-\rho_1)\rho_2}$ $\gamma_2=\rho_1+(1-\rho_1)\rho_2$ 同理，对于双旋，有:(图见下方) $\gamma_1=\displaystyle\frac{\rho_1}{\rho_1+(1-\rho_1)\rho_2\rho_3}$ $\gamma_2=\displaystyle\rho_1+(1-\rho_1)\rho_2\rho_3$ $\gamma_3=\displaystyle\frac{\rho_2(1-\rho_3)}{1-\rho_2\rho_3}$   此时考虑对于平衡因子$\alpha$的选取。可以证明，当$\displaystyle\alpha<1-\frac{\sqrt2}{2}$时，可以通过这两种操作来使新的节点平衡度处于$[\alpha,1-\alpha]$之内。当然此时选择$\displaystyle\alpha=1-\frac{\sqrt2}{2}$最合适。 至于维护的方法，就是当发现树失衡时，根据较小树的平衡度$\rho$进行讨论。如果$\displaystyle\rho<\frac{1-2\alpha}{1-\alpha}$时，进行一次单旋。否则进行一次双旋。 我的代码中有一个$newnode$函数和一个$delet$函数，是用来回收节点的，可以不写。 代码: ```cpp inline bool isr(int x){return x==son[fa[x]][1];} inline void rotate(int x)//简单平衡树的旋转操作(一模一样) { static int f,ff,k;f=fa[x];ff=fa[f];k=isr(x); son[fa[son[x][k^1]]=f][k]=son[x][k^1]; son[fa[x]=ff][isr(f)]=x; son[fa[f]=x][k^1]=f; refresh(f);refresh(x); if(f==rt)rt=x; } const double alp=1-sqrt(2)/2,lim=(1-2*alp)/(1-alp); inline void maintain(int x)//保持平衡 { static int dir; if(son[x][0])//非叶子节点才需要维护平衡 { if(sz[son[x][0]]<sz[x]*alp)dir=1;//找到较小的一个子树 else if(sz[son[x][1]]<sz[x]*alp)dir=0; else return;//没有失衡则跳出 if(sz[son[son[x][dir]][dir^1]]>=sz[son[x][dir]]*lim)//分情况分类讨论 rotate(son[son[x][dir]][dir^1]); rotate(son[x][dir]); } } void insert(int now,int x) { if(!rt){rt=newnode(x);return;}//特判根节点 if(sz[now]==1)//找到叶子结点 { fa[son[now][0]=newnode(x)]=now;//开启新节点，当前叶子结点下放 fa[son[now][1]=newnode(ma[now])]=now; if(x>ma[now])swap(son[now][0],son[now][1]); } else insert(son[now][x>ma[son[now][0]]],x);//向下递归 refresh(now);//维护 maintain(now); } ``` ####2.删除 发现因为节点只会删去叶子结点，所以只需要将结点直接删去，其父亲叶子结点由另一棵子树代替，也被删除。 代码: ```cpp void del(int now,int x) { int dir=x>ma[son[now][0]],t; if(sz[son[now][dir]]==1)//找到叶子结点 { delet(son[now][dir]);//直接删掉 fa[t=son[now][dir^1]]=fa[now];//用另一棵子树替代辅助节点并删除 son[fa[now]][isr(now)]=t; delet(now); if(now==rt)rt=t;//特判根的情况 now=t; } else del(son[now][dir],x);//向下递归 refresh(now);//维护 maintain(now); } ``` ####3.求结点rank 这个和普通平衡树基本一样。但是因为每个节点的$size$实际上只是叶子结点数量，所以分类讨论的细节大大减少。 代码: ```cpp int find_by_order(int now,int x) { if(sz[now]==1)return now;//找到叶子结点即返回 if(sz[son[now][0]]>=x)return find_by_order(son[now][0],x);//递归查找 else return find_by_order(son[now][1],x-sz[son[now][0]]); } ``` ####4.找到第k大元素 和普通平衡树差不多。同样也少了很多细节。 代码: ```cpp int order_of_key(int now,int x) { if(x<=mi[now])return 0;//数字不在范围内则返回0 if(sz[now]==1)return 1;//找到叶子返回1 if(ma[son[now][0]]>=x)return order_of_key(son[now][0],x);//递归求解 else return sz[son[now][0]]+order_of_key(son[now][1],x); } ``` #### 5.查找前驱/后继 直接按照定义来查找就可以了。 代码: ```cpp int pre(int now,int x) { if(sz[now]==1)return now; if(mi[son[now][1]]>=x)return pre(son[now][0],x); else return pre(son[now][1],x); } int suf(int now,int x) { if(sz[now]==1)return now; if(ma[son[now][0]]>x)return suf(son[now][0],x); else return suf(son[now][1],x); } ``` 经过测试，本程序速度优秀。在自带大常数情况下，在我自己打的几种不同平衡树中，仅次于$01trie$(如果这也算的话)。 整体代码: ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define For(i,a,b) for(i=(a),i<=(b);++i) #define Forward(i,a,b) for(i=(a),i>=(b);--i) #define Chkmin(a,b) a=a<b?a:b #define Chkmax(a,b) a=a>b?a:b #define pb push_back inline void read(int &x) { static const int BUFSIZE = 1048576; static char buf[BUFSIZE]; static char *bufnow = buf; static char *bufmax = buf; if (bufnow == bufmax) { bufmax = buf + fread(buf, 1, BUFSIZE, stdin); bufnow = buf; } static int c,f; f=1; c = *bufnow++; for (;!isdigit(c)&&(c^'-');c = *bufnow++) { if (bufnow == bufmax) { bufmax = buf + fread(buf, 1, BUFSIZE, stdin); bufnow = buf; } } if(!isdigit(c)){f=-1;c=*bufnow++;} x = 0; for (;isdigit(c);c = *bufnow++) { x = (x << 1) + (x << 3) + c - 48; if (bufnow == bufmax) { bufmax = buf + fread(buf, 1, BUFSIZE, stdin); bufnow = buf; } } x*=f; } inline void write(int a,char ed='\n') { static short s[13],tp; if(!a){putchar('0'),putchar(ed);return;} for(tp=0;a;a/=10)s[++tp]=a%10; for(;tp;putchar(s[tp--]^48)); putchar(ed); } using namespace std; const int MAXN=2e5+27; static int n; namespace leafy_tree { const double alp=1.0-sqrt(2)/2,lim=(1-2*alp)/(1-alp); static int sz[MAXN],fa[MAXN],son[MAXN][2],ma[MAXN],mi[MAXN],rt; inline void refresh(int h) { if(son[h][0]) { mi[h]=mi[son[h][0]];ma[h]=ma[son[h][1]]; sz[h]=sz[son[h][0]]+sz[son[h][1]]; } } inline bool isr(int x){return x==son[fa[x]][1];} inline void rotate(int x) { static int f,ff,k;f=fa[x];ff=fa[f];k=isr(x); son[fa[son[x][k^1]]=f][k]=son[x][k^1]; son[fa[x]=ff][isr(f)]=x; son[fa[f]=x][k^1]=f; refresh(f);refresh(x); if(f==rt)rt=x; } inline void maintain(int x) { static int dir; if(son[x][0]) { if(sz[son[x][0]]<sz[x]*alp)dir=1; else if(sz[son[x][1]]<sz[x]*alp)dir=0; else return; if(sz[son[son[x][dir]][dir^1]]>=sz[son[x][dir]]*lim) rotate(son[son[x][dir]][dir^1]); rotate(son[x][dir]); } } static int sta[MAXN],tp; inline int newnode(int x) { ma[sta[tp]]=mi[sta[tp]]=x;sz[sta[tp]]=1; return sta[tp--]; } void insert(int now,int x) { if(!rt){rt=newnode(x);return;} if(sz[now]==1) { fa[son[now][0]=newnode(x)]=now; fa[son[now][1]=newnode(ma[now])]=now; if(x>ma[now])swap(son[now][0],son[now][1]); } else insert(son[now][x>ma[son[now][0]]],x); refresh(now); maintain(now); } inline void delet(int x) {son[x][0]=son[x][1]=fa[x]=sz[x]=0;sta[++tp]=x;} void del(int now,int x) { int dir=x>ma[son[now][0]],t; if(sz[son[now][dir]]==1) { delet(son[now][dir]); fa[t=son[now][dir^1]]=fa[now]; son[fa[now]][isr(now)]=t; delet(now); if(now==rt)rt=t; now=t; } else del(son[now][dir],x); refresh(now); maintain(now); } int find_by_order(int now,int x) { if(sz[now]==1)return now; if(sz[son[now][0]]>=x)return find_by_order(son[now][0],x); else return find_by_order(son[now][1],x-sz[son[now][0]]); } int order_of_key(int now,int x) { if(x<=mi[now])return 0; if(sz[now]==1)return 1; if(ma[son[now][0]]>=x)return order_of_key(son[now][0],x); else return sz[son[now][0]]+order_of_key(son[now][1],x); } int pre(int now,int x) { if(sz[now]==1)return now; if(mi[son[now][1]]>=x)return pre(son[now][0],x); else return pre(son[now][1],x); } int suf(int now,int x) { if(sz[now]==1)return now; if(ma[son[now][0]]>x)return suf(son[now][0],x); else return suf(son[now][1],x); } } using namespace leafy_tree; inline void work() { read(n); Rep(i,1,(n<<1)+10)sta[i]=i;tp=(n<<1)+10; static int opt,x; insert(rt,-2147483647); insert(rt,2147483647); Rep(i,1,n) { read(opt);read(x); switch(opt) { case 1:insert(rt,x);break; case 2:del(rt,x);break; case 3:printf("%d\n",order_of_key(rt,x));break; case 4:printf("%d\n",ma[find_by_order(rt,x+1)]);break; case 5:printf("%d\n",ma[pre(rt,x)]);break; case 6:printf("%d\n",ma[suf(rt,x)]);break; } } } inline void file() { #ifndef ONLINE_JUDGE freopen("water.in","r",stdin); freopen("water.out","w",stdout); #endif } int main() { file(); work(); cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl; return 0; } ``` ####ex.leafy tree的其他扩展 $leafy tree$的作用远不止通过模板题。 它能够支持可持久化，且时间复杂度稳定$O(logn)$，常数比$FHQ$要更小。 它能够合并与分裂，时间复杂度为$O(logn)$，且常数比$FHQ$小。 ~~总之就是比FHQ好用~~ 并且它的形式和线段树相似，区间操作更加简单。 尽早学习，也可以作为一种常数优秀的简单平衡树来使用吧。