关于splay的一些基础操作
本文最后修改于 766 天前，部分内容可能已经过时！
BST详解，splay基本操作介绍
本蒟蒻最近不久前刚学splay，就写篇博客加强理解这是本蒟蒻第一次写博客
预备知识
首先，你需要知道什么是二叉查找树(BST)
首先观察一下下面这棵树
这图怎么那么丑
可以发现，结点值是从左往右依次递增的
也就是左儿子小于根节点小于右儿子
左子树的节点一定小于自身节点一定小于右子树的节点
而且BST里是不会有同一个节点不同位置的
只会在一个节点上记录出现次数
这棵树可以干很多很方便的事
比如查找前驱（比x小的最大的数是x的前驱），后继（同理），第k大的数，数在整个数列的排名。
BST都可以很完美的做到。
下面开始详细介绍下BST。
所需变量
每个节点所需要的变量有
size（子树（包括自己）的大小),
s[2] (s[0]是左儿子，s[2]是右儿子)，
f(父亲)，
v(值)，
cnt(次数)。
为了方便，本蒟蒻习惯使用struct
代码如下
struct BST
{
int f,s[2],v,cnt,size;
}e[Max];插♂入
假设我们要插入的数是19
首先从根节点开始往下查找
先和根节点比较，发现19 < 25
我们就把19扔到左边
如下图
发现左边有节点
再拿19和13比较，发现19>13
我们就把19扔到右边
然后继续和17比，被扔到右边
最后和21比，扔到右边，发现右边没有节点了，就再这个地方新建一个节点并连接到21的左边作为21的左儿子
接下来上代码
void insert(int v)
{
int u=root,f=0;//f为u的父亲
while(u&&e[u].v!=v)//寻找合适位置
{
e[u].size++;
f=u;
u=e[u].s[v>e[u].v];
//这里利用了返回值，如果x小于当前值返回0，大于返回1
}
//找到了
if(u) e[u].cnt++;//当前已经有这个值了，那么cnt++
else//否则新建一个节点
{
u=++cnt;
if(f) e[f].s[v>e[f].v]=u;//同理，建立父子关系
e[u].s[0]=e[u].s[1]=0;
e[u].f=f;
e[u].size=1;
e[u].cnt=1;
e[u].v=v;
}
}写博客真累啊orz，写了一晚上才写了一个插入。
删除
删除很简单，直接找到位置让他父亲断掉关系就好233
放到splay再说
查询！
1.找前驱和后继
前驱
我们接着上面的图继续讲，假如我们要找的是30的前驱
30的前驱是小于30的最大的数
还是从根开始
首先根比25大，我们把30下放到右儿子，并记录前驱25
继续和当前节点27对比，发现比27大，继续下放到右儿子，就记录27，发现27>25，就用27代替25
我们发现30小于当前节点31，就把下放到左儿子
最后发现30比29大，就记录29，发现29>27，所以用29代替27，并且当前节点没有右儿子了，于是前驱就搜索完毕，30的前驱就是29。
后继
后继和前驱差不多，所以就懒的讲了2333其实是作者懒，鸽了
代码
前驱：
int GetPre(int pos,int v,int ans)
{
if (e[pos].v>=v)
{
if (e[pos].s[0]==0)
{
return ans;
}
else
{
GetPre(e[pos].s[0],v,ans);
}
}
else
{
if (x[pos].s[1]==0)
{
if (x[pos].v<v)
{
return x[pos].v;
}
else
{
return ans;
}
}
if (x[pos].cnt!=0)
{
return GetPre(x[pos].s[1],v,x[pos].v);
}
else
{
return GetPre(x[pos].s[1],v,ans);
}
}
}后继：
后继和前驱差不多反正splay都不这样写，不看代码都行
2.找排名为k的数和查询数的排名
找排名为k的数：
这个实现需要用到size。
（咕咕咕，施工中