从二叉搜索树到 Splay

从堆到二叉搜索树

引言

考虑你需要维护一个数据结构，需要进行以下若干操作：

• 添加一个值 value
• 删除一个值 value
• 查询值 value 的排名
• 查询排名为 rank 的值
• 求值 value 的前驱和后继

显然，如果只需要进行添加操作、查询最大值（最小值），只需要用一个二查堆，就可以解决。如果外加删除操作，则可以开启懒惰标记进行删除。整体复杂度是 $\operatorname{O}{(\log n)}$ 的。

堆的特性是根的节点的值比左右子树的都要大，于是我们扩展了一下，就可以变成二叉搜索树：对于某个节点 $i$ ，他的值 $data_i$ 大于左儿子节点的值，小于右儿子节点的值。

二叉搜索树

维护这样一个二叉搜索树，如下图：

$\color{red}\text{添加：}$

考虑我们需要添加一个数，比如 $25$。

首先我们应该找到 $25$ 应该放在哪里，所以从根节点出发，遵循二叉搜索树左儿子小于根节点（右儿子大于根节点）的原则，因为要添加的数字 $<41$ 所以来到左边，同理因为 $25>20$ 所以跳到 $20$ 右儿子，又因为 $25<29$，我们得出 $25$ 在 $29$ 左子树上。

因为 $29$ 没有左儿子，所以可以在这里新建一个节点。也就是添加完变成了这样（用颜色高亮标记了走过的点）：

当然如果我插入一个已经存在的树，可以记录每个数出现的次数，更为方便。

可以得出添加操作的伪代码如下：

void add(int x){
    int u = root ;
    while true :
        if 找到要填的地方 :
            添加节点（新建节点，更新 u 和新节点关系等）;
            return ;
        if x< 当前这个点的值
            u = u 的左儿子
        else :
            u = u 的右儿子
}

$\color{Goldenrod}\text{删除：}$

显然如果我要删除一个已经存在多个的数字，可以将这个数字出现的次数减去一。因此我们重点看要删的数字只出现一次的情况。

还是最开始给出的二叉搜索树的例子，假设我们要删除一个点，比如 $91$。

既然我要删除一个点，实际上就是找到这个点的位置，将其删除之后，更新它父亲和它的儿子的关系即可。所以我们应该重点考虑找到一个点。

对于 $91$ 而言，还是从根开始搜索，发现 $91>41$ ，所以往右子树走，进一步发现 $91>65$ ，还是往右子树走，此时我们发现找到 $91$ 了。

问题在于我们如果直接删掉它，$91$ 的两个儿子 $72$ 和 $99$ 就也跟着没有了。如果简单地将这两个节点直接连向 $65$，那么 $65$ 就有三个儿子，不符合二叉搜索树的定义了。真令人头秃

我们先假设如果 $91$ 只有一个儿子，那么是不是可以直接把这个儿子提到 $91$ 的位置呢？

当然可以，因为既然这个儿子在 $65$ 右子树内，则它一定大于 $65$，将其提到 $91$ 出无妨。

现在回头考虑多余的儿子，因为对于每个点 $i$，记它的左右儿子为 $left, right$，则一定有 $left<i<right$，也就是一定有 $left<right$ 了，那么可以将右儿子提到原来的位置，左儿子放到右儿子子树里就可以啦。

但如果右儿子下还有两个儿子，左儿子插不进去怎么办？这时候可以从右儿子往下找，向前面添加一个数一样找到一个合适的位置，把左儿子放进去即可。

因此删除 $91$ 的操作完成后，整个树会变成（注意加了一条 $99$ 和 $72$ 的连边）：

伪代码如下：

查找要删除的节点 v
if  v 是叶子节点 :
    直接删除
else if  v 有一个儿子 :
    删除 v ;
    将 v 的父亲连向 v 的儿子
else : 
   删除 v ;
   将 v 的父亲连向其右儿子
   在右子树内找到一个合适的位置添加左子树

$\color{Green}\text{查找一个数的排名（查询一个排名是什么数）：}$

还是最初的树，我们把他写成序列的形式（随机顺序）：

$[11,29,41,72,32,20,50,99,91,65]$

如果在这样的序列里来查找 $50$ 的排名，想必各位都会想到先排序，再数 $50$ 之前有几个数。但是考虑到这是一个二叉搜索树，大家有没有发现，比 $50$ 小的数不正好是 $41$ 的左子树（包括 $41$ ）吗？

为什么会出现这种情况呢？显然，因为二叉搜索树那最重要的定义：左儿子 $<$ 根 $<$ 右儿子，那么 $50$ 很显然小于 $65$，但大于 $41$。而 $41$ 左子树所有点均小于 $41$，那么 $50$ 很显然就比那些数大了。

因此得出一个结论：

• 如果我要查找的数字是某个右儿子，则它的父亲、左子树、以及其他这以左的所有点都比查找的数小，其右边所有的数都比其大。
• 如果我要查找的数字是某个左儿子，则它的父亲比他大，但其左儿子以及这以左的所有点比查找的树小，且这个点往上查找到的所有是右儿子的祖先（且不是父亲），它们的左子树比要查的点小，除此之外所有数都比其大。

根据这样的结论，我们可以得出什么呢？不难发现，我如果要查询某个数值的排名，可以通过查询比他小的数有几个得到，而查询比他小的数有几个，可以通过查询子树大小得到。

因此如果我们进一步维护各个点的子树，就可以简单解决这类问题。确切地说：从根节点跳到这个点，过程中累加到达的点的左子树大小，最后再加上到达的点的个数，答案就是这个数的排名（这段话应该可以代替伪代码了吧……）。

现在考虑已经知道了一个数的排名 $rank$，需要查找排名为 $rank$ 的数字是多少。举个例子（和前面一样的例子）：

$[11,29,41,72,32,20,50,99,91,65]$

现在我们来查找排名为 $7$ 的数字是哪个。你的第一反应是不是还是从小到大排序地找，直到找出了第七个？

正如前文所述，找出一个点前面有几个点比他小，完全可以通过查找子树大小，然后通过一顿操作解决这类问题。结合上文的结论可以发现这样一个算法：

我们要查找排名为 $k$ 的数，其实可以转换为查找按照前文两个结论得出的数字个数恰好为 $k-1$ 的数是哪个。因此从根节点出发，读取这个点左子树的节点个数。如果大于（或等于）$k$，那么我们需要往左子树走，反之，需要往右子树走，并实时记得更新（ $k$ 需要减去左子树大小与 $1$ 的和，这个 $1$ 表示我要找的这个点不是现在到达的这个点）。

$\color{CornflowerBlue}\text{查找一个数的前驱（或后继）：}$

前驱定义：$x$ 的前驱为比 $x$ 小的数中，最大的那个
后继定义：$x$ 的后继为比 $x$ 大的数中，最小的那个

我们进一步探究整个二叉搜索树。

首先来看前驱。根据二叉搜索树的性质，首先我要找的前驱比这个数字要小，首先所有点的左儿子一定比他小，其次，如果这个数在右儿子，那它的父亲比它小；如果是一个左儿子，那么他左边（感性理解）的点的值也比他小。

进一步地发现，如果这个存在左儿子（左子树），那么先往左子树走一步，随后只走右边走到底（注意如果只有左边可以走了那也不要走了直接停），此时它的前驱就找到了。否则如果这个点是一个右儿子，其父亲就是它的前驱；如果是个左儿子，就一直往祖先跳，直到跳到一个是右儿子的祖先，这个祖先的父亲就是前驱（或者跳到根）。

反过来，我们来看看后继。和前驱几乎一样的道理，只是反过来了而已。那么同理就有如下做法：

从要查找的点出发，如果可以往右走，那么先往右儿子走一步，随后只走左边走到底（注意如果只有右边可以走了那也不要走了直接停），此时它的后继就找到了。否则如果这一个点是一个左儿子，其父亲就是它的后继；如果是个右儿子，就一直往祖先跳，直到跳到一个是左儿子的祖先，这个祖先的父亲就是后继（或者跳到根）。

（想必各位发现这就是复制粘贴然后把方向反了，不过本来就是这样）

至此就是二叉搜索树的六大操作哩~

从二叉搜索树到平衡树

如果你在阅读完上述部分之后认为自己完全理解了，那么恭喜你！但是我还是要泼一盆冷水：这样的二叉搜索树是非常低效的。下面将简单分析按照上述方法维护的二叉搜索树的复杂度。

普通二叉搜索树的复杂度分析

空间方面：显然二叉搜索树对于每一次加点，都会新创建一个节点。因此空间复杂度和新建节点的个数是同级的，换句话说假设操作数是 $m$（如果题目明确提及了加节点的次数，那么也可以认为 $m$ 代表加点的次数），最坏情况下每一次操作都加一个节点。空间复杂度是 $\operatorname{O}{(m)}$ 的。

更确切地说，我们对于一个节点，维护了它的父亲、左儿子、右儿子、代表的数字、这个数字出现的次数、子树大小。一共 $6$ 个元素。因此它的空间复杂度是 $\operatorname{O}{(6m)}$ 的。（当然一般还要开变量记录节点个数，甚至特殊题目也还要更多东西，不过这里均未考虑）

重点来看 时间方面 ：

对于前面的任何一个操作，最坏情况下我需要从根跑到叶子（或叶子跑到根），我们记树的节点个数是 $n$，树高是 $h$，一共有 $m$ 次操作，一次操作的复杂度是 $\operatorname{O}{(h)}$ 的。

在最优情况下，二叉搜索树会形成一颗完全二叉树（甚至满二叉树），如下图

我们发现在满二叉树的情况下，树高 $h$ 是 $\log n$ 级别的。每一次操作只需要 $\log n$ 的时间复杂度就可以完成。整体复杂度是 $\operatorname{O}{(m\log n)}$，听起来是个很完美的数字了，即使 $n=m=10^5$，它也可以轻松跑过。

但是最坏情况下，假设我的树最开始是空的，然后依次加入 $10,9,8,...,3,2,1$ ，整个树就会长成这个样子：

每一次操作最坏都要从 $10$ 跑到 $1$ （或从 $1$ 跑到 $10$），换句话说树退化成了链，树的高度退化成了 $n$，整体复杂度退化为了 $\operatorname{O}{(nm)}$，放在 $n=m=10^5$ 的数据下，直接 TLE ，而且被卡得死死的。

Splay 引入

为了解决这样一个问题，避免这种传统的二叉搜索树被极端数据卡飞，换句话说，我们要构造一颗始终“平衡”的树，使得树高总是等于或一直趋近与 $\log n$ 级别。为此珂学家们进行了无数研究探讨。其中 Tarjan 提出了一个不错的想法：构造一个伸展树。

所谓 伸展树，就是接下来要讲解的 Splay。当然平衡树的实现不仅仅有 Splay，但是因为 Spaly 是本文的压轴主题，带有神圣的主角光环，所以我们只将 Spaly 而暂时舍弃别的平衡树。

首先把话放在前头，因为平衡树也是二叉搜索树的一种，所以平衡树的六大操作基本和朴素的二叉搜索树一致。而 Tarjan 提出了将一组节点“旋转”的方法，控制了树的平衡。我们要保证查询的点尽可能离根更近，因此，我们可以简单地假设：现在查到的这个点就是经常容易被查到的点，不管后面查没查过提到根就对了。

这句话听起来十分玄乎，因此还是具体地分析一下“旋转”到底如何进行。

Splay 基本操作：旋转

单旋

既然要把一个节点提到根，我们首先考虑怎么把这个节点移到它父亲的位置上，假设某一个平衡树构造是这样的，其中 $x,y,z$ 是三个节点，$A,B,C,D$ 代表着四个子树的根，也就是 $x$ 的两个儿子、$y,z$ 的左儿子。

归纳一下这七个点之间的数量关系，得到 $D<z<C<y<B<x<A$。

现在我们进行了一次单旋操作，将 $x$ 的位置变到了 $y$ 这里，但是我们还是要满足上述的大小关系。

• 首先 $x,y$ 的关系颠倒了，又因为 $x>y>z$，因此 $x$ 连在 $z$ 的右儿子上，$y$ 在 $x$ 的左儿子上。
• 那么原本应该在 $x$ 左儿子上的 $B$ 应该去哪里呢？我们发现 $B>y$ 因此我们可以再将 $B$ 挂到 $y$ 的右儿子上。
• 此时 $x$ 的右儿子 $A$没变，$y$ 的左儿子 $C$ 没变，$z$ 的左儿子 $D$ 没变。整个树旋转一次后变成了这样：

检查一遍这棵树上七个点的数量关系，得到 $D<z<C<y<B<x<A$，与上文所述完全一致！说明我们现在已经成功地将 $x$ 往上移动到了它的父亲。

当然这只是其中的一种情况，如果我们根据左右儿子关系不同，可以分类讨论出非常多种可能，这些可能都有一些普遍的特点：

• 如果 $x$ 是 $y$ 的左儿子，则 $x$ 的左右儿子中要更新的点是右儿子；反之则为左儿子。（即二者相反）
• 如果 $x$ 是 $y$ 的左儿子，则 $y$ 应该更新为 $x$ 的右儿子；反之则为左儿子。（即二者相反）
• 如果 $y$ 是 $z$ 的左儿子，则 $x$ 应该更新为 $z$ 的左儿子；反之则为右儿子。（即二者相同）

整理一下思路，我们更新了三对关系：$x-y$ 的关系、$z-x$ 的关系、$y-B$ 的关系。注意因为二叉搜索树我们还记录了每个点的子树大小，所以还要实时更新子树大小！

数据存储：

struct dot{
	int size,cnt,data,son[2],fa;
    /* cnt 表示出现次数，size 表示以这个点为根的子树大小，data 表示节点存储的数值
    * son[0] 表示左儿子编号，son[1] 表示右儿子编号，fa 表示父亲节点编号
    */
	dot(){fa=size=cnt=data=son[0]=son[1]=0;} // 初始化，全部赋为 0
}a[max_n];
#define root a[0].son[1]
 // 为了方便把根节点设为 0 号点的右儿子，当然也可以设别的

前置函数：

inline int getson(int x){ // 确认 x 是左儿子还是右儿子
	return (a[a[x].fa].son[1]==x?1:0);
}
inline void connect(int u,int fa,int k){ 
// 建立一条边， u 的父亲是 fa，u 是 fa 的 k 儿子
// 后文将 k 儿子视为左/右儿子，其中 k=0 是左儿子，k=1 是右儿子
	a[u].fa=fa,
	a[fa].son[k]=u;
}
inline void resize(int u){ // 更新 u 节点的子树大小
// 显然，子树大小=左子树大小+右子树大小+自己这个数出现的次数
	int lsize=a[a[u].son[0]].size,rsize=a[a[u].son[1]].size;
	a[u].size=lsize+rsize+a[u].cnt;
}

单旋函数实现

inline void rotate(int x){// 将 x 旋转
	int y=a[x].fa,z=a[y].fa;
	int k=getson(x),p=getson(y);// 标记一下 x,y 分别是什么儿子

	connect(a[x].son[k^1],y,k), // k^1 刚好就是左变右，右变左inline void splay(int x,int to){
	to=a[to].fa;
	while(a[x].fa!=to){

		int y=a[x].fa,z=a[y].fa;
		int k=getson(x),p=getson(y);

		if(z==to) rotate(x);
		else if(k==p) rotate(y),rotate(x);
		else rotate(x),rotate(x);
	}
}
	connect(y,x,k^1),
	connect(x,z,p);

	resize(y),resize(x); // 注意要先更新 y 的子树大小
}

双旋

如果我们真的遇到一个退化成链的平衡树，现在我想把叶子节点提到根上来，可不可以不停地单旋完成呢？

如果你手推一下，就会发现，只进行单选操作并不能把链的数据“平衡”下来。因此我们需要一个双旋函数：一次旋转两次。

为此我们设计一个函数 $\operatorname{Splay}{(x,to)}$，表示将节点 $x$ 通过若干次单旋提到原本是节点 $to$ 的位置。注意不能一步一步单旋上去，不然树高没有减小，该退化的复杂度还是退化了。

如果我们先旋转一个点的父亲，然后再旋转这个点本身，不难得出在有些情况下是可以非常好的达到这个效果。根据手推，分类讨论只有三种情况：

1. $to$ 是 $x$ 的父亲，此时直接将 $x$ 转上去。
2. $x$ 和它父亲，以及它爷爷共线（举例： $x$ 是左儿子，$fa_x$ 也是左儿子），此时先旋转 $fa_x$，再旋转 $x$ 更优。
3. $x$ 和它父亲，以及它爷爷不共线（举例：$x$ 是右儿子，但 $fa_x$ 是左儿子），此时旋转两次 $x$ 更优。

当然为了方便判断，我们事先执行 $to_{fa} \rightarrow to$ ，以便在我记录 $x$ 的父亲 $y$ 和爷爷 $z$ 时，可以直接通过 $z=to$ 判断第一种情况，并方便地一次旋转两个点。

总的代码如下：

inline void splay(int x,int to){
	to=a[to].fa;
	while(a[x].fa!=to){

		int y=a[x].fa,z=a[y].fa;
		int k=getson(x),p=getson(y);

		if(z==to) rotate(x); // 第一种情况
		else if(k==p) rotate(y),rotate(x); // 第二种情况
		else rotate(x),rotate(x); // 第三种情况
	}
}

用 splay 实现普通二叉搜索树的功能

在执行添加删除等一堆函数前，我们可以先提前写好一些函数，如：查找数值为 $x$ 的点的编号、新建一个节点等。显然这些函数都比较有用，为了简化后续的复杂函数内容我们可以先码上。

前置函数

int tot=0; // 用 tot 记录有几个节点
inline int find(int x){ // 查找数值为 x 的点
	int u=root;
	while(1){
		if(!u) return 0; // 没有找到，返回 0
		if(a[u].data==x){ // 找到了这个点
			splay(u,root); // 把这个点提到根节点上，维持树平衡
			return u;
		}
		int k=(x>a[u].data?1:0),v=a[u].son[k]; // u 跳到左/右儿子
		u=v;
	}
}
inline int adnew(int data,int fa){
// 新建一个节点，数值为 data，父亲为 fa
	a[++tot].fa=fa; // 设置父亲节点
	a[tot].data=data; // 设置数值
	a[tot].cnt=a[tot].size=1; // 设置子树大小和出现次数
	return tot; // 为了方便，返回现在有几个点
}

主要函数

发现 Splay 的本质还是一个二叉搜索树，按照上文（很上面）所述的方法进行操作即可。但是值得注意的是，要在操作后将操作的这个点旋转到根的位置（后面代码中的 splay 函数都是这个道理），以此避免复杂度的退化。

最后上 Splay 的加注释版代码（含主要函数，其他函数也在上文均有出现）：

int inf=1000000005; // 赋无穷大的初值
inline void add(int x){ // 添加一个值为 x 的节点
	int u=root;
	if(!root){ // 如果树是空的
		root=adnew(x,0); // 新建一个根节点
		return;
	}
	while(1){
		++a[u].size; 
        // 添加一个点的一路上更新其他点子树大小
		if(a[u].data==x){ // 这个点已经出现过了
			++a[u].cnt; // 直接在次数上累加
			splay(u,root);
			return;
		}
		int k=(x>a[u].data?1:0),v=a[u].son[k]; 
        // 找到我要去哪个儿子
		if(!v){ 
        // 那个儿子还不存在，说明那里就是新节点应该在的位置
			int p=adnew(x,u);
			a[u].son[k]=v=p; // 更新父节点的儿子
			splay(p,root);
			return;
		}
		u=v; // 还没有找到，继续跳儿子
	}
}
inline void delet(int x){ // 删除（一个）数值为 x 的数字
	int u=find(x); // 找到这个数的编号
    // 注意 find 时已经将找到的点 splay 到根了
	if(!u) return; // 没找到，说明操作不合法
	if(a[u].cnt>=2){ // 这个点出现次数多于 1 次
		--a[u].cnt, // 直接减少出现次数即可
		--a[u].size; // 不要忘记更新子树大小
        /* 这里不更新其他点子树大小是因为
         * 要么这些点的子树大小没用过
         * 要么就会在别的地方 resize
         */
		return;
	}
	if(!a[u].son[1] && !a[u].son[0]){ // 没有儿子
    // 注意到 u 已经 splay 到根了，
    // 还没有儿子说明这是整个树中唯一的点
		root=0; // 清空整个树
		return;
	}
	if(!a[u].son[0]){ // 没有有左儿子
		root=a[u].son[1], // 将右儿子提到根
		a[root].fa=0;
		return;
	}
	int v=a[u].son[0];
	while(a[v].son[1]) v=a[v].son[1]; // 找到 u 的前驱
    // 将前驱变为新根可以更好地维护树平衡
	splay(v,a[u].son[0]);
	connect(a[u].son[1],v,1),
	connect(v,0,1);
	resize(v);
    // 维护新根和别的节点关系、子树大小
}
inline int getrank(int x){ // 查询 x 的排名
	int u=root,res=0; // 从根开始跳
    // res 记录比 x 小的数有几个，排名=res+1
	while(u){
		if(x<a[u].data){ // 往左儿子跳
			u=a[u].son[0];
			continue;
		}
		res+=a[a[u].son[0]].size;
		if(x==a[u].data){ // 找到了这个点
			splay(u,root);
			return res+1;  // 注意排名=res+1
		}
		res+=a[u].cnt, // 别忘了加上这个点的出现次数
		u=a[u].son[1]; // 往右儿子跳
	}
	return res+1; // 别忘了排名=res+1
}
inline int getnum(int x){ // 查找排名为 x 的数
	int u=root;
	while(1){
		int rank=a[u].size-a[a[u].son[1]].size;
        // rank 表示已经有那么多个数比现在的点小了
		if(x>a[a[u].son[0]].size && x<=rank){
            // 符合条件
            // 因为还要考虑 x 的出现次数所以不能直接判==rank
			splay(u,root);
			return a[u].data;
		}
		if(x<rank) u=a[u].son[0];
		else x-=rank,u=a[u].son[1];
        // 跳右儿子时，因为 rank 不是累加左子树得到，要更新 x
	}
}
inline int smaller(int x){ // 查找 x 的前驱
	int u=root,res=-inf; // 先给 res 赋无穷小
	while(u){
		if(a[u].data<x && a[u].data>res){
            // 找到一个点比 x 小，尝试更新答案
			splay(u,root);
			res=a[u].data;
		}
		if(x>a[u].data) u=a[u].son[1];
		else u=a[u].son[0];
        // 跳左/右儿子
	}
	return res;
}
inline int bigger(int x){ // 查找 x 的后继
	int u=root,res=inf;
	while(u){
		if(a[u].data>x && a[u].data<res){
			splay(u,root);
			res=a[u].data;
		}
		if(x<a[u].data) u=a[u].son[0];
		else u=a[u].son[1];
	}
	return res;
}// 基本与前驱同理