Splay详解(一)

前言

Spaly是基于二叉查找树实现的,

什么是二叉查找树呢?就是一棵树呗:joy: ,但是这棵树满足性质—一个节点的左孩子一定比它小,右孩子一定比它大

比如说

这就是一棵最基本二叉查找树

对于每次插入,它的期望复杂度大约是logn级别的,但是存在极端情况,比如9999999 9999998 9999997.....1这种数据,会直接被卡成n^2

在这种情况下,平衡树出现了!

Splay简介

Splay是平衡树的一种,中文名为伸展树,由丹尼尔·斯立特Daniel Sleator和罗伯特·恩卓·塔扬Robert Endre Tarjan在1985年发明的(mmp怎么又是tarjan)

它的主要思想是:对于查找频率较高的节点,使其处于离根节点相对较近的节点

这样就可以保证了查找的效率

那么现在问题来了:

  • 什么样的点是查找频率高的点?

这个玩意儿确实不好统计,但是你可以认为每次被查找的点查找频率相对较高,说白了就是你把每次查找到的点搬到根节点去

当然你也可以每次查找之后随机一个点作为根,于是Treaplay这种数据结构就诞生啦

  •  怎么实现把节点搬到根这种操作?

这也是Splay这种数据结构所要实现的功能,接下来我们详细的介绍一下

Splay基本操作

rotate

首先考虑一下,我们要把一个点挪到根,那我们首先要知道怎么让一个点挪到它的父节点

情况1

当X是Y的左孩子

这时候如果我们让X成为Y的父亲,只会影响到3个点的关系

B与X,X与Y,X与R

根据二叉排序树的性质

B会成为Y的左儿子

Y会成为X的右儿子

X会成为R的儿子,具体是什么儿子,这个要看Y是R的啥儿子

经过变换之后,大概是这样

情况2

当X是Y的右孩子

本质上和上面是一样的,

变换后为

这两种代码单独实现都比较简单,我就不写了(实际上是我懒)

但是这两种旋转情况很类似,第二种情况实际就是把第一种情况的X,Y换了换位置

我们考虑一下能不能将这两种情况合并起来实现呢?

答案是肯定的

首先我们要获取到每一个节点它是它爸爸的哪个孩子,可以这么写

bool ident(int x)
{
    return tree[tree[x].fa].ch[0]==x?0:1;
}

如果是左孩子的话会返回0,右孩子会返回1

那么我们不难得到R,Y,X这三个节点的信息

    int Y=tree[x].fa;
    int R=tree[Y].fa;
    int Yson=ident(x);//x是y的哪个孩子
    int Rson=ident(Y);

B的情况我们可以根据X的情况推算出来,根据^运算的性质,0^1=1,1^1=0,2^1=3,3^1=2,而且B相对于X的位置一定是与X相对于Y的位置是相反的

(否则在旋转的过程中不会对B产生影响)

int B=tree[x].ch[Yson^1];

然后我们考虑连接的过程

根据上面的图,不难得到

B成为Y的哪个儿子与X是Y的哪个儿子是一样的

Y成为X的哪个儿子与X是Y的哪个儿子相反

X成为R的哪个儿子与Y是R的哪个儿子相同

    connect(B,Y,Yson);
    connect(Y,x,Yson^1);
    connect(x,R,Rson);

connect函数这么写,挺显然的

void connect(int x,int fa,int how)//x节点将成为fa节点的how孩子
{
    tree[x].fa=fa;
    tree[fa].ch[how]=x;
}

单旋函数就是这样了,利用这个函数就可以实现把一个节点搬到它的爸爸那儿了,

Splay

Splay(x,to)是实现把x节点搬到to节点

最简单的办法,对于x这个节点,每次上旋直到to

但是!

如果你真的这么写,可能会T成SB,出题人可能会构造数据把单旋卡成$n^2$,不要问我为什么!(其实是我不知道)

下面我们介绍一下双旋的Splay

这里的情况有很多,但是总的来说就三种情况

1.to是x的爸爸,

这样的话吧x旋转上去就好

update in 2018.2.19 这里可能写错了一个地方(其实也没有写错) 因为我们在双旋的时候会改变三个点的关系,为了方别写,所以我们开始的时候把to设置为to的爸爸

if(tree[tree[x].fa].fa==to) rotate(x);

2.x和他爸爸和他爸爸的爸爸在一条线上

这时候先把Y旋转上去,再把X旋转上去就好

else if(ident(x)==ident(tree[x].fa)) rotate(tree[x].fa),rotate(x);

3.x和他爸爸和他爸爸的爸爸不在一条线上

这时候把X旋转两次就好

总的代码:

void splay(int x,int to)
{
    to=tree[to].fa;
    while(tree[x].fa!=to)
    {
        if(tree[tree[x].fa].fa==to) rotate(x);
        else if(ident(x)==ident(tree[x].fa)) rotate(tree[x].fa),rotate(x);
        else rotate(x),rotate(x);
    }
}

后记

至此,Spaly的最核心最基本的操作已经讲解完毕

至于这玩意儿怎么用,以及能实现什么功能,且听下回分解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

“玲珑杯”ACM比赛 Round #19题解&源码【A,规律,B,二分,C,牛顿迭代法,D,平衡树,E,概率dp】

A -- simple math problem Time Limit:2s Memory Limit:128MByte Submissions:1599Sol...

3395
来自专栏小樱的经验随笔

看破欧拉函数的奥秘

注意以下三个特殊性质 编程实现   利用欧拉函数和它本身不同质因数的关系,用筛法计算出某个范围内所有数的欧拉函数值。 1 //直接求解欧拉函数 ...

35110
来自专栏温安适的blog

贪婪算法-单源最短路径

3905
来自专栏数据结构与算法

BZOJ3624: [Apio2008]免费道路(最小生成树)

这棵树上有一些0边是必须要选的,我们先把他们找出来,如果数量$\geqslant k$显然无解

933
来自专栏生信技能树

第2篇:原始数据的质控、比对和过滤

首先对拿到的原始测序数据(fastq或fastq.gz格式)进行质控检测,直接用fastqc软件,再加上multiqc将多个检测结果一起展示。 如:

5403
来自专栏HansBug's Lab

3224: Tyvj 1728 普通平衡树

3224: Tyvj 1728 普通平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2566  Sol...

3576
来自专栏数据结构与算法

Link-Cut-Tree(LCT)详解

2930
来自专栏锦小年的博客

python学习笔记6.7-简化数据结构的初始化过程

我们每编写一个类的时候都需要编写一个初始化函数,那么如果编写的类当做数据结构来用,它们的初始化结构就是一样的,例如: class Stock: def ...

2176
来自专栏大闲人柴毛毛

贪心算法(三)——最佳合并模式

问题描述 给定n个有序文件,每个文件的记录数分别为w1~wn,请给出一种两两合并的方案,使得总合并次数最少。 注意: 1. 外排序算法是将多个有序文件合...

42310
来自专栏数据结构与算法

09:LGTB 学分块

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB描述 LGTB 最近在学分块,但是他太菜了,分的块数量太多他就混乱...

3517

扫码关注云+社区

领取腾讯云代金券