Treap平衡树

从二叉查找树说起

这一棵二叉查找树的中序遍历就是2-5-8-13-17-20-22-26。

使用二叉查找树有什么好处呢?

假如你插入时的数据基本随机,那么你建立的二叉查找树应该是基本平衡的。所谓平衡,就是这棵树的每个叶子节点的深度都基本相同。

如果一棵二叉查找树基本平衡,那么它将会有以下好的性质:

  • 查找一个值的时间约为O(log(n))

  • 插入一个值的时间约为O(log(n))

而且它的代码也非常容易完成,每个操作只需要一个小的递归函数就可以了,目测没几行。

二叉查找树的问题

这么好的东西基本没人用自然是有原因的。

上文提到,“如果二叉查找树是基本平衡的”。

这是个不错的flag,很多时候你都没法保证它是基本平衡的。尤其在竞赛中,这种卡你的数据是必然会出现的。

举个例子,假如你在建树的时候,给你的数据是有序的,那么建出来的树可能就是这样的:

这样一棵二叉查找树就退化成了一个链表。此时,查找操作的时间复杂度就变成了O(n)。

那我还不如写个链表呢……

当然,你也可以采用其他的一些方法,比如全读进来再随机插入到树里。但这些方法终归都是有局限性的。

平衡树

那么,有没有使一棵二叉查找树墙柱保持平衡的方法呢?答案当然是肯定的,这样的二叉查找树就被成为平衡二叉查找树,简称平衡树。

当然这意味着你要写更多的代码……

平衡树有很多种,比如说AVL,红黑树,SBT,Splay等等。今天的Treap就是平衡树中相对比较好写的一种。

代价就是慢,当然比起线性表来说还是强多了。

Treap

废话扯了这么多终于进入正题了……

Treap,顾名思义就是Tree+Heap。这么命名的原因就是它使用了二叉堆的性质来保持二叉树的平衡。

我们知道,一个二叉堆满足这样的性质:一个节点的两个儿子的值都小于节点本身的值。如果一个二叉查找树满足这样的性质,那么它就被称作Treap。

但是等等,这样的设定似乎和二叉查找树矛盾啊。一个要求节点值小于左儿子的值,一个要求节点值大于左儿子的值,这显然是不可能做到的。

只有一种方法能够解决,就是让每个节点有2个值,其中一个满足二叉查找树的性质,一个满足堆的性质。为方便起见,下面把满足二叉查找树性质的值称作key,把满足大根堆性质的值称作priority。

每个节点的key我们是无法改变了,为了保证Treap的平衡性,我们需要在priority上做一点文章。其实也没有什么复杂的,就是让每个节点的priority都取一个随机值,这样我们就可以保证这棵树“基本平衡”。

随机数的生成

显然,在Treap中节点priority的随机数堆排序,随机数是不能重复的。如果我们采用系统函数生成的随机数,会有出现重复的可能性。如果priority取到了重复的值,则必然会造成堆结构的混乱。

那么,如何生成不重复的随机数呢?

万能的搜索引擎告诉我,以下这种方式,可以生成不重复的随机数……

1
2
3
4
5
inline int random()
{
static int seed=19260817; //seed可以随便取
return seed=int(seed*48271LL%2147483647);
}

说实话我也不知道48271这个数字是哪里来的,不过百度告诉我这样可以取遍1-2147483647中的所有数字。

Treap

有些性质是显然的

如果v是u的左孩子,则v.key < u.key。

如果v是u的右孩子,则v.key > u.key。

如果v是u的孩子,则v.priority > u.priority。

那么,如何维护这些性质在插入删除或者查找后,仍能够同时存在呢?

一般我们采用的方式,是现先将待插入的数插入二叉查找树,然后通过旋转操作来调整使其满足堆的性质。

哨兵节点

  • 为了便于处理Treap树的边界条件,我们定义一个哨兵节点来代表空节点(NULL),哨兵nil是一个树中普通节点相同属性的对象。

  • 哨兵的属性key、left、right并不重要,可以是任意值(建议left和right都指向nil自身),为了保证Treap堆的性质不受nil影响,其priority取一个极大值(如之前随机数决定的最大值2147483647)。

  • 所有指向空节点的指针(NULL)全部用nil代替。

插入

如图一颗Treap树

插入新节点C:25

Then

插入完成!!!

插入新节点D:9

Then

通过旋转调整,使得平衡树满足堆性质

插入完成!!!

删除

旋转二叉树,使要删除的结点只有一个孩子或者成为叶子,通过指针交换即可删除,删除后通过旋转二叉树,调整使其满足堆的性质。

一个递归的过程:找到待删除的点=>判断并旋转知道其满足删除条件=>删除=>旋转使其满足堆的性质。

查询

同理,按二叉搜索树的规则找就可以了。

树上的动态顺序统计

顺序统计树

在Treap树的每个节点中,除了key、priority、left、right以外,在添加一个size,这个属性通常包含以这个节点为根的子树的内节点数,即这颗子树的大小。

如果定义哨兵节点nil.size=0,则有等式x.size=x.left.size+x.right.size+1。

旋转

待旋转的树

旋转后

用原来根位置的节点(E:23)的size赋值给现在根节点(D:9)的size。

再对原来根节点(E:23)进行重新统计:x.size=x.left.size+x.right.size+1。

查找具有给定秩的元素

如图一颗Treap树,红色的数字代表size

1
2
3
4
5
6
7
8
OS-SELECT(T,x)
r=T.left.size+1
if x==r
return T.key;
else if x<r
return OS-SELECT(T.left,x)
else
return OS-SELECT(T.right,x-r)

确定元素的秩

如图一颗Treap树,红色的数字代表size

1
2
3
4
5
6
7
8
OS-RANK(T,x)
r=T.left.size+1
if T.key==x
return r;
else if x<T.key
return OS-RANK(T.left,x)
else
return OS-RANK(T.right,x)+r

Treap含有重复元素处理

简单说一下方法,在存树的结构体内开辟一个cnt,表示具有相同key值的的插入个数,删除时,只要让cnt-1,当cnt为0时,就可以将这个节点删除。

同时,在统计节点的过程中,

统计公式

应改变为

代码实现

这里写一个板子码。

以洛谷P3369 【模板】普通平衡树(Treap/SBT)为例。

模拟指针+数组

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<bits/stdc++.h>
using namespace std;
struct Treap
{
int left,right;
int key,priority;
int size,cnt;
}tree[100005];
int n,size,root,ans;
inline long random()//别问我为啥定义long类型,Linux下int类型CE了!!!
{
static int seed=19260817;//随意取
return seed=int(seed*48271LL%2147483647);
}
void r_turn(int &node)//右旋
{
int tmp=tree[node].left;
tree[node].left=tree[tmp].right;
tree[tmp].right=node;
tree[tmp].size=tree[node].size;
tree[node].size=tree[tree[node].left].size+tree[tree[node].right].size+tree[node].cnt;
node=tmp;
}
void l_turn(int &node)//左旋
{
int tmp=tree[node].right;
tree[node].right=tree[tmp].left;
tree[tmp].left=node;
tree[tmp].size=tree[node].size;
tree[node].size=tree[tree[node].left].size+tree[tree[node].right].size+tree[node].cnt;
node=tmp;
}
void insert(int &node,int x)//插入
{
if(node==0)//建立新节点
{
node=++size;
tree[node].size=tree[node].cnt=1;
tree[node].key=x;
tree[node].priority=(int)random();
return;
}
tree[node].size++;
if(tree[node].key==x)//处理重复插入
tree[node].cnt++;
else if(x>tree[node].key)
{
insert(tree[node].right,x);
if(tree[tree[node].right].priority<tree[node].priority)
l_turn(node);
}
else
{
insert(tree[node].left,x);
if(tree[tree[node].left].priority<tree[node].priority)
r_turn(node);
}
}
void del(int &node,int x)//删除
{
if(node==0)
return ;
if(tree[node].key==x)
{
if(tree[node].cnt>1)
{
tree[node].cnt--;
tree[node].size--;
return ;
}
if(tree[node].left*tree[node].right==0)
node=tree[node].left+tree[node].right;
else if(tree[tree[node].left].priority<tree[tree[node].right].priority)
{
r_turn(node);
del(node,x);
}
else
{
l_turn(node);
del(node,x);
}
}
else if(x>tree[node].key)
{
tree[node].size--;
del(tree[node].right,x);
}
else
{
tree[node].size--;
del(tree[node].left,x);
}
}
int query_rank(int node,int x)//确定元素的秩
{
if(node==0)
return 0;
if(tree[node].key==x)
return tree[tree[node].left].size+1;
else if(x<tree[node].key)
return query_rank(tree[node].left,x);
else
return query_rank(tree[node].right,x)+tree[tree[node].left].size+tree[node].cnt;
}
int query_select(int node,int x)//查找给定秩的元素
{
if(node==0)
return 0;
if(x<=tree[tree[node].left].size)
return query_select(tree[node].left,x);
else if(x>tree[tree[node].left].size+tree[node].cnt)
return query_select(tree[node].right,x-tree[tree[node].left].size-tree[node].cnt);
else
return tree[node].key;
}
void query_before(int node,int x)//求前驱
{
if(node==0)
return ;
if(tree[node].key<x)
{
ans=node;
query_before(tree[node].right,x);
}
else
query_before(tree[node].left,x);
}
void query_after(int node,int x)//求后继
{
if(node==0)
return ;
if(tree[node].key>x)
{
ans=node;
query_after(tree[node].left,x);
}
else
query_after(tree[node].right,x);
}
int main()
{
scanf("%d",&n);
int mode,x;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&mode,&x);
switch(mode)
{
case 1:insert(root,x); break;
case 2:del(root,x); break;
case 3:printf("%d\n",query_rank(root,x)); break;
case 4:printf("%d\n",query_select(root,x)); break;
case 5:
{
ans=0;
query_before(root,x);
printf("%d\n",tree[ans].key);
break;
}
case 6:
{
ans=0;
query_after(root,x);
printf("%d\n",tree[ans].key);
break;
}
//1.插入x数
//2.删除x数(若有多个相同的数,因只删除一个)
//3.查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
//4.查询排名为x的数
//5.求x的前驱(前驱定义为小于x,且最大的数)
//6.求x的后继(后继定义为大于x,且最小的数)
}
}
return 0;
}

指针+直接内存分配

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include<bits/stdc++.h>
using namespace std;
typedef struct Treap_Node//Treap数据结构
{
int key,priority;
int size,cnt;
Treap_Node *left,*right;
}TreapNode,*Treap;
int n;
Treap root,nil,ans;//根,哨兵
inline long random()
{
static int seed=19260817;
return seed=int(seed*48271LL%2147483647);
}
inline void init()//初始化根和哨兵节点
{
nil=(Treap)malloc(sizeof(TreapNode));
nil->left=nil->right=nil;
nil->cnt=nil->key=nil->size=0;
nil->priority=2147483647;
root=nil;
}
void update(Treap node)//更新节点size值
{
node->size=node->left->size+node->right->size+node->cnt;
}
Treap creat()//建立一个新节点
{
Treap node=new TreapNode;
node->cnt=1;
node->priority=random();
node->left=node->right=nil;
update(node);
return node;
}
void r_turn(Treap &node)//右旋
{
Treap tmp=node->left;
node->left=tmp->right;
tmp->right=node;
tmp->size=node->size;
update(node);
node=tmp;
}
void l_turn(Treap &node)//左旋
{
Treap tmp=node->right;
node->right=tmp->left;
tmp->left=node;
tmp->size=node->size;
update(node);
node=tmp;
}
void insert(Treap &node,int x)//插入
{
if(node==nil)//假如空节点
{
node=creat();//建立一个新节点
node->key=x;
return ;
}
node->size++;
if(node->key==x)//重复插入
node->cnt++;
else if(x>node->key)
{
insert(node->right,x);
if(node->right->priority<node->priority)
l_turn(node);
}
else
{
insert(node->left,x);
if(node->left->priority<node->priority)
r_turn(node);
}
}
void del(Treap &node,int x)//删除
{
if(node==nil)
return ;
if(node->key==x)
{
if(node->cnt>1)
{
node->cnt--;
node->size--;
}
else if(node->left==nil)
{
Treap tmp=node;
node=node->right;
delete tmp;
}
else if(node->right==nil)
{
Treap tmp=node;
node=node->left;
delete tmp;
}
else if(node->left->priority<node->right->priority)
{
r_turn(node);
del(node,x);
}
else
{
l_turn(node);
del(node,x);
}
}
else if(x>node->key)
{
node->size--;
del(node->right,x);
}
else
{
node->size--;
del(node->left,x);
}
}
int query_rank(Treap node,int x)//确定元素的秩
{
if(node==nil)
return 0;
if(node->key==x)
return node->left->size+1;
else if(x<node->key)
return query_rank(node->left,x);
else
return query_rank(node->right,x)+node->left->size+node->cnt;
}
int query_select(Treap node,int x)//查找给定秩的元素
{
if(node==nil)
return 0;
if(x<=node->left->size)
return query_select(node->left,x);
else if(x>node->left->size+node->cnt)
return query_select(node->right,x-node->left->size-node->cnt);
else
return node->key;
}
void query_before(Treap node,int x)//前驱
{
if(node==nil)
return;
if(node->key<x)
{
ans=node;
query_before(node->right,x);
}
else
query_before(node->left,x);
}
void query_after(Treap node,int x)//后继
{
if(node==nil)
return ;
if(node->key>x)
{
ans=node;
query_after(node->left,x);
}
else
query_after(node->right,x);
}
int main()
{
init();
scanf("%d",&n);
int mode,x;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&mode,&x);
switch(mode)
{
case 1:insert(root,x); break;
case 2:del(root,x); break;
case 3:printf("%d\n",query_rank(root,x)); break;
case 4:printf("%d\n",query_select(root,x)); break;
case 5:
{
ans=nil;
query_before(root,x);
printf("%d\n",ans->key);
break;
}
case 6:
{
ans=nil;
query_after(root,x);
printf("%d\n",ans->key);
break;
}
//1.插入x数
//2.删除x数(若有多个相同的数,因只删除一个)
//3.查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)
//4.查询排名为x的数
//5.求x的前驱(前驱定义为小于x,且最大的数)
//6.求x的后继(后继定义为大于x,且最小的数)
}
}
return 0;
}

神仙代码

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
#include<bits/stdc++.h>
#define TN T &N
#define R return
#define I int
#define V void
#define B break;
#define P if
#define E else
#define EI E P
#define NL N==ni
#define C case
#define X x)
#define O printf("%d\n"
#define U N->s=N->l->s+N->r->s+N->c;
typedef struct TR{I k,p,s,c;TR *l,*r;}*T;I n,m,x,D=2147483647;T rot,ni,ans;
long RA(){static I seed=19260817;R seed=I(seed*48271LL%D);}
T CR(){T N=new TR;N->c=1;N->p=RA();N->l=N->r=ni;U;R N;}
V rt(TN){T t=N->l;N->l=t->r;t->r=N;t->s=N->s;U;N=t;}
V lt(TN){T t=N->r;N->r=t->l;t->l=N;t->s=N->s;U;N=t;}
V IN(TN,I X{P(NL){N=CR();N->k=x;R;}N->s++;P(N->k==X N->c++;EI(x>N->k)
{IN(N->r,X;P(N->r->p<N->p)lt(N);}E{IN(N->l,X;P(N->l->p<N->p)rt(N);}}
V DE(TN,I X{P(NL)R;P(N->k==X{P(N->c>1){N->c--;N->s--;R;}
P(N->l==ni||N->r==ni)N=(N->l==ni)?(N->r):(N->l);
EI(N->l->p<N->r->p){rt(N);DE(N,X;}E{lt(N);DE(N,X;}}
EI(x>N->k){N->s--;DE(N->r,X;}E{N->s--;DE(N->l,X;}}
I qr(T N,I X{P(NL)R 0;P(N->k==X R N->l->s+1;
EI(x<N->k)R qr(N->l,X;E R qr(N->r,X+N->l->s+N->c;}
I qs(T N,I X{P(NL)R 0;P(x<=N->l->s)R qs(N->l,X;
EI(x>N->l->s+N->c)R qs(N->r,x-N->l->s-N->c);E R N->k;}
V qb(T N,I X{P(NL)R;P(N->k<X{ans=N;qb(N->r,X;}E qb(N->l,X;}
V qa(T N,I X{P(NL)R;P(N->k>X{ans=N;qa(N->l,X;}E qa(N->r,X;}
I main(){ni=new TR;ni->l=ni->r=rot=ni;ni->c=ni->k=ni->s=0;ni->p=D;
scanf("%d",&n);while(n--){scanf("%d%d",&m,&X;switch(m){
C 1:IN(rot,X;B C 2:DE(rot,X;B C 3:O,qr(rot,X);B C 4:O,qs(rot,X);B
C 5:ans=ni;qb(rot,X;O,ans->k);B C 6:ans=ni;qa(rot,X;O,ans->k);B}}R 0;}