普通平衡树

#前言
您需要写一种数据结构,来维护一些数,其中需要提供一下的操作:
1.插入数值x
2.删除数值x(如果有多个,只删除一个)
3.查询数值x的排名(如有多个相同的数,应输出最小的排名)
4.查询排名为x的数值
5. 求数值x的前驱(小于x最大的数)
6.求数值x的后继(大于x最小的数)

首先我们引入一种数据结构叫二叉查找树(BST)。该树满足一下性质:
对于树的任意一个节点
1.该节点的关键码不小于它的左子树中任意节点的关键码
2.该节点的关键码不大于它的右子树中任意节点的关键码

通俗一点来讲就是,一个节点的左边都比他小,右边都比他大QWQ

显然,二叉查找树的中序遍历是一个单调递增的节点序列……

那么我们来考虑解决上面的普通平衡树(因为不是主角就不重点讲啦!!)

1.插入:从根节点开始访问,小了向左走,大了向右走,找不到就新建点啦
2.删除:同插入过程啦啦啦啦
3.查询排名:因为左子树的点都比此节点小,那抹排名就是左子树的size(大小)+1啦啦啦,求size应该都会吧……
4.查询数值:如果左子树的大小比要求排名大,就往左走,否则往右走,直到一样……
5.前驱:首先我们先找到这个数,因为左子树的点都比这个数小,所以向左儿子走一步,然后一直向右边走,走到头就是啦
6.后继:同理啦,向右儿子走一步,然后一直向左走

是不是感觉BST超简单的,没错就是这么简单……但是你没发现什么问题嘛??
这里写图片描述

不不不这里写图片描述

现在我按顺序插入1,2,3,4,5
树就变成了这样
我要是按顺序插入1,2,3……10^5
这特么不就变成链表了么这里写图片描述
实际上就算不这么极端,也能分分钟把这种最单纯的2x查找树搞死
这里写图片描述
很显然这样是过不了普通平衡树的……

是不是感觉刚才看的都白看了,不不不,下面要将的treap就是基于2x进行优化的……

那么该怎么优化呢???

我们发现2x查找树的不足之处就在于它太深了(太深了……咳咳咳),因此我们就想减少它的深度,通俗的来讲就是把它拍扁。那么如何实现呢……

旋转(不转不是中国人……)
右旋,是让某个节点的左儿子站到自己原来的位置,然后自己成为原来左儿子的右儿子(左旋同理啦!!请自行脑补)可以看下面的动来动去的图
这里写图片描述

合理的旋转操作可以是BST变得更扁(you)平(xiu)。那么问题来了,怎么样才算合理呢???根据研究发现,在随机的数据下,普通的BST可以虐杀其他一切高级的树。Treap的思想就是利用“随机”来创造平衡的条件。因为在旋转的过程中必须维持BST的性质,所以Treap就把“随机”作用在堆性质上。
其实Treap就是Tree和Heap的合成词啦。Treap在插入每个新节点的时候,就给该节点随机生成一个额外的权值。然后像二叉堆的插入过程一样,自底向上依次检查,当某个节点不满足大根堆性质时,就执行单旋转,是该节点与其父节点的关系发生对换。
特别的,对于删除操作,因为Treap支持旋转,我们可以将要删除的节点转到叶子节点,然后直接删除,就可以避免信息更新的问题啦。

Treap的所有操作时间复杂度都是O(logn)的

下面附上丑丑的代码:

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//By Bibi
/// .-~~~~~~~~~-._ _.-~~~~~~~~~-.
/// __.' ~. .~ `.__
/// .'// \./ \\`.
/// .'// | \\`.
/// .'// .-~"""""""~~~~-._ | _,-~~~~"""""""~-. \\`.
/// .'//.-" `-. | .-' "-.\\`.
/// .'//______.============-.. \ | / ..-============.______\\`.
/// .'______________________________\|/______________________________`.
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int MAXN=100010;
const int INF=0x7fffffff;
int read(){
int sum=0,flag=1;
char c;
for(;c<'0'||c>'9';c=getchar())if(c=='-') flag=-1;
for(;c>='0'&&c<='9';c=getchar())sum=(sum<<1)+(sum<<3)+c-'0';
return sum*flag;
}
int tot,root,n;
struct Treap{
int l,r;
int val,dat;
int cnt,size;
}tr[MAXN];
int New(int val){
tr[++tot].val=val;
tr[tot].dat=rand();
tr[tot].cnt=tr[tot].size=1;
return tot;
}
void update(int p){
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
void build(){
New(-INF);New(INF);
root=1;tr[1].r=2;
update(root);
}
int getrankbyval(int p,int val){
if(!p) return 0;
if(tr[p].val==val) return tr[tr[p].l].size+1;
if(val<tr[p].val) return getrankbyval(tr[p].l,val);
return getrankbyval(tr[p].r,val)+tr[tr[p].l].size+tr[p].cnt;
}
int getvalbyrank(int p,int rank){
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return getvalbyrank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].val;
return getvalbyrank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
void zig(int &p){
int q=tr[p].l;
tr[p].l=tr[q].r;tr[q].r=p;p=q;
update(tr[p].r);update(p);
}
void zag(int &p){
int q=tr[p].r;
tr[p].r=tr[q].l;tr[q].l=p;p=q;
update(tr[p].l);update(p);
}
void insert(int &p,int val){
if(!p) {p=New(val);return;}
if(val==tr[p].val) {tr[p].cnt++;update(p);return;}
if(val<tr[p].val){
insert(tr[p].l,val);
if(tr[p].dat<tr[tr[p].l].dat) zig(p);
}
else{
insert(tr[p].r,val);
if(tr[p].dat<tr[tr[p].r].dat) zag(p);
}
update(p);
}
int getpre(int val){
int ans=1;
int p=root;
while(p){
if(val==tr[p].val){
if(tr[p].l>0){
p=tr[p].l;
while(tr[p].r>0) p=tr[p].r;
ans=p;
}
break;
}
if(tr[p].val<val&&tr[p].val>tr[ans].val) ans=p;
p=val<tr[p].val ? tr[p].l:tr[p].r;
}
return tr[ans].val;
}
int getnext(int val){
int ans=2;
int p=root;
while(p){
if(val==tr[p].val){
if(tr[p].r){
p=tr[p].r;
while(tr[p].l) p=tr[p].l;
ans=p;
}
break;
}
if(tr[p].val>val&&tr[p].val<tr[ans].val) ans=p;
p=val<tr[p].val ? tr[p].l:tr[p].r;
}
return tr[ans].val;
}
void remove(int &p,int val){
if(!p) return;
if(val==tr[p].val){
if(tr[p].cnt>1) {tr[p].cnt--;update(p);return;}
if(tr[p].l||tr[p].r){
if(tr[p].r==0||tr[tr[p].l].dat>tr[tr[p].r].dat) zig(p),remove(tr[p].r,val);
else zag(p),remove(tr[p].l,val);
update(p);
}
else p=0;
return;
}
val<tr[p].val ? remove(tr[p].l,val):remove(tr[p].r,val);
update(p);
}
void init(){
n=read();
while(n--){
int opt=read(),x=read();
switch(opt){
case 1: insert(root,x);break;
case 2: remove(root,x);break;
case 3: printf("%d\n",getrankbyval(root,x)-1 );break;
case 4: printf("%d\n",getvalbyrank(root,x+1) );break;
case 5: printf("%d\n",getpre(x) );break;
case 6: printf("%d\n",getnext(x) );break;
}
}
}
int main(){
build();
init();
return 0;
}