关于splay的一些基础操作

Baka 2018年08月19日 •  C++ NOIP 数据结构与算法 编程 5426 •  0
本文最后修改于 680 天前,部分内容可能已经过时!

BST详解,splay基本操作介绍

本蒟蒻最近不久前刚学splay,就写篇博客加强理解
这是本蒟蒻第一次写博客

预备知识

首先,你需要知道什么是二叉查找树(BST)

首先观察一下下面这棵树
1.png
这图怎么那么丑
可以发现,结点值是从左往右依次递增的
也就是左儿子小于根节点小于右儿子
左子树的节点一定小于自身节点一定小于右子树的节点
而且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
2.png
首先从根节点开始往下查找
先和根节点比较,发现19 < 25
我们就把19扔到左边
如下图
3.png
发现左边有节点
再拿19和13比较,发现19>13
我们就把19扔到右边
4.png
然后继续和17比,被扔到右边
5.png
最后和21比,扔到右边,发现右边没有节点了,就再这个地方新建一个节点并连接到21的左边作为21的左儿子
6.png
接下来上代码

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的最大的数
还是从根开始
7.png
首先根比25大,我们把30下放到右儿子,并记录前驱25
8.png
继续和当前节点27对比,发现比27大,继续下放到右儿子,就记录27,发现27>25,就用27代替25
9.png
我们发现30小于当前节点31,就把下放到左儿子
10.png
最后发现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。
(咕咕咕,施工中

Tags:splayoinoip信息学奥赛
上一篇
下一篇

添加新评论

0:00