首页 > 其他分享 >【学习笔记】平衡树 Treap

【学习笔记】平衡树 Treap

时间：2022-09-21 16:55:05浏览次数：92  
标签：return val rs int siz 笔记 Treap ls 平衡

平衡树 旋转Treap

一个重要的等式

treap=tree+heap

解释：treap，即树堆，顾名思义，就是树+堆，而一般的，此处的树指BST（二叉搜索树）

也就是说，treap是一棵BST,也是一个二叉堆，但二者的性质似乎有些冲突啊，BST怎么可能同时是一个二叉堆呢?treap则是很好的解决了这一问题

我们可以给每个值一个随机附加的优先级，让值满足BST的性质（左<根<右），而优先级满足堆的性质

Treap的优点

Treap，作为BST和堆的结合体，一种随机化的数据结构，它的形态根本无法固定下来——不是规则的二叉树，更不是完全二叉树，甚至有时无法满足平衡树两侧高度差小于等于一的定义，但是它却可以保证log的时间复杂度，防止极端的情况使BST退化成链

平衡树の作用

模板题

写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

  1. 插入 \(x\) 数
  2. 删除 \(x\) 数(若有多个相同的数，因只删除一个)
  3. 查询 \(x\) 数的排名(排名定义为比当前数小的数的个数 \(+1\) )
  4. 查询排名为 \(x\) 的数
  5. 求 \(x\) 的前驱(前驱定义为小于 \(x\)，且最大的数)
  6. 求 \(x\) 的后继(后继定义为大于 \(x\)，且最小的数)

考虑如何针对Treap的性质来实现这些操作

当然是旋转啦

Treap的实现

先来看一下预处理操作

随机分配的优先级（这个背过就好）

inline int rand()
{
	static int seed=12345;
	return seed=(int)seed*482711ll%2147483647;
}

push_up 更新操作（类似BST,一目了然）

void push_up(int p)
{
	t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz+t[p].cnt;
}

然后就是旋转啦

想一下，我们要向满足Treap堆的性质，那么当其不满足堆性质时就应该有所作为，我们可以通过旋转来搞定

放一张图，来自这里

其实还是很好理解的，但是唯一迷惑的就是B变成了F的儿子,其实是因为旋转前后要保证BST遍历顺序不变，而大家都知道BST的遍历顺序是中序遍历，自己手模一遍就可以理解啦QWQ

左旋

void left_rotate(int &p) //左旋 
{
	int x=t[p].rs;
	t[p].rs=t[x].ls;
	t[x].ls=p;
	t[x].siz=t[p].siz;
	push_up(p);
	p=x;
}

右旋

void right_rotate(int &p) //右旋 
{
	int x=t[p].ls;
	t[p].ls=t[x].rs;
	t[x].rs=p;
	t[x].siz=t[p].siz;
	push_up(p); 
	p=x;
}

插入操作

insert操作，我们可以利用动态开点的方法，同时也不断的进行比较（val）、旋转（根据优先级），直到该节点成为叶节点位置，至于往哪转的话自己根据代码手模一下即可

void insert(int &p,int x) //插入 
{
	if(p==0) //成功变成了叶节点
	{
		p=++tot;
		t[p].siz=t[p].cnt=1;
		t[p].val=x;
		t[p].pri=rand();
		return ;
	}
	
	t[p].siz++;
	
	if(t[p].val==x) //search中。。。
	{
		t[p].cnt++;
	}
	else
	{
		if(x>t[p].val) //x应该在右子树
		{
			insert(t[p].rs,x); //把它插进右子树里
			if(t[t[p].rs].pri<t[p].pri) //优先级比较（此处是小根堆）
			{
				left_rotate(p); //左旋p点，让右子树上去
			}
		}
		else //x应该在左子树
		{
			insert(t[p].ls,x); //把它插进左子树里
			if(t[t[p].ls].pri<t[p].pri) //同理
			{
				right_rotate(p); //右旋p点，让左子树上去
			}
		}
	}
	
}

删除操作

remove操作，同时也是代码量最大的操作，可以根据BST性质删，但此处主要介绍根据堆的性质删除

若一节点左节点pri小于右节点，那就右旋该节点，让左节点上去（因为是小根堆），此时右节点变成了右子树的根节点，然后再访问右节点递归进行（因为树就是递归的操作啦），然后pri小的弄上去，保证堆的性质，然后进行删除

void remove(int &p,int x) //删除 
{
	if(p==0)
	{
		return ;
	}
	
	if(t[p].val==x)
	{
		if(t[p].cnt>1)
		{
			t[p].cnt--;
			t[p].siz--;
		}
		else
		{
			if(t[p].ls==0 || t[p].rs==0)
			{
				p=t[p].ls+t[p].rs;
			}
			else
			{
				if(t[t[p].ls].pri<t[t[p].rs].pri)
				{
					right_rotate(p);
					remove(p,x);
				}
				else
				{
					left_rotate(p);
					remove(p,x);
				}
			}
		}
	}
	else
	{
		if(x>t[p].val)
		{
			t[p].siz--;
			remove(t[p].rs,x);
		}
		else
		{
			t[p].siz--;
			remove(t[p].ls,x);
		}
	}
}

查询排名 && 第k值

这个很好理解啦（cnt指的是这样的值有多少个）

int query_rank(int p,int x)
{
	if(p==0)
	{
		return 0;
	}
	if(t[p].val==x)
	{
		return t[t[p].ls].siz+1;
	}
	if(x>t[p].val)
	{
		return t[t[p].ls].siz+t[p].cnt+query_rank(t[p].rs,x);
	}
	else
	{
		return query_rank(t[p].ls,x);
	}
}

int query_kth(int p,int k)
{
	if(p==0)
	{
		return 0;
	}
	
	if(k<=t[t[p].ls].siz)
	{
		return query_kth(t[p].ls,k);
	}
	
	k-=t[t[p].ls].siz;
	
	if(k<=t[p].cnt)
	{
		return t[p].val;
	}
	
	k-=t[p].cnt;
	
	return query_kth(t[p].rs,k);
}

查询前驱/后继

按照BST的性质找就好

int query_pre(int p,int x)
{
	if(p==0)
	{
		return -inf;
	}
	
	if(t[p].val<x)
	{
		return max(t[p].val,query_pre(t[p].rs,x));
	}
	else
	{
		return query_pre(t[p].ls,x);
	}
}

int query_back(int p,int x)
{
	if(p==0)
	{
		return inf;
	}
	
	if(t[p].val>x)
	{
		return min(t[p].val,query_back(t[p].ls,x));
	}
	else
	{
		return query_back(t[p].rs,x); 
	}
}

下面是整个的代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=1e5+5;

const int inf=1e7+5;

inline int read()
{
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w*f;
}

int root;

int n,tot;

struct treap
{
	int ls;
	int rs;
	int cnt;
	int siz;
	int val;
	int pri;
}t[maxn];

inline int rand()
{
	static int seed=12345;
	return seed=(int)seed*482711ll%2147483647;
}

void push_up(int p)
{
	t[p].siz=t[t[p].ls].siz+t[t[p].rs].siz+t[p].cnt;
}

void right_rotate(int &p) //右旋 
{
	int x=t[p].ls;
	t[p].ls=t[x].rs;
	t[x].rs=p;
	t[x].siz=t[p].siz;
	push_up(p); 
	p=x;
}

void left_rotate(int &p) //左旋 
{
	int x=t[p].rs;
	t[p].rs=t[x].ls;
	t[x].ls=p;
	t[x].siz=t[p].siz;
	push_up(p);
	p=x;
}

void insert(int &p,int x) //插入 
{
	if(p==0)
	{
		p=++tot;
		t[p].siz=t[p].cnt=1;
		t[p].val=x;
		t[p].pri=rand();
		return ;
	}
	
	t[p].siz++;
	
	if(t[p].val==x)
	{
		t[p].cnt++;
	}
	else
	{
		if(x>t[p].val)
		{
			insert(t[p].rs,x);
			if(t[t[p].rs].pri<t[p].pri)
			{
				left_rotate(p);
			}
		}
		else
		{
			insert(t[p].ls,x);
			if(t[t[p].ls].pri<t[p].pri)
			{
				right_rotate(p);
			}
		}
	}
	
}

void remove(int &p,int x) //删除 
{
	if(p==0)
	{
		return ;
	}
	
	if(t[p].val==x)
	{
		if(t[p].cnt>1)
		{
			t[p].cnt--;
			t[p].siz--;
		}
		else
		{
			if(t[p].ls==0 || t[p].rs==0)
			{
				p=t[p].ls+t[p].rs;
			}
			else
			{
				if(t[t[p].ls].pri<t[t[p].rs].pri)
				{
					right_rotate(p);
					remove(p,x);
				}
				else
				{
					left_rotate(p);
					remove(p,x);
				}
			}
		}
	}
	else
	{
		if(x>t[p].val)
		{
			t[p].siz--;
			remove(t[p].rs,x);
		}
		else
		{
			t[p].siz--;
			remove(t[p].ls,x);
		}
	}
}

int query_rank(int p,int x)
{
	if(p==0)
	{
		return 0;
	}
	if(t[p].val==x)
	{
		return t[t[p].ls].siz+1;
	}
	if(x>t[p].val)
	{
		return t[t[p].ls].siz+t[p].cnt+query_rank(t[p].rs,x);
	}
	else
	{
		return query_rank(t[p].ls,x);
	}
}

int query_kth(int p,int k)
{
	if(p==0)
	{
		return 0;
	}
	
	if(k<=t[t[p].ls].siz)
	{
		return query_kth(t[p].ls,k);
	}
	
	k-=t[t[p].ls].siz;
	
	if(k<=t[p].cnt)
	{
		return t[p].val;
	}
	
	k-=t[p].cnt;
	
	return query_kth(t[p].rs,k);
}

int query_pre(int p,int x)
{
	if(p==0)
	{
		return -inf;
	}
	
	if(t[p].val<x)
	{
		return max(t[p].val,query_pre(t[p].rs,x));
	}
	else
	{
		return query_pre(t[p].ls,x);
	}
}

int query_back(int p,int x)
{
	if(p==0)
	{
		return inf;
	}
	
	if(t[p].val>x)
	{
		return min(t[p].val,query_back(t[p].ls,x));
	}
	else
	{
		return query_back(t[p].rs,x); 
	}
}

int main()
{
	n=read();
	
	for(int i=1;i<=n;i++)
	{
		int opt=read();
		int x=read();
		
		if(opt==1)
		{
			insert(root,x);
		}
		if(opt==2)
		{
			remove(root,x);
		}
		if(opt==3)
		{
			cout<<query_rank(root,x)<<endl;
		}
		if(opt==4)
		{
			cout<<query_kth(root,x)<<endl;
		}
		if(opt==5)
		{
			cout<<query_pre(root,x)<<endl; 
		}
		if(opt==6)
		{
			cout<<query_back(root,x)<<endl;
		}
	}
	
	return 0;
}

扩展：Fhq_treap 和 Splay

Fhq_treap是一种NB的treap(无旋treap)

Splay又名伸展树,也是一种平衡树

以上二者最大的共性就是我都不会。。。所以先去学习啦！

其实，平衡树的种类还有很多，感兴趣的话可以自行查找一下

自分の命よりも大切なものは、こんなに探しやすいものではありません

标签：return,val,rs,int,siz,笔记,Treap,ls,平衡
From： https://www.cnblogs.com/SitoASK/p/16716216.html

相关文章

  • openstack笔记下
    用ssh登录其他节点：sship地址，退出用logoutopestackserverresize调整云主机类型openstacknetworkcreate网络名--mtu1350 echo"anon_root=/opt" /etc/vsftpd......
  • 记：信息系统项目管理师学习笔记三
    学习流程：先整理十大管理的详细知识点，然后是其他章节的内容项目整体管理：识别、确定、结合、统一与协调各项目管理过程组内不同过程与项目管理活动所需进行的各种过程和活......
  • 扩展欧拉定理笔记
    扩展欧拉定理笔记前置知识欧拉定理\[\forall(a,m)=0,s.t.\,a^{\varphi(m)}\equiv1\;(mod\;m)\]简证：考虑\(m\)的简化剩余系\(S\)，它关于模乘法封闭，\(a\)是其中元......
  • STC51单片机学习笔记
    点灯系列STC8点灯点击查看STC8点灯代码#include<STC8H.H>//include了stc8h.h，就不用声明P0M1之类的//#include"reg51.h"//sfrP0M1=0x93;//sfrP0M0=0x94;......
  • python学习笔记：pytest单元测试框架
    一、安装配置和运行规则1、安装：pipinstallpytest查看安装版本：pytest--version 2、Pytest用例运行规则用Pytest写用例时候，一定要按照下面的规则去写，否则不符合规......
  • 《基于深度学习的跨模态检索综述》阅读笔记
    目录写这篇阅读笔记有如下目标0引言0.1多模态数据是什么？0.2多模态数据有哪些应用？0.3传统单模态检索是什么？0.4跨模态检索是什么？0.4.1优势0.4.2挑战0.4.3可行的解决......
  • java学习笔记day01
    笔记基础语法一、注释单行注释：//123123多行注释：/*多行注释*/文档注释：/***@Description111*@Author111*/二、基本数据类型1、数据存储的单位​ 位、......
  • 机械革命笔记本 code01 开机显示屏不亮但是外接显示器正常显示的解决
    从网上搜了3个解决方法。实际上用方法一就解决了，释放下机器的静电就行了。不是显卡驱动或者内存条、显示器排线的问题！ 方法一笔记本释放静电的方法:拔掉电源充电器......
  • dotnet 读 WPF 源代码笔记 为什么自定义的 UserControl 用户控件不能跨程序集继承
    从设计上，用户控件UserControl就不是一个合适用来多次继承的类型，更不要说进行跨程序集继承自定义的UserControl用户控件。对于大部分的用户控件来说，都是采用组合现有的......
  • 【学习笔记】匈牙利算法
    【图论】二分图最大匹配——匈牙利算法二分图相当好理解这是百度百科的定义二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99