Splay

xiaoxiao2021-02-28  7

简介

伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特(Daniel Sleator)和罗伯特·恩卓·塔扬(Robert Endre Tarjan)在1985年发明的。

原理

普通二叉排序树很容易因为变成一条链而导致时间复杂度大大增加,而Splay则通过伸展来不断地变换树的形态,这样即使出现了链也很快会被打破当前链的状态,从而大大降低了复杂度。

所以有事没事就Splay一下,当你发现你有几个点T掉的时候,很有可能就是你Splay太少了。

均摊复杂度 O(nlog2n)

伸展实现

Splay的伸展用到了旋转。这个旋转和Treap一样。只是要分情况讨论如何旋转。

下面我们来讨论伸展:

1.当x的爷爷是目标节点时,此时只需根据情况左旋/右旋就好了

2.当x的爷爷不是目标节点时 ​ ①:当x,y,z不在一条直线上时 ​ ②:当x,y,z在同一条直线上时 总结一下,当x,y,z不在同一条直线上时先旋转x,在同一条直线上时先旋转y,然后再旋转x。

代码实现:

void rtt(int x,int &w){//x表示当前节点,w表示目标节点 int y=t[x].fa,z=t[y].fa,l=(t[y].to[1]==x),r=l^1; //根据x是y的左儿子还是右儿子来确定左旋或右旋 if (y==w) w=x; else t[z].to[t[z].to[1]==y]=x; //如果y有父亲(z)的话就把x接到z上 t[t[x].to[r]].fa=y,t[y].fa=x,t[x].fa=z; t[y].to[l]=t[x].to[r],t[x].to[r]=y; //把x的另一个儿子给y,y变成z的儿子 pshp(y),pshp(x);//pushup用来重新计算这个节点的其他量 } void splay(int x,int &w){ while (x!=w){ int y=t[x].fa,z=t[y].fa; if (y!=w) if (t[z].to[0]==y^t[y].to[0]==x) rtt(x,w); else rtt(y,w); rtt(x,w); } }

操作

基本操作

Splay支持一般BST的基本操作,因为其他操作大同小异,所以这里只讲讲插入/删除操作。

想看其他操作的同学戳Treap

插入:

因为Splay不需要记录键值来维护堆的性质,所以它的插入变得简单很多。根据它的权值确定位置后直接插入即可。

代码:

void nsrt(int &x,int w,int fa){ if (!x){ t[x=++nd].w=w,t[x].fa=fa; splay(x,rt); return; } nsrt(t[x].to[t[x].w<w],w,x); }

删除:把需要删除的节点Splay到根,然后将它的左子树合并到x的后继上,把右子树的父亲清零即可。

当然反过来把右子树合并到前驱也是可以的。或者和Treap一样把它Splay到叶子节点。

因为博主太菜没有做到需要删除的题目,没有代码。但是子树合并到前驱/后继上的代码还是有的: 见骗流量传送门里的tp/bttm。

区间操作

Splay当然可以维护区间啦!

建树

那么怎么把一个区间对应到Splay上呢?

首先, id[i] 表示位置i对应的节点编号。

设一个区间 [L,R] ,中间位置为mid,那么 [L,R] 就对应着以mid为根的子树。其中 [L,MID) 对应mid的左子树, (MID,R] 对应mid 的右子树。

这个对应的操作我们可以同线段树一样写一个build来实现。

void build(int l,int r,int fa){ if (l>r) return; int mid=(l+r)>>1,x=id[mid]; if (l==r){ t[x].mx=t[x].sum=a[l],t[x].t1=t[x].t2=0; t[x].l=t[x].r=max(a[l],0),t[x].sz=1; } build(l,mid-1,mid),build(mid+1,r,mid); t[x].w=a[mid],t[x].fa=id[fa]; t[id[fa]].to[mid>=fa]=x; }

查找区间

当我们需要找到 [L,R] 这个区间时,把L-1伸展到根,把R+1伸展到根的右节点,那么 [L,R] 这段区间就是R+1的左子树。

然后我们就可以进行各种区间操作了。

因为需要L-1和R+1,实际操作时我们要多建两个节点来应付 [1,n] 的操作。而0节点作为空节点,所以一般都把区间往右平移一格,虚拟节点即为1和n+2。

int srch(int x,int w){//寻找节点位置 int l=t[x].to[0]; if (t[l].sz+1==w) return x; if (t[l].sz>=w) return srch(l,w); return srch(t[x].to[1],w-t[l].sz-1); } int sprt(int l,int r){//把[l,r]分离出来 int p=srch(rt,l),q=srch(rt,r+2); //因为平移过,所以l-1变成l,r+1变成r+2 splay(p,rt);splay(q,t[p].to[1]); return t[q].to[0];//返回r+1的左子树 }

区间各种奇怪操作

有了查找区间这个操作后,我们就可以搞很多事情。下面举一些例子:

插入一整段区间:先把这个区间建成一颗平衡树,找到需要插入的位置 [x,x+1] ,直接把根接到x+1的左子树上即可。

删除一整段区间:找到要删除的区间,把R+1的左子树直接清零

区间翻转:这个操作比较典型。翻转区间就是交换mid的左右子树。然而我们不可能一次性把所有的mid都换一遍。所以我们可以把需要翻转的区间打个Tag,然后不断下传Tag即可。

当然区间操作远远不止这些,可以根据需要记录一些东西来实现。

以上操作的代码见这里的nsrt/dlt/rvrs

转载请注明原文地址: https://www.6miu.com/read-1400059.html

最新回复(0)