首页 > 其他分享 >Treap 学习笔记

Treap 学习笔记

时间：2023-12-10 12:35:49浏览次数：35  
标签：return get int updata 笔记 学习 Treap 节点 size

二叉查找树

二叉查找树是一棵有点权的二叉树，具有以下几个特征：

  • 左孩子的权值小于父亲的权值
  • 右孩子的权值大于父亲的权值
  • 中序遍历及从小到大排序

二叉查找树支持以下几个操作：

  • 插入一个数
  • 删除一个数
  • 找一个数的前驱
  • 找一个数的后继
  • 询问一个数的排名
  • 询问排第几名的数

二叉查找树一棵二叉查找树，所以在最优的情况下单一操作的时间复杂度应该是 \(\text{O}(\log n)\) 级别的。但是在进行操作时，如果输入的点权单调递增或递减，那么整个数据结构就将由树退化成为链。所以单次操作的时间复杂度最坏为 \(\text{O}(n)\) 级别。

普通平衡树

为了使这个数据结构平衡，平衡树就应运而生了。Treap 就是平衡树的一种，这个算法就是将树 (Tree) 与堆 (Heap) 相结合了起来。Treap 给每一个节点在维护原来的数值的同时，还添加了一个随机值。但看权值，这是一颗二叉搜索树，但是但看随机值这又是一个堆。

储存

首先我们应该了解一下如何储存一颗平衡树。

因为平衡树的结构是会改变的，所以我们需要储存每一个节点的左孩子与右孩子。因为一个节点可能会多次添加，所以应该使用 cnt 记录以下这个节点出现的个数。为了后面的操作，我们应该还需要定义一个 size 变量记录这个节点及子树的大小。

所以在我们定义的结构体应该是下面这样的：


struct node{
	int l,r,k,val,cnt,size;
}a[N];

updata

在进行修改操作之后，节点的子树大小会发行变化。updata 函数的功能是更新节点的 size 值。


void updata(int u){
	a[u].size=a[a[u].l].size+a[a[u].r].size+a[u].cnt;
}

make

在进行操作时，为了节省空间复杂度，平衡树使用了动态开点。动态开点就是你需要使用一个新节点时就现马上申请一个空间，而不是全部预留好。


int make(int k){
	a[++tot].k=k,a[tot].val=rand(); //tot 记录节点个数
	a[tot].cnt=a[tot].size=1;
	return tot;
}

zig && zag

既然需要再维护二叉查找树的同时维护平衡树，就需要在不改变平衡树的性质的情况下完成堆所需要的 swap 的操作。所以我们就迎来了平衡树最重要的操作 zig 与 zag。

这是一棵平衡树，其中 1 2 3 为节点 A B C 为子树。
它们满足以下性质：\(1>A>2>C>3>D\)

那么如果需要交换 2 3 的位置，那么在不违背其性质的情况下将其改为：

这个过程就是 zig 操作，反之即是 zag 操作。代码实现就是将将操作进行模拟，方法如下：


void zig(int &p){
	int q=a[p].l;
	a[p].l=a[q].r,a[q].r=p,p=q;
	updata(a[p].r),updata(p);
}
void zag(int &p){
	int q=a[p].r;
	a[p].r=a[q].l,a[q].l=p,p=q;
	updata(a[p].l),updata(p);
}

build

因为在平衡树中有旋转操作，所以根节点有可能会在旋转操作中改变位置。为了让根节点的位置保持不变，可以建立两个虚点，并令其优先级远远高于其他的点,永远停留在根节点的位置。


void build(){
	make(-INF),make(INF);
	root=1,a[1].r=2,updata(root);
	if(a[1].val<a[2].val) zag(root);
}

insert

在插入操作中，一共有三种操作。反复执行操作三，直至满足操作一或操作二。

  • 操作一：需要处理的节点为 \(0\)，意味着这个节点不存在，所以直接新建。

  • 操作二：已经找到车要添加的节点，cnt 加一。

  • 操作三：需要添加的节点小于或大于这个节点，那么分别访问左节点或右节点。


void insert(int &p,int k){
	if(p==0) p=make(k);
	else{
		if(a[p].k==k) a[p].cnt++;
		if(a[p].k>k){
			insert(a[p].l,k);
			if(a[a[p].l].val>a[p].val) zig(p);
		}if(a[p].k<k){
			insert(a[p].r,k);
			if(a[a[p].r].val>a[p].val) zag(p);
		}
	}updata(p);
}

del

在删除操作中，同样分为三种操作：

  • 操作一：没有找到这个点就直接返回，不进行修改操作。

  • 操作二：如果这个节点的值大于或者小于要删除的值，那么就继续访问左孩子或者右孩子。

  • 操作三：找到了这个值，如果 cnt 大于 \(1\)，那么直接 cnt-- 否则寻找比这个节点大的集合中的最小值。


void del(int &p,int k){
	if(p==0) return ;
	if(a[p].k==k){
		if(a[p].cnt>1){
			a[p].cnt--;
			updata(p);
			return;
		}if(a[p].l||a[p].r){
			if(!a[p].r||a[a[p].l].val) zig(p),del(a[p].r,k);
			else zag(p),del(a[p].l,k);
		}else p=0;
		updata(p);
		return;
	}if(a[p].k>k) del(a[p].l,k);
	else del(a[p].r,k);
	updata(p);
}

get_rank

get_rank 函数可以获得某个点的排名。在寻找时如果节点在左子树，则这个节点在左子树的排名就是这个节点在这棵子树上的排名。反之，如果这个节点在右子树，那么他的排名就是左子树的大小+根节点的大小+自己在右子树的排名。


int get_rank(int p,int k){
	if(p==0) return 0;
	if(a[p].k==k) return a[a[p].l].size+1;
	if(a[p].k>k) return get_rank(a[p].l,k);
	return a[a[p].l].size+a[p].cnt+get_rank(a[p].r,k);
}

因为查询的数可能不在树中存在，所以但是 get_rank 的返回值又是默认其存在的，所以将答案设为了函数值\(-1\)。为了避免发生这样的错误，需要在定义一个 find 函数检查是否存在这个节点。


bool find(int p,int x){
	if(a[p].k==x) return 0;
	if(a[p].val==0) return 1;
	if(a[p].k>x) return find(a[p].l,x);
	return find(a[p].r,x);
}

get_key

get_key 函数可以获取某个排名的数。当访问到一个节点时，如果这个节点的左子树的大小大于它的排名，那么这个节点就应该在左子树。如果这个排名大于这个节点的大小 + 左子树的大小，那么这个节点就应该在右子树。其他的情况就应该就在这个节点。


int get_key(int p,int rank){
	if(p==0) return INF;
	if(a[a[p].l].size>=rank) return get_key(a[p].l,rank);
	if(a[a[p].l].size+a[p].cnt>=rank) return a[p].k;
	return get_key(a[p].r,rank-a[a[p].l].size-a[p].cnt);
}

get_pr

get_pr 函数可以找到一个数的前驱，及比他大的数中最小的一个。因为平衡树满足左孩子 \(<\) 根节点 \(<\) 右孩子，所以只需要先走到左孩子，再一直向右走就可以了。


int get_pr(int p,int k){
	if(p==0) return-INF;
	if(a[p].k>=k) return get_pr(a[p].l,k);
	return max(get_pr(a[p].r,k),a[p].k);
}

get_ne

get_ne 函数可以找到一个数的后驱，及比他小的数中最大的一个。因为平衡树满足左孩子 \(<\) 根节点 \(<\) 右孩子，所以只需要先走到右孩子，再一直向左走就可以了。


int get_ne(int p,int k){
	if(p==0) return INF;
	if(a[p].k<=k) return get_ne(a[p].r,k);
	return min(get_ne(a[p].l,k),a[p].k);
}

P3369 普通平衡树

这一题就是一道模板题，只需要将前面的操作整合在一起就可以了。


#include<bits/stdc++.h>
using namespace std;
const int N=100010,INF=1e8;
int n;
struct Node{int l,r,k,val,cnt,size;}a[N];
int root,tot;
void updata(int u){a[u].size=a[a[u].l].size+a[a[u].r].size+a[u].cnt;}
int make(int k){
	a[++tot].k=k,a[tot].val=rand();
	a[tot].cnt=a[tot].size=1;
	return tot;
}
void zig(int &p){
	int q=a[p].l;
	a[p].l=a[q].r,a[q].r=p,p=q;
	updata(a[p].r),updata(p);
}
void zag(int &p){
	int q=a[p].r;
	a[p].r=a[q].l,a[q].l=p,p=q;
	updata(a[p].l),updata(p);
}
void build(){
	make(-INF),make(INF);
	root=1,a[1].r=2,updata(root);
	if(a[1].val<a[2].val) zag(root);
}
void insert(int &p,int k){
	if(p==0) p=make(k);
	else{
		if(a[p].k==k) a[p].cnt++;
		if(a[p].k>k){
			insert(a[p].l,k);
			if(a[a[p].l].val>a[p].val) zig(p);
		}if(a[p].k<k){
			insert(a[p].r,k);
			if(a[a[p].r].val>a[p].val) zag(p);
		}
	}updata(p);
}
void del(int &p,int k){
	if(p==0) return ;
	if(a[p].k==k){
		if(a[p].cnt>1){
			a[p].cnt--;
			updata(p);
			return;
		}if(a[p].l||a[p].r){
			if(!a[p].r||a[a[p].l].val) zig(p),del(a[p].r,k);
			else zag(p),del(a[p].l,k);
		}else p=0;
		updata(p);
		return;
	}if(a[p].k>k) del(a[p].l,k);
	else del(a[p].r,k);
	updata(p);
}
int get_rank(int p,int k){
	if(p==0) return 0;
	if(a[p].k==k) return a[a[p].l].size+1;
	if(a[p].k>k) return get_rank(a[p].l,k);
	return a[a[p].l].size+a[p].cnt+get_rank(a[p].r,k);
}
int get_key(int p,int rank){
	if(p==0) return INF;
	if(a[a[p].l].size>=rank) return get_key(a[p].l,rank);
	if(a[a[p].l].size+a[p].cnt>=rank) return a[p].k;
	return get_key(a[p].r,rank-a[a[p].l].size-a[p].cnt);
}
int get_pr(int p,int k){
	if(p==0) return-INF;
	if(a[p].k>=k) return get_pr(a[p].l,k);
	return max(get_pr(a[p].r,k),a[p].k);
}
int get_ne(int p,int k){
	if(p==0) return INF;
	if(a[p].k<=k) return get_ne(a[p].r,k);
	return min(get_ne(a[p].l,k),a[p].k);
}
bool find(int p,int x){
	if(a[p].k==x) return 0;
	if(a[p].val==0) return 1;
	if(a[p].k>x) return find(a[p].l,x);
	return find(a[p].r,x);
}
int main(){
	build();
	cin>>n;
	for(int i=1,op,x;i<=n;i++){
		cin>>op>>x;
		if(op==1) insert(root,x);
		if(op==2) del(root,x);
		if(op==3) cout<<get_rank(root,x)+find(root,x)-1;
		if(op==4) cout<<get_key(root,x+1);
		if(op==5) cout<<get_pr(root,x);
		if(op==6) cout<<get_ne(root,x);
		if(op!=1&&op!=2)cout<<endl;
	}return 0;
}

标签：return,get,int,updata,笔记,学习,Treap,节点,size
From： https://www.cnblogs.com/liudagou/p/treap.html

相关文章

  • 《网络空间安全导论》第5周学习总结 20232323郭旗
    教材学习内容总结 教材学习中的问题和解决过程问题：对非结构信息自组织聚合表达技术理解不够清晰解决方法：学问AI非结构信息自组织聚合表达技术，也称为自组织映射（Self-OrganizingMap，SOM）技术，是一种常用的无监督学习方法，可以将高维度的非结构化信息聚合到一个二维或者更高维......
  • 2023-2024-1 20231419 《计算机基础与程序设计》第十一周学习总结
    2023-2024-120231419《计算机基础与程序设计》第十一周学习总结作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2023-2024-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK11这个作业的目标自学《计算机科学......
  • 人工智能基础 - 机器学习算法分类
    监督学习在监督式学习下，输入数据被称为“训练数据”，每组训练数据有一个明确的标识或结果，如对防垃圾邮件系统中“垃圾邮件”“非垃圾邮件”，对手写数字识别中的“1“，”2“，”3“，”4“等。在建立预测模型的时候，监督式学习建立一个学习过程，将预测结果与“训练数据”的实际结果进行比较，不......
  • 通过提示学习进行多级蛋白质结构预训练
    MULTI-LEVELPROTEINSTRUCTUREPRE-TRAININGWITHPROMPTLEARNING通过提示学习进行多级蛋白质结构预训练期刊：ICLR2023作者：浙江大学团队背景蛋白质可以关注不同的结构水平来实现其功能。蛋白质结构有四个不同的层次，第一级是由氨基酸组成的蛋白质序列，第二级是指局部折叠结构，第三季......
  • 自己写个网盘系列：① 来学习开启这个项目吧
    ❤这个系列准备用Simple快速框架搞个自己能用的网盘，来个实战，教大家如何搞一个项目，其中你能学到如何进行项目级对接，如何快速进行项目编码，如何完善你的项目，以及如何部署它。......
  • .net core - 本地使用minikube搭建k8s - k8s(微服务学习) 一
    1.Docker-Desktop首先本地电脑需要安装docker-desktopDocker-Desktop的windows程序下载网址:docker-desktop2.K8s安装1.kubectl下载首先创建一个文件夹目录kubectl得安装可使用2种方式1.直接下载exe后放到该目录下载最新补丁版1.28： kubectl1.28.4。2.在创建目录......
  • vue3学习之createApp(App).mount('#app')
    装了vue-cli之后，新建个项目跑起来了，碰上个没理解的问题，不知道createApp(App).mount('#app')挂载的这个id=“app”从哪冒出来的 用命令创建出来的项目，components/HelloWorld.vue,App.vue,main.js中都没有估摸着得是底层的，网上找一圈，各路大神基本是一句带过，可能是太简单了，没......
  • 【项目学习】谷粒商城学习记录6 - 异步
    【项目学习】谷粒商城学习记录6-异步一、异步知识点复习1.四种java实现异步方法(1)继承Thread类，重写run()方法测试publicclassThreadTest{publicstaticvoidmain(String[]args){System.out.println("main...start...");Thread01thread0......
  • 学习资源推荐
    数学类学习资源推荐：3Blue1Brown一个学习数学频道，动画生动、直观、深刻，适合计算机领域学生学习。微积分：浙江大学苏德矿线性代数：山东大学秦静清华大学马辉   MIT线性代数---全球最牛线代课程概率论与数理统计：国防科技大学吴翊计算机MOOC学习资源推荐：计算机系统基础：南京大学袁春风C......
  • 学习笔记
    1.线段树平衡树进阶线段树分裂：按某个标准将线段树从某一条从根到叶子的路径处裂开，分成左、右两棵树。时间复杂度证明：由于线段树分裂时仅和一条从根到叶子的路径上的点有关，而树高为$O(\log{n})$，所以时间复杂度为$O(\log{n})$，且分裂一次会新建$O(\log{n})$个节点，所以分裂$......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99