Splay

Splay 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链，它由 Daniel Sleator 和 Robert Tarjan 发明。

下面的代码可以通过模板题 Luogu P3369。

结构

二叉搜索树的性质

左子树任意节点的值 < 根节点的值 < 右子树任意节点的值

节点维护信息

• $root$：根节点编号
• $total$：节点个数
• $fa[i]$：$i$ 的父亲
• $child[i][0]$：$i$ 的左节点
• $child[i][1]$：$i$ 的右节点
• $count[i]$：$i$ 的权值出现次数
• $size[i]$：以 $i$ 为根的子树的大小

操作

基本操作

• $maintain(a)$：在改变节点位置后，将节点 $a$ 的 $size$ 更新
• $get(a)$：判断节点 $a$ 是父亲节点的左儿子还是右儿子。
• $clear(a)$：销毁节点 $a$。

inline void maintain(int a){
	size[a]=size[child[a][0]]+size[child[a][1]]+count[a];
}
inline bool get(int a){
	return a==child[fa[a]][1];
}
inline void clear(int a){
	fa[a]=child[a][0]=child[a][1]=value[a]=count[a]=size[a]=0;
}

旋转操作

为了使 Splay 保持平衡而进行旋转操作，旋转的本质是将某个节点上移一个位置。

要求

• 整颗 Splay 的中序遍历不变。
• 受影响的节点维护的信息依然有效。
• $root$ 必须指向旋转后的根节点。

步骤

C++Copy
inline void rotate(int a){
	bool check=get(a);
	int b=fa[a],c=fa[b];
	child[b][check]=child[a][!check];
	fa[child[a][!check]]=b;
	child[a][!check]=b;
	fa[b]=a;
	fa[a]=c;
	if(c)child[c][b==child[c][1]]=a;
	maintain(b);
	maintain(a);
}

Splay 操作

Splay 规定：每访问一个节点后都要强制将其旋转到根节点。此时旋转操作具体分为 6 种情况讨论（其中 $a$ 为需要旋转到根的节点）

• 如果 $a$ 的父节点是根节点，直接将 $a$ 左旋或右旋。
• 如果 $a$ 的父节点不是根节点，且 $a$ 和父节点的儿子类型不同，首先将父节点左旋或右旋，然后将 $a$ 右旋或左旋。
• 如果 $a$ 的父节点不是根节点，且 $a$ 和父节点的儿子类型不同，将 $a$ 左旋再右旋或者右旋再左旋。

C++Copy
inline void splay(int a){
	for(int i=fa[a];i=fa[a],i;rotate(a))
		if(fa[i])
			rotate(get(a)==get(i)?i:a);
	root=a;
}

插入操作

如果要在 Splay 树中插入值为 $k$ 的节点，需要经过一下步骤：

• 如果树空了则直接插入根并退出。
• 如果当前节点的权值等于 $k$ 则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 Splay 操作。
• 否则按照二叉查找树的性质向下找，找到空节点并插入，最后进行 Splay 操作。

C++Copy
inline void ins(int k){
	if(!root){
		value[++total]=k;
		count[total]++;
		root=total;
		maintain(root);
		return;
	}
	int cnr=root,f=0;
	while(true){
		if(value[cnr]==k){
			count[cnr]++;
			maintain(cnr);
			maintain(f);
			splay(cnr);
			break;
		}
		f=cnr;
		cnr=child[cnr][value[cnr]<k];
		if(!cnr){
			value[++total]=k;
			count[total]++;
			fa[total]=f;
			child[f][value[f]<k]=total;
			maintain(total);
			maintain(f);
			splay(total);
			break;
		}
	}
}

查询 $k$ 的排名

根据二叉搜索树的定义和性质，显然可以按照以下步骤查询 $k$ 的排名：

• 如果 $k$ 比当前节点的权值小，向其左子树查找。
• 如果 $k$ 比当前节点的权值大，将答案加上左子树（$size$）和当前节点（$count$）的大小，向其右子树查找。
• 如果 $k$ 与当前节点的权值相同，将答案加 $1$，进行 Splay 操作并返回。

C++Copy
inline int rank(int k){
	int res=0,cnr=root;
	while(true){
		if(k<value[cnr])cnr=child[cnr][0];
		else{
			res+=size[child[cnr][0]];
			if(k==value[cnr]){
				splay(cnr);
				return res+1;
			}
			res+=count[cnr];
			cnr=child[cnr][1];
		}
	}
}

查询排名 $k$ 的数

设 $k$ 为剩余排名，具体步骤如下：

• 如果左子树非空且剩余排名 $k$ 不大于左子树的大小 $size$，那么向左子树查找。
• 否则将 $k$ 减去左子树和根的大小。如果此时 $k$ 的值小于等于 $0$，则返回根节点的权值，否则继续向右子树查找。

C++Copy
inline int kth(int k){
	int cnr=root;
	while(true){
		if(child[cnr][0]&&k<=size[child[cnr][0]])cnr=child[cnr][0];
		else{
			k-=count[cnr]+size[child[cnr][0]];
			if(k<=0){
				splay(cnr);
				return value[cnr];
			}
			cnr=child[cnr][1];
		}
	}
}

查询前驱

$a$ 的前驱可以转化为：$a$ 的左子树中最右边的节点，求法如下：

C++Copy
inline int pre(){
	int cnr=child[root][0];
	while(child[cnr][1])cnr=child[cnr][1];
	splay(cnr);
	return cnr;
}

查询后继

$a$ 的后驱可以转化为：$a$ 的右子树中最左边的节点，求法如下：

C++Copy
inline int next(){
	int cnr=child[root][1];
	while(child[cnr][0])cnr=child[cnr][0];
	splay(cnr);
	return cnr;
}

合并操作

合并两棵 Splay 树，设两棵树的根节点分别为 $a$ 和 $b$，那么我们要求 $a$ 树中的最大值小于 $b$ 树中的最小值。删除操作如下：

• 如果 $a$ 和 $b$ 其中之一或两者都为空树，直接返回不为空的那一棵树的根节点或空树。
• 否则将 $a$ 树中的最大值 splay 到根，然后把它的右子树设置为 $b$ 并更新节点的信息，然后返回这个节点。

删除操作

删除操作步骤如下：

• 将 $a$ 旋转到根的位置。
• 如果 $count[a]>1$（有不止一个 $a$），那么将 $count[a]$ 减 $1$ 并输出。
• 否则，合并它的左右两棵子树即可。

C++Copy
inline void del(int k){
	rank(k);
	if(count[root]>1){
		count[root]--;
		maintain(root);
		return;
	}
	if(!child[root][0]&&!child[root][1]){
		clear(root);
		root=0;
		return;
	}
	if(!child[root][0]){
		int cnr=root;
		root=child[root][1];
		fa[root]=0;
		clear(cnr);
		return;
	}
	if(!child[root][1]){
		int cnr=root;
		root=child[root][0];
		fa[root]=0;
		clear(cnr);
		return;
	}
	int cnr=root;
	int x=pre();
	splay(x);
	fa[child[cnr][1]]=x;
	child[x][1]=child[cnr][1];
	clear(cnr);
	maintain(root);
}

完整代码

数组实现

提交记录 备份

结构体指针实现

如果写挂了，询问自己：

1. 输入的数字 包含负数，我用的快读判断了负数吗？
2. 对于使用指针的实现，如何处理空指针？是否避免了访问 NULL？有没有特别地清空初始的空节点？
3. 插入的时候，假设当前节点是 $u$，我们要 maintain(u)，也要 maintain(u->fa)！
4. 每次操作后，都要进行 splay 操作！对于其他的平衡树题目（尤其是树套树），求 rank 的时候可能存在不存在的情况，那时候也要 splay！
5. rotate 操作的细节是否正确？

提交记录 备份

例题

参考资料

• Splay - OI Wiki
• 【随笔浅谈】splay 时间复杂度简要分析 - Calculatelove - 博客园（有纰漏）
• Splay Trees（英文版，时间复杂度的严谨证明）