【学习笔记】非旋Treap

发表于 | 分类于 | 误人子弟 个
字数统计: 1,304 | 阅读时长 ≈ 6

概念与基本性质

Treap = Tree + Heap，即是一棵同时满足二叉搜索树和堆性质的二叉树
Treap 有一个随机附加域满足堆的性质，其结构相当于以随机数据插入的二叉搜索树
其基本操作的期望时间复杂度为 O(log n)

相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。

基本操作

  1. 插入和删除
  2. 访问某位置
  3. 查询某数所在的位置

实现方法

本题目的是构造名次树来维护一个有序序列
为了在保证堆的性质的同时进行如上操作，我们引入下列函数：

1
2
cut(u, k)      //将以 u 为根节点的子树在第 k 个节点后切开，并返回切开后两树根节点。
merge(l, r)    //在维护堆性质的同时将的两棵 Treap 合并为一棵，并返回合并后的根节点。

每次cut的位置大概如下：

具体操作

插入 - insert = cut + merge + merge
删除 - delete = split + split + merge ? O(log n)
排名查询/数值查询 - search ：通过二叉排序树的性质进行查找
前驱 - last：将所有比 x 小的数切下，找到其中最大的数后，再合并
后继 - next：将所有比 x 小的数（包括）切下，在剩下的树中找出最小的数后，再合并

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<cstdio>
#include<cstdlib>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define ll long long
using namespace std;
struct Tnode{     //记录节点状态
	int l,r,val,siz,heap;
//l,r为节点左右子树，val节点数值 ，siz节点子树大小，heap随机生成
} t[100100];
struct aft{
	int l,r;
};
int n,root;
inline ll read(){
	ll f=1,x=0;
	char ch;
	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0' or ch>'9');
	do{x=x*10+ch-'0';ch=getchar();}while(ch>='0' and ch<='9');
	return f*x;
}
inline void update(int u){			//更新以u为根的子树的siz
	t[u].siz=t[t[u].l].siz+t[t[u].r].siz+1;
}
inline aft cut(int u,int k){		//从以u为根的子树上割下k个点
	aft ans={0,0}; 		//记录切割后左右子树的根节点
	if(!u) return ans;
	int lsize=t[t[u].l].siz+1;
	if(k>=lsize){		//若需要切下的点比整个左子树多，从右子树继续割
		ans=cut(t[u].r,k-lsize);
		t[u].r=ans.l;
		ans.l=u;
	}
	else{
		ans=cut(t[u].l,k);
		t[u].l=ans.r;
		ans.r=u;
	}
	update(u);			//更新以u为根节点的子树的siz
	return ans;		//返回左右子树根节点
}
inline int merge(int l,int r){       //将两棵树合并（按照heap值（小根堆））并返回根节点
	if(!l) return r;	//若左子树为空，返回右子树
	if(!r) return l;
	if(t[l].heap<t[r].heap){    //若左子树根节点heap比右子树小，将右子树与左子树的右儿子merge
		t[l].r=merge(t[l].r,r);
		update(l);
		return l;
	}
	else{		//左子树与右子树左儿子merge
		t[r].l=merge(l,t[r].l);
		update(r);
		return r;
	}
}
inline int rank(int x){    //查询有多少个数严格比x小
	int tmp=root,ans=0;
	while(tmp){
		if(x>t[tmp].val){
			ans+=t[t[tmp].l].siz+1;
			tmp=t[tmp].r;
		}
		else tmp=t[tmp].l;
	}
	return ans;
}
int cnt=0;
inline void ins(int x) {	//插入操作
	t[++cnt].val=x;
	t[cnt].heap=rand();  //随机生成heap值，使树保持相对平衡
	t[cnt].siz=1;
	aft p=cut(root,rank(x));
	//查找x在树中的rank，将比x小的数从树中切下
	root=merge(merge(p.l,cnt),p.r);
	//先将x与左子树合并，再将左子树和右子树合并，并更新根节点Root
}
inline void del(int x){      //删除操作
	aft p1=cut(root,rank(x));
	aft p2=cut(p1.r,1);
	root=merge(p1.l,p2.r);
}
inline int find(int u,int x){ //在以u为根节点的树中，找第x小的数
	int tmp=u;
	while(1){
		int val=t[t[tmp].l].siz+1;
		if(x==val) return t[tmp].val;
		if(x<val) tmp=t[tmp].l;
		else{
			x-=val;
			tmp=t[tmp].r;
		}
	}
}
inline int sma(int x){			//查找第一个比x小的数
	aft p=cut(root,rank(x));	//将所有比x小的数切下
	int ans=find(p.l,t[p.l].siz);	//查询切下的数中最大的
	root=merge(p.l,p.r);          //合并
	return ans;
}
inline int lar(int x){ 	     	//查找第一个比x大的数
	aft p=cut(root,rank(x+1));	//将所有比x小的数（包括）切下
	int ans=find(p.r,1);		//查询剩下的数中最小的
	root=merge(p.l,p.r);
	return ans;
}
int main(){
	n=read();
	rep(i,1,n){
		int opt,x;
		opt=read(),x=read();
		switch(opt){
			case 1: ins(x); break;
			case 2: del(x); break;
			case 3: printf("%d\n",rank(x)+1); break;
			case 4: printf("%d\n",find(root,x)); break;
			case 5: printf("%d\n",sma(x)); break;
			case 6: printf("%d\n",lar(x)); break;
		}
	}

	return 0;
}

题目来源

洛谷 P3369 【模板】普通平衡树（Treap/SBT）

0%