Splay基础操作

Splay

Splay是一类二叉查找树，与其他平衡树相比，也是运用旋转保证复杂度
其最重要的操作便是$rotate$ $and$ $spaly$了
先来谈旋转，我们都知道，旋转是这样的

仔细观察后，我们会发现，旋转操作可以拆解为三步，设$x$是$y$的父亲，$k$表示$y$是$x$的儿子（左0右1），现在要将$y$旋转

1. 将$x$的父节点的子节点从$x$改为$y$
2. 将$x$的$k$儿子换成$y$的$1-k$儿子
3. 将$y$的$1-k$儿子变成$x$
   写成代码即为：

void rotate(int x){int y=t[x].f,z=t[y].f,k=t[y].ch[1]==x;t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].f=y;t[z].ch[t[z].ch[1]==y]=x; t[x].f=z;t[x].ch[k^1]=y;t[y].f=x;pushup(y);pushup(x);//不要忘记旋转后更新信息
}

接着便是$Splay$操作，对于使用到的一个节点$x$，我们将其一直旋转至树根，便是$Splay$操作，在旋转过程中，不能一直单旋转，我们发现$x和father(x)$都是自己父亲的$k$儿子的情况下，先旋转$x$的父节点，再旋转$x$会使得树变得更加均衡，会更加优秀

void splay(int x,int goal=0){while(t[x].f!=goal){int y=t[x].f,z=t[y].f;if(z!=goal){t[z].ch[1]==y ^ t[y].ch[1]==x?rotate(x):rotate(y);}rotate(x);}if(!goal)root=x;
}

然后便是其他平衡树的常规操作了

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

我们来分别考虑几种操作,为了方便操作，我们往树中插入两个无穷大和无穷小的哨兵
1.插入操作
在树中查找$x$，并记录其父节点$p$，若找到了$x$节点，则将其计数的$cnt$加上1，若没有找到$x$节点，此时$p$一定是一个叶子节点，直接判断$x$应是其的哪一个儿子，直接加上关系即可，最后还得$Splay$一下

void insert(int x){int u=root,p=0;while(u&&t[u].val!=x){p=u;u=t[u].ch[x>t[u].val];}if(!u){u=++tot;t[u].cnt=t[u].siz=1;t[u].f=p,t[u].val=x;if(p)t[p].ch[x>t[p].val]=tot;}else{t[u].cnt++;}splay(u);
}

2.删除操作
因为普普通通的删除很麻烦，所以我们采用一种简单的方式：
将$x$在树中的严格前驱和严格后继找到，将严格前驱旋转到树根，将严格后继旋转为严格前驱的儿子，此时$x$一定位于$t[t[root].ch[1]].ch[0]$,执行即可

void Delete(int x){int last=nxt(x,0);int nex=nxt(x,1);splay(last,0);splay(nex,last);if(t[t[nex].ch[0]].cnt>1){t[t[nex].ch[0]].cnt--;splay(t[nex].ch[0]);}else  t[nex].ch[0]=0;pushup(nex),pushup(last);
}

3.查询排名
我们可以对于每一个节点记录$siz$，表示节点$x$及其子树中有多少个节点，这样我们就可以找到节点$x$后将其旋转至树根，求树根左儿子的$siz$再加一即可，但由于哨兵无穷小的存在，无需加一

int rak(int x){find(x);//查找到x所在节点，并将其旋转至根节点return t[t[root].ch[0]].siz;
} 

4.查找排名为$k$的数
我们可以从根节点开始查找，对于一个节点$p$,若$k\le t[t[p].ch[0]].siz$,那么这个节点就在$p$的左子树中，若$t[t[p].ch[0]].siz<k\le t[t[p].ch[0]].siz+t[p].cnt$,则说明当前节点$p$即为要找的节点，否则令$k=k-t[p].cnt-t[t[p].ch[0]].siz$，然后再进入右子树

int kth(int u){int x=root;if(t[x].siz

int nxt(int x,int f){find(x);if ((f==0&&t[root].valx))return root;//特判x不在树中的情况int u=t[root].ch[f];while (t[u].ch[!f])u=t[u].ch[!f];splay(u);return u;
}

void find(int x){int u=root;while(t[u].ch[x>t[u].val]&&t[u].val!=x){u=t[u].ch[x>t[u].val];}splay(u);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！