Splay是？
一种可以调整形态的平衡树，功能性很强
动态树就是基于Splay强大的变形功能实现的
这篇文章会浅谈Splay平衡树和动态树。
一颗Splay
前置芝士
二叉搜索树
模板传送门
P3369
【模板】普通平衡树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
基本约定
我们会用 ch 数组存放左/右子信息
旋转会需要知道某个点的父亲，所以用 fa 数组存放 父亲的信息
旋转
rotate.drawio
因为这是二叉搜索树。
对于右旋，图左有 B 左旋同理。 所以左旋和右旋是正确的。 不论是左旋还是右旋，我们都把某个结点上旋了，而上旋结点的B子树总和他的父亲不在同一侧，所以我们有了一种简便的写法同时适用于左旋和右旋 1234567void rot(int x){//把x上旋 int y=fa[x],z=fa[fa[x]],k=get(x);//ch[x][k]即B子树 ch[z][get(y)]=x,fa[x]=z; ch[y][k]=ch[x][k^1],fa[ch[x][k^1]]=y;//步骤二 ch[x][k^1]=y,fa[y]=x;//步骤三，注意步骤三只能在步骤二之后 pushup(x),pushup(y);} splay Splay的核心操作就在于将某个结点旋至根结点 我们可以先考虑单旋。 假定有一个结点 x ,我们需要把 x 旋至根。想象最极端的一种情况，这棵树目前是一条链，而 x 正位于这棵链的底端。 Example1.drawio 如上图，我们把 x 旋到了根，但是这棵树还是一条链，如果我每次都旋这条链的底端，我能轻松的卡死这个单旋算法 于是我们考虑双旋。假设我们要旋转 x ，y 是 x 的父亲，z 是 y 的父亲 如果 x ，y ，z 不在同侧，旋转两次 x 即可 twoRot2.drawio 如果 x ，y ，z 在同侧，先旋转 y ， 再旋转 x twoRot1.drawio 123456789void splay(int x,int goal=0){ while(fa[x]){ //我们根据 如果fa[x]=0,代表x已经是根了 int y=fa[x]; if(fa[y]) //我们不能转x，不然会出问题 rot(get(x)^get(y)?x:y); //^ 等同于 != ，是一种偷懒()的写法，实际跑起来也没快多少，主要是美观 rot(x); } if(!goal) root=x;} 这时候我们再来看链状的情况，依照双选的策略就可以把链旋成优秀的形态。 Example1-2.drawio 这种双旋的思路可以巧妙地均摊复杂度 我们可以通过构造势能函数来证明这样均摊下来的复杂度是O(log n) 的(具体的数学证明可以移步oi-wiki )。注意，这不是期望复杂度，他最坏的均摊复杂度就是 O(log n)。 我们可以做一些感性的理解，对于树中一个很长的部分，splay他最低的结点可能是O (n)的，但是旋转了他之后，这个“很长的部分”的高度必然以一半高度的级别衰减(我们可以从那个链的例子中看出，如果不明显，你可以手动画6个结点的链)。事实上，你要把某个部分卡的很长，也是需要很多步骤的，而这些步骤的便利，恰均摊给“很长的部分”以坏的复杂度。你旋转某个复杂度坏的结点之后，总能使他周围的结点受益，而这些结点则被均摊了好的复杂度。 所有的操作的次数做一个平均数，便是O(log n)级别的了。 删除 插入、查询前驱后继、查询排名的方法在二叉搜索树里是通用的，故不赘述。 Splay的删除非常简单。对于一个结点 x ，我们先把他的前驱 y 旋到根，再把他的后继 z 旋到后驱下面(z>y, 那么z应该为y的右儿子)，那么这棵树的状态一定是下图这样的。 道理也很简单。 因为 z 在 y 的右侧， z 的左子必然大于 y，z 的左子必然小于 z 。那么大于前驱，小于后继的就只能是 x 。 delete.drawio 此时直接删除 x 即可。 为了满足 “把 z 转到 y 下面” 的需求，我们可以对 \(splay\) 函数作出一些微调 12345678910111213141516171819void splay(int x,int goal=0){//意思是不填第二个参数默认为0 while(fa[x]^goal){ int y=fa[x]; if(fa[y]^goal) rot(get(x)^get(y)?x:y); rot(x); } if(!goal) root=x;}void del(int x){ int a=prex(x,0),b=prex(x,1);//a为前驱，b为后继 splay(a),splay(b,a); int u=ch[b][0]; if(cnt[u]==1) ch[b][0]=0; else --cnt[u],--siz[u],splay(u); //这个splay(u)我认为是可以不加的 //你其实知道u的位置就在b的左子。你不会因为重复做访问u这一步而被卡飞，那么就不用均摊他 return;} 删除操作也体现了 Spaly 强大的变形功能， 我们可以主观的调整一棵树的形态来满足我们的需求，这在后续操作中非常重要。 细节和调试指南 Splay中的查询操作也都需要均摊复杂度，因为你没法保证单次查询的复杂度是O(log n)的，所以只能均摊他，做法就是找到某个点之后splay(x)。如果你不进行均摊，我只要反复找那个点，复杂度就出错了。 我们会加入上界和下界，一个大于最大值，一个小于最小值，来保证前驱和后驱都必定能被找到。 不可以旋转根结点。这很大概率会使你的程序莫名WA。检查的 splay 函数是怎么判根的。 不可以旋转不存在的结点(包括空结点)。这会使你的程序TLE。你可能在查询函数里 splay 了值，而非结点的序号，或者你再调用查询函数的时候没有查询值，而查询了序号...各种各样，总之，注意你的函数调用。 以上两个非法操作都和 fa[0] 不为 0 有关，我们正常旋转时，如果某个结点有空子树，那空结点的父亲就不为 0 了，这是合法的。但是要旋转的点涉及到空结点时(他或他的父亲是空的)就出问题了。如果你的非法操作只有旋根，那还比较微妙，只会让你WA，因为你把空父亲旋下来相当于丧失了你的左子，还给自己的父亲连到一个未知的东西上。如果你旋了不存在的点，他甚至会让你的平衡树存在环，你就会TLE。 通用的检查方法。1. 你的root有没有更新（这会造成各种蜜汁错误）。2. 打印出 fa 数组，手动画一画看看你的树出现什么问题了 另一种写法 由于splay的过程中，我们实际只需要更新被转下去的结点，一直上旋的点始终只有 x (可以自己手模一下两种双旋需要的更新操作)。所以最后更新一下根就可以。 1234567891011121314151617void rot(int x){ int y=fa[x],z=fa[fa[x]],k=get(x); ch[z][get(y)]=x,fa[x]=z; ch[y][k]=ch[x][k^1],fa[ch[x][k^1]]=y; ch[x][k^1]=y,fa[y]=x; pushup(y);}void splay(int x,int goal=0){ while(fa[x]^goal){ int y=fa[x]; if(fa[y]^goal) rot(get(x)^get(y)?x:y); rot(x); } pushup(x); if(!goal) root=x;} 但是在数据结构中，我们总希望每一次操作之后信息都是正确的，这样最简明和便于书写，所以我更喜欢在rot里push两次的写法。如果你要 push 两次，注意是先push(y) ，后 push(x) 。 贴 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108#include