平衡树学习(2)——Splay_splay 博客-程序员宅基地

Splay是一种平衡树,它的代码复杂度和时间复杂度稍弱于Treap,但由于其可以支持区间操作,所以在实战中还是有许多用处。
我们先来看看Splay的定义和基本思路。

伸展树(Splay Tree),也叫分裂树,它能在O(log n)内完成插入、查找和删除操作。在伸展树上的一般操作都基于伸展操作:假设想要对一个二叉查找树执行一系列的查找操作,为了使整个查找时间更小,被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法, 在每次查找之后对树进行重构,把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。
它的优势在于不需要记录用于平衡树的冗余信息。

Ps:我们介绍的Splay是双旋操作Splay。


数组定义:
struct node{
	int fa,siz,ct,val,son[2];
}T[MAXN];
//fa记录父亲节点,siz记录子树大小,val记录当前节点值,ct表示与当
//前节点值相同的点个数,son[2]记录其左儿子和右儿子。

预先操作:

1.clear:清空点k里的数据

void clear(int k){
	T[k].siz=T[k].ct=T[k].fa=T[k].val=T[k].son[0]=T[k].son[1]=0;
} 

2.up:统计k的子树大小

void up(int k){
	T[k].siz=T[L].siz+T[R].siz+T[k].ct;
} 

3.get:查询k是父亲的左儿子还是右儿子

int get(int k){
	return T[T[k].fa].son[1]==k;
}

旋转:

对于Splay来说,最重要的就是rotate旋转和splay伸展操作。
对于rotate操作,我们可以类比于Treap的旋转。

void rotate(int &k){
	int fa=T[k].fa,gran=T[fa].fa;
	int d1=get(k),d2=get(fa);
	T[T[k].son[d1^1]].fa=fa;
	T[fa].son[d1]=T[k].son[d1^1];T[k].son[d1^1]=fa;
	T[k].fa=gran;T[fa].fa=k;
	if(gran) T[gran].son[d2]=k;;
	up(fa);up(k);
}

splay操作是Rotate的升级版,该函数将子节点旋转到根,来保持Splay的复杂度。
每次的splay操作,我们都将其旋转到根节点。对于Splay的伸展操作,我们需要进行讨论:
1.当旋转的点中有根节点时,可以直接进行旋转。
这里写图片描述

2.当点x和其父亲,祖父三点共线,则先旋转x的父亲,然后旋转x。
这里写图片描述
3.如果x和其父亲,祖父三点不共线,旋转两次x。

void splay(int k){
	for(int fa;fa=T[k].fa;rotate(k))
	  if(T[fa].fa) rotate(get(fa)==get(k)?fa:k);
	root=k; 
}

删除:

删除操作需要进行讨论,如果对于值x存在多个,那直接将x所在节点k的size和ct减1即可。如果不是这样,我们继续讨论,如果k没有儿子,直接clear节点k即可。如果k只有一个儿子,就将它的儿子接上来即可。如果k有两个儿子,就将它的前驱接到它父亲上,然后将k的右儿子接到前驱上,这样就删去了k节点。

int find(int k,int val){   //先求出要删除点的位置,并进行splay伸展
	if(!k) return 0;
	if(val==T[k].val){
		splay(k);return k;
	}
	return find(T[k].son[val>T[k].val],val);
}
void delet(int x){
	int pl=find(root,x);
	if(!pl) return;
	if(T[root].ct>1){
		T[root].ct--,T[root].siz--;return;
	}
	if(!T[root].son[1]&&!T[root].son[0]){
		clear(root),root=0;return;
	}
	if(!T[root].son[1]||!T[root].son[0]){
		int rt=root;
		root=T[root].son[0]+T[root].son[1];
		T[root].fa=0;clear(rt);return;
	}
    int rt=root;
    pre(root,x);splay(dist);
    T[T[rt].son[1]].fa=root;T[root].son[1]=T[rt].son[1];
    clear(rt);up(root);T[root].fa=0;
    return;
}

其它操作:

如求取前驱,后继等操作,类似于Treap

void insert(int &k,int val,int pos){   //插入操作
	if(!k){
		k=++sz;
		T[k].ct=T[k].siz=1;T[k].fa=pos;T[k].son[0]=T[k].son[1]=0;T[k].val=val;
		dist=k;return; 
	}
	if(val==T[k].val){
		dist=k;T[k].siz++;T[k].ct++;return;
	}
	if(val<T[k].val) insert(T[k].son[0],val,k);
	if(val>T[k].val) insert(T[k].son[1],val,k);
	up(k);
}
int searchRANK(int k,int x){  //查询x排在第几
	if(!k) return 0;
	if(x<T[k].val) return searchRANK(L,x);
	if(x==T[k].val) return T[L].siz+1; 
	if(x>T[k].val) return T[L].siz+T[k].ct+searchRANK(R,x);
}
int searchPLACE(int k,int x){    //查询排在x的数是几
	if(!k) return 0;
	if(x<=T[L].siz) return searchPLACE(L,x);
	x-=T[L].siz;
	if(x<=T[k].ct) return T[k].val;
	x-=T[k].ct;
	return searchPLACE(R,x);
}
void pre(int k,int val){   //前驱,dist记录位置
	if(!k) return;
	if(val<=T[k].val) pre(L,val);
	else dist=k,pre(R,val);
}
void ahe(int k,int val){   //后继
	if(!k) return;
	if(val>=T[k].val) ahe(R,val);
	else dist=k,ahe(L,val);
}

合并:

①当S1中的所有元素小于S2(比如S1和S2是刚刚分裂出来的)时,只需要把S1最大的点伸展到根,然后连边即可。
②当S1和S2大小任意时,启发式合并,把小的往大的身上挪。
分裂:(以k为界限,左边小于或等于k,右边大于或等于k)


BZOJ3224模板:
#include<bits/stdc++.h>
#define L T[k].son[0]
#define R T[k].son[1]
#define MAXN 100005
using namespace std;
int read(){
	char c;int x=0,y=1;while(c=getchar(),(c<'0'||c>'9')&&c!='-');if(c=='-') y=-1;else x=c-'0';
	while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x*y;
}
int root,dist,sz,n;
struct node{
	int fa,siz,ct,val,son[2];
}T[MAXN];
void clear(int k){
	T[k].siz=T[k].ct=T[k].fa=T[k].val=T[k].son[0]=T[k].son[1]=0;
} 
void up(int k){
	T[k].siz=T[L].siz+T[R].siz+T[k].ct;
} 
int get(int k){
	return T[T[k].fa].son[1]==k;
}
void rotate(int &k){
	int fa=T[k].fa,gran=T[fa].fa;
	int d1=get(k),d2=get(fa);
	T[T[k].son[d1^1]].fa=fa;
	T[fa].son[d1]=T[k].son[d1^1];T[k].son[d1^1]=fa;
	T[k].fa=gran;T[fa].fa=k;
	if(gran) T[gran].son[d2]=k;;
	up(fa);up(k);
}
void splay(int k){
	for(int fa;fa=T[k].fa;rotate(k))
	  if(T[fa].fa) rotate(get(fa)==get(k)?fa:k);
	root=k; 
}
void insert(int &k,int val,int pos){
	if(!k){
		k=++sz;
		T[k].ct=T[k].siz=1;T[k].fa=pos;T[k].son[0]=T[k].son[1]=0;T[k].val=val;
		dist=k;return; 
	}
	if(val==T[k].val){
		dist=k;T[k].siz++;T[k].ct++;return;
	}
	if(val<T[k].val) insert(T[k].son[0],val,k);
	if(val>T[k].val) insert(T[k].son[1],val,k);
	up(k);
}
int searchRANK(int k,int x){
	if(!k) return 0;
	if(x<T[k].val) return searchRANK(L,x);
	if(x==T[k].val) return T[L].siz+1; 
	if(x>T[k].val) return T[L].siz+T[k].ct+searchRANK(R,x);
}
int searchPLACE(int k,int x){
	if(!k) return 0;
	if(x<=T[L].siz) return searchPLACE(L,x);
	x-=T[L].siz;
	if(x<=T[k].ct) return T[k].val;
	x-=T[k].ct;
	return searchPLACE(R,x);
}
void pre(int k,int val){
	if(!k) return;
	if(val<=T[k].val) pre(L,val);
	else dist=k,pre(R,val);
}
void ahe(int k,int val){
	if(!k) return;
	if(val>=T[k].val) ahe(R,val);
	else dist=k,ahe(L,val);
}
int find(int k,int val){
	if(!k) return 0;
	if(val==T[k].val){
		splay(k);return k;
	}
	return find(T[k].son[val>T[k].val],val);
}
void delet(int x){
	int pl=find(root,x);
	if(!pl) return;
	if(T[root].ct>1){
		T[root].ct--,T[root].siz--;return;
	}
	if(!T[root].son[1]&&!T[root].son[0]){
		clear(root),root=0;return;
	}
	if(!T[root].son[1]||!T[root].son[0]){
		int rt=root;
		root=T[root].son[0]+T[root].son[1];
		T[root].fa=0;clear(rt);return;
	}
    int rt=root;
    pre(root,x);splay(dist);
    T[T[rt].son[1]].fa=root;T[root].son[1]=T[rt].son[1];
    clear(rt);up(root);T[root].fa=0;
    return;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++){
		int x=read(),y=read();
		if(x==1) insert(root,y,0),splay(dist);
		if(x==2) delet(y);
		if(x==3) printf("%d\n",searchRANK(root,y));
		if(x==4) printf("%d\n",searchPLACE(root,y));
		if(x==5) dist=0,pre(root,y),printf("%d\n",T[dist].val);
		if(x==6) dist=0,ahe(root,y),printf("%d\n",T[dist].val); 
	}
	return 0;
}

文献资料:图片转自博客ZigZagK,感谢ZZK大佬

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/stevensonson/article/details/79731526

智能推荐

HTML、CSS知识点总结_下列是html和css中的注释语句是-程序员宅基地

文章浏览阅读680次,点赞5次,收藏23次。一,html+css基础1-1 Html和CSS的关系学习web前端开发基础技术需要掌握:HTML、CSS、JavaScript语言。下面我们就来了解下这三门技术都是用来实现什么的:HTML是网页内容的载体。内容就是网页制作者放在页面上想要让用户浏览的信息,可以包含文字、图片、视频等。CSS样式是表现。就像网页的外衣。比如,标题字体、颜色变化,或为标题加入背景图片、边框等。所有这些用来改变内容外观的东西称之为表现。JavaScript是用来实现网页上的特效效果。如:鼠标滑过弹出下拉菜单。或鼠_下列是html和css中的注释语句是

《Linux4.0设备驱动开发详解》笔记--第十八章:ARM Linux设备树_第18章 arm linux设备树-程序员宅基地

文章浏览阅读3.6k次。18.1 ARM设备树简介设备舒适一种描述印鉴的数据结构,它起源于OpenFirmware(OF) 采用设备树前后对比: 采用设备树之前:ARM架构的板极硬件细节过多的被硬编码在arch/arm/plat-xxx和arch/arm/mach-xxx中采用设备树之后:许多硬件细节可以直接通过它传递给Linux,而不再需要在讷河中进行大量的冗余编码设备树的组成:由一系列被命名的节点(Node)_第18章 arm linux设备树

qt QDateTime和QString互转_qt qdate转qjsovalue-程序员宅基地

文章浏览阅读2.9w次。(1)QDateTime 做差值 QDateTime beginTime = QDateTime::currentDateTime(); QDateTime endTime = QDateTime::currentDateTime(); QString value = QDateTime::fromMSecsSinceEpoch(endTime.toMSecsSince..._qt qdate转qjsovalue

python下载过程中最后一步执行opencv出错怎么回事_PyCharm安装opencv-python和opencv-contrib-python的一些问题和解决方法_2018-09-27...-程序员宅基地

文章浏览阅读1.9k次。当我想要在python上测试FeatureDetector并使用OpenCV的SIFT时,由于我在pycharm上仅仅安装了opencv-python,所以会出现报错(忘记截图了,好像是:‘module’ object has no attribute ‘xfeatures2d’。大致意思是说找不到 xfeatures2d 的库)。2018.9.30更新:Windows环境下把opencv中pyt..._为什么我下的python最后一步测试的时候

springcloud_originaluri.gethost() 为 null-程序员宅基地

文章浏览阅读637次。认识微服务单体架构单体架构:将业务的所有功能集中在一个项目中开发,打成一个包部署。优点:架构简单,部署成本低缺点:耦合度高(维护困难、升级困难)分布式架构分布式架构:根据业务功能对系统做拆分,每个业务功能模块作为独立项目开发,称为一个服务。优点:降低服务耦合,有利于服务升级和拓展缺点:服务调用关系错综复杂分布式架构虽然降低了服务耦合,但是服务拆分时也有很多问题需要思考:服务拆分的粒度如何界定? 服务之间如何调用? 服务的调用关系如何管理?人们需要制定.._originaluri.gethost() 为 null

狂神说JavaWeb详细笔记_狂神说javaweb笔记-程序员宅基地

文章浏览阅读2.8k次,点赞5次,收藏44次。目录概念前言WEB应用程序动态WEB的访问过程WEB服务器技术讲解Tomcat安装tomcat配置发布一个WEB网站HTTP什么是HTTPHTTP的两个时代HTTP请求HTTP请求MavenMaven项目架构管理工具在IDEA里面使用Maven创建一个普通的Maven项目标记文件夹功能解决遇到的问题Servlet简介HelloServletMaven环境优化Servlet原理概念前言静态Web:. 提供给所有人看数据不会发生变化!. HTML,CSS动态Web:.有数据交互,登录账号密码,网站_狂神说javaweb笔记

随便推点

MySQL中Windows下my.ini.配置文件修改后无法启动的问题解决_my.ini替换后无法启动-程序员宅基地

文章浏览阅读2.5k次,点赞4次,收藏6次。本节目标1.掌握如何解决my.ini配置文件修改后无法启动的问题net stop mysql80配置文件my.ini的默认路径C:\ProgramData\MySQL\MySQL Server 8.0防止出错,拷贝一份复制到桌面,另存为的方式要保存为ANSInet start mysql80解决问题..._my.ini替换后无法启动

STM32窗口看门狗(警犬)_如果在while(1)循环体一直重设窗口看门狗值,系统会不会复位-程序员宅基地

文章浏览阅读632次。学习窗口看门狗记录_如果在while(1)循环体一直重设窗口看门狗值,系统会不会复位

如何优雅的实现 Spring Boot 接口参数加密解密?_encrypt-body-spring-boot-starter-程序员宅基地

文章浏览阅读5.1k次,点赞19次,收藏83次。因为有小伙伴刚好问到这个问题,松哥就抽空撸一篇文章和大家聊聊这个话题。加密解密本身并不是难事,问题是在何时去处理?定义一个过滤器,将请求和响应分别拦截下来进行处理也是一个办法,这种方式虽然粗暴,但是灵活,因为可以拿到一手的请求参数和响应数据。不过 SpringMVC 中给我们提供了 ResponseBodyAdvice 和 RequestBodyAdvice,利用这两个工具可以对请求和响应进行预处理,非常方便。所以今天这篇文章有两个目的:分享参数/响应加解密的思路。分享 ResponseBodyA_encrypt-body-spring-boot-starter

程序使用微软雅黑作为默认字体在xp下的问题_xp默认字体变成微软雅黑了-程序员宅基地

文章浏览阅读2.4k次。1、微软雅黑是 Vista 及更高版本 Windows 的标配中文字体,但不是 XP 的标配字体,XP 的任何一个 SP 或更新包都没有包含它。2、XP系统默认中文字体是宋体,在电脑上的显示效果不如微软雅黑好看。3、程序如果在XP下使用微软雅黑,但系统又没有该字体时,会使用XP默认字体。4、XP 系统上的微软雅黑字体,通常有两种来源:用户主动下载安装或安装 Of_xp默认字体变成微软雅黑了

iOS 浅谈MVVM+RAC_ioss中mvvm使用raccommand请求多个接口-程序员宅基地

文章浏览阅读788次。学习笔记之MVVM+RAC公司项目之前的很多年一直是用MVC框架,最近项目改版(加重构)提出了使用MVVM + RAC的框架结构,以达到各个部分模块代码之间的解耦。关于MVVM 以及RAC 还不太了解的同学请自行百度,我这里主要讲解下简单的使用。 以登录界面为例,需求如下: - 注册用户输入手机号密码登录 - 手机号获取验证码快速登录 - 游客登录 - 第三方(QQ,微信…)登录_ioss中mvvm使用raccommand请求多个接口

【复杂网络】复杂网络度的不相关性(Degree-uncorrelated network)标注笔记-程序员宅基地

文章浏览阅读4.5k次,点赞6次,收藏19次。【笔记】度相关、不相关网络的理解(不一定正确)社交网络中,你刚注册,系统给你推荐了小明,你关注小明的概率和小明一点关系都没有,纯粹是你为了完成任务随便选了个人关注。因为你关注小明的概率随机,只是由你自己的关注总数(节点出度)决定,和对方的关注数和被关注数无关。这个网络就是度不相关网络。你已经玩社交网络很久,系统根据你的兴趣给你推荐小明,你关注小明的概率和小明是不是大V有很大关系(假设..._uncorrelated network

推荐文章

热门文章

相关标签