关于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。
(咕咕咕,施工中