[学习笔记] 浅谈splay

前言

本篇博客只是对于 \(splay\) 思路和代码的简单介绍，主要是讲解代码

id

bool id(int x){return ch[fa[x]][1]==x;}//返回x是它父亲的哪个儿子

connect

void connect(int x,int y,bool son){fa[x]=y,ch[y][son]=x;}//把y的左/右儿子更新成x

upd

当节点的位置或者个数发生改变时，就要调用这个函数来改变子树大小

void upd(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}

rotate

旋转是 \(splay\) 最基本的操作，通过模拟+总结可以得出：

  1. \(X\) 变到原来 \(Y\) 的位置（两个节点位置互换）

  2. \(Y\) 变成了 \(X\) 原来在 \(Y\) 的 相对的那个儿子（ \(X\) 原来是 \(Y\) 的左节点那么变换之后 \(Y\) 就是 \(X\) 的右节点）

  3. \(Y\) 的非 \(X\) 的儿子不变 \(X\) 的 \(X\) 原来在 \(Y\) 的 那个儿子不变（最大和最小的两个节点不变）

  4. \(X\) 的 \(X\) 原来在 \(Y\) 的 相对的 那个儿子 变成了 \(Y\) 原来是 \(X\) 的那个儿子（\(X\) 剩下的儿子给 \(Y\)，也可以理解为

    和 \(Z\) 和 \(Y\) 相对大小相同的点，\(Y\) 是大的节点，小的就不用改了，应该改变大的）

所以一共只需要变换 \(4\) 个节点，位置变化了的只有 \(3\) 个

void rotate(int x){//将x旋转到父亲的位置
    int y=fa[x],fy=fa[y],fyson=id(y),yson=id(x),z=ch[x][yson^1];
    connect(x,fy,fyson),connect(y,x,yson^1),connect(z,y,yson);
    upd(y),upd(x);
}

splay

这里要注意一下，我们需要进行双旋操作，不然会存在有一条链仍然存在的清况导致超时

每次都要旋转 \(x\) 节点，只有 \(x,y\) 在一条链的情况下才要两个都旋转

void splay(int x,int p){//双旋到p的儿子节点
    for(int y;(y=fa[x])!=p;rotate(x))
	if(fa[y]!=p&&id(x)==id(y)) rotate(y);
    if(!p) root=x;//如果旋转到了根节点就要改变一下root
}

find

类似于二分查找，大了就往左，小了就往右

找到了之后就把它 \(splay\) 到根节点，方便接下来的操作

void find(int x){//查找x的位置，并旋转到根节点
    int u=root;
    while(ch[u][x>val[u]]&&val[u]!=x) u=ch[u][x>val[u]];
    splay(u,0);
}

insert

类似于 \(find\) 的查找方式，查找过程中记录父亲节点，如果找到了就直接计数，如果没找到就新开一个节点

插入之后必须要 \(splay\) 因为我们改变了树的结构，要把当前位置移动到根，把保证平衡，改变了子树大小，

所以要进行 \(splay\) 的 \(upd\) 操作

void insert(int x){//插入x
    int u=root,father=0;
    while(u&&x!=val[u]) father=u,u=ch[u][x>val[u]];
    if(!u){
	u=++tot;
	fa[u]=father;if(father) ch[father][x>val[father]]=u;//判断非根节点的情况
	siz[u]=cnt[u]=1;
	val[u]=x;
    }
    else ++cnt[u];
    splay(u,0);//must
}

rank

查找一个数的排名，先找到它的位置然后 \(splay\) 到根节点，这样就能让左子树全是小于它的，由于这个数可能本

来是不存在的，所以要和根节点判一下，注意要 \(+1\)

int Rank(int x){
    find(x);
    return siz[ch[root][0]]+(x>val[root]?cnt[root]:0)+1;
}

kth

查找排名第 \(k\) 大的数，注意最后要加 \(1\) ，因为我们多插入了一个 \(-inf\) 节点

从根节点开始找，然后比较大小关系

int kth(int x){
    int u=root;
    if(siz[u]siz[y]+cnt[u]) x-=siz[y]+cnt[u],u=ch[u][1];//查找的数在右儿子
	else if(siz[y]>=x) u=y;//如果左子树的个数更大，就往左子树找
	else return val[u];//否则就是当前节点
    }
}

preornxt

先是找到这个数的位置，然后转到根节点

有两种情况需要特判解决：

  1. 如果当前节点的值大于x并且要查找的是后继

  2. 如果当前节点的值小于x并且要查找的是前驱

直接返回 \(u\) 就行了

然后就按 \(BST\) 的查找方式就行了

int preornxt(int x,int flag){
    find(x);
    int u=root;
    if((val[u]x&&flag)) return u;
    u=ch[u][flag];//先往同方向走
    while(ch[u][!flag]) u=ch[u][!flag];//然后就是反着走
    return u;
}

del

先找前驱和后继，然后把前驱转到根节点，后继转到根节点的子结点

然后后继的左儿子就是小于后继大于前驱的数了，显然是我们要删除的数

void del(int x){
    int pre=preornxt(x,0),nxt=preornxt(x,1);
    splay(pre,0),splay(nxt,pre);
    int u=ch[nxt][0];
    if(cnt[u]>1) --cnt[u],splay(u,0);//节点数发生了改变
    else ch[nxt][0]=0;//直接丢弃这个节点
}
A——算法学习笔记数据结构——splay

相关

标签