前置：二叉查找树

在二叉查找树上做许多操作都十分方便。然而递归树的层数意味着时间复杂度为树高级别。当树是链状时，时间复杂度会退化。各类平衡树的存在大都为了使二叉查找树“平衡”，即高度不会超过 \(\log n\)（\(n\) 为树的结点个数）。如此以来，在二叉查找树上的操作就有了时间复杂的的保证。

splay 伸展树

平衡树的一种。splay 通过保证树的有序性的前提下的旋转来完成操作 & 保证树的平衡。

基本操作

1.左旋（zag）

设要左旋的节点为 \(x\)，其父亲节点为 \(y\)。则一次左旋操作会造成以下影响：

1. 将 \(y\) 设为 \(x\) 的右儿子。
2. 将 \(x\) 的原右儿子设为 \(y\) 的左儿子。

2.右旋（zig）

与左旋相反。将 \(x\) 左旋后的树的右旋后的结果即为原树。

1. 将 \(y\) 设为 \(x\) 的左儿子。
2. 将 \(x\) 的原左儿子设为 \(y\) 的右儿子。

code：

void zig(node *x)
{
	node *y=x->fa;
	node *z=y->fa;
	y->lson=x->rson;
	if(x->rson!=null)
		x->rson->fa=y;
	update(y);
	x->rson=y;
	y->fa=x;
	update(x);
	x->fa=z;
	if(z!=null)
	{
		if(z->lson==y)z->lson=x;
		if(z->rson==y)z->rson=x;
	}
}
void zag(node *x)
{
	node *y=x->fa;
	node *z=y->fa;
	y->rson=x->lson;
	if(x->lson!=null)
		x->lson->fa=y;
	update(y);
	x->lson=y;
	y->fa=x;
	update(x);
	x->fa=z;
	if(z!=null)
	{
		if(z->rson==y)z->rson=x;
		if(z->lson==y)z->lson=x;
	}
}

左旋 / 右旋后的树依旧满足二叉搜索树的性质。可手动模拟确认。

核心操作

伸展操作 \(\texttt{splay(x,s)}\)

\(\texttt{splay(x,s)}\) 的含义是：将 \(x\) 结点旋转至 \(s\) 的儿子节点的位置。当 \(s=0\) 时，将 \(x\) 旋转至根节点。

实现：设当前 \(x\) 的父亲是 \(y\)，\(y\) 的父亲是 \(z\)。

情况一：\(y=s\)。即 \(x\) 的父亲即为目标，当 \(x\) 为 \(y\) 的左儿子，进行一次 zig 操作。当 \(x\) 为 \(y\) 的右儿子，进行一次 zag 操作。

则 \(\texttt{splay(x,s)}\) 完成。

情况二：\(y≠s\)，且 \(x\) 与 \(y\) 皆为其父亲的左 / 右儿子，则进行 zig-zig （即两次右旋）操作或 zag-zag （即两次左旋）操作。

情况三：\(y≠s\)，且 \(x\) 与 \(y\) 一个为父亲的左儿子，一个为父亲的右儿子。当 \(x\) 为 \(y\) 的左儿子且 \(y\) 为 \(z\) 的右儿子，则进行 zig-zag 操作。当 \(x\) 为 \(y\) 的右儿子且 \(y\) 为 \(z\) 的左儿子，则进行 zag-zing 操作。

code：（细节自行参悟）

void splay(node *x,node *aim)
{
	while(x->fa!=aim)
	{
		node *y=x->fa;
		node *z=y->fa;
		bool p1=(x==y->lson);
		bool p2=(y==z->lson);
		if(z==aim)
		{
			if(p1)zig(x);
			else zag(x);
		}
		else
		{
			if(p1&&p2)zig(y),zig(x);
			if((!p1)&&(!p2))zag(y),zag(x);
			if(p1&&(!p2))zig(x),zag(x);
			if((!p1)&&p2)zag(x),zig(x);
		}
	}
	if(x->fa==null)root=x;
}

基于核心操作的扩展操作

在这里进行概念的一个明确：splay 所依靠的二叉搜索树可以以下标 / 权值为关键字，这样有不同的效果。然而大部分二叉搜索树以权值为关键字。

前驱

寻找小于 \(x\)，且最大的数。从根节点开始遍历，如果当前节点的值小于要查找的值，则往右子树遍历。否则往左子树遍历。

code：

node* pred(int val,node *now,node *opt)
{
	if(now==null)return opt;
	if(now->val<val)
		return pred(val,now->rson,now);
	return pred(val,now->lson,opt);
}

后继

寻找大于 \(x\)，且最小的数。从根节点开始遍历，如果当前节点的值大于要查找的值，则往左子树遍历。否则往右子树遍历。

code：

node* succ(int val,node *now,node *opt)
{
	if(now==null)return opt;
	if(now->val>val)
		return succ(val,now->lson,now);
	return succ(val,now->rson,opt);
}