树堆，在数据结构中也称Treap(事实上在国内OI界常称为Traep,与之同理的还有"Tarjan神犇发明的"Spaly)，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。
我们可以看到，如果一个二叉排序树节点插入的顺序是随机的，这样我们得到的二叉排序树大多数情况下是平衡的，即使存在一些极端情况，但是这种情况发生的概率很小，所以我们可以这样建立一颗二叉排序树，而不必要像AVL那样旋转，可以证明随机顺序建立的二叉排序树在期望高度是O(logn)，但是某些时候我们并不能得知所有的带插入节点，打乱以后再插入。所以我们需要一种规则来实现这种想法，并且不必要所有节点。也就是说节点是顺序输入的，我们实现这一点可以用Treap。
Treap=Tree+Heap
Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。
操作
Treap维护堆性质的方法用到了旋转，这里先简单地介绍一下。Treap只需要两种旋转，这样编程复杂度比Splay等就要小一些，这正是Treap的特色之一。
旋转是这样的：
插入
给节点随机分配一个优先级，先和二叉排序树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比根大就旋转，如果当前节点是根的左儿子就右旋如果当前节点是根的右儿子就左旋。
我们如果把插入写成递归形式的话，只需要在递归调用完成后判断是否满足堆性质，如果不满足就旋转，实现非常容易。
由于是旋转的二叉排序树，最多进行h次(h是树的高度),插入的复杂度是log( n )的，在期望情况下，所以它的期望复杂度是 O( log( N ) );
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
void insert(int &k,int x)
{ if(k==0)
{
size++;k=size;
tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].rnd=rand();
return;
}
tr[k].size++;
if(tr[k].v==x)tr[k].w++;//每个结点顺便记录下与该节点相同值的数的个数
else if(x>tr[k].v)
{
insert(tr[k].r,x);
if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);//维护堆性质
}
else {
insert(tr[k].l,x);
if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);
}
} |
删除
有了旋转的操作之后，Treap的删除比二叉排序树还要简单。因为Treap满足堆性质，所以我们只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子，向与其相反的方向旋转，直到那个节点被旋转到叶节点，然后直接删除。删除最多进行log( n )次旋转，期望复杂度是log( n )。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void del(int &k,int x)
{ if(k==0)return;
if(tr[k].v==x)
{
if(tr[k].w>1)
{
tr[k].w--;tr[k].size--;return;//若不止相同值的个数有多个，删去一个
}
if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;//有一个儿子为空
else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
rturn(k),del(k,x);
else lturn(k),del(k,x);
}
else if(x>tr[k].v)
tr[k].size--,del(tr[k].r,x);
else tr[k].size--,del(tr[k].l,x);
} |
第二种删除方法：为保证效率，可以用普通二叉查找树的删除方法，找到节点的中序前缀，然后替换，删除，并使用非递归。虽然时间复杂度仍为log级别，但常数因子小了很多。
Pascal代码：
|
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
|
proceduredel(x:longint);var now,MinMax,p:point;
begin now:=root;//root为根指针
null^.x:=x;
whilenow^.x<>xdo
begin p:=now;
ifnow^.x>xthen
now:=now^.l
else now:=now^.r;
end; ifnow=nullthen//没找到X
exit;
ifnow^.l<>nullthen//左子树不为空，往左找
begin MinMax:=now^.l;
p:=now;
whileMinMax^.r<>nulldo
begin p:=MinMax;
MinMax:=MinMax^.r;
end; now^.x:=MinMax^.x;
ifp<>nowthen
p^.r:=MinMax^.l
else p^.l:=MinMax^.l;
dispose(MinMax);
endelse ifnow^.r<>nullthen//右子树不为空，往右找
begin MinMax:=now^.r;
p:=now;
whileMinMax^.l<>nulldo
begin p:=MinMax;
MinMax:=MinMax^.l;
end; now^.x:=MinMax^.x;
ifp<>nowthen
p^.l:=MinMax^.r
else p^.r:=MinMax^.r;
dispose(MinMax);
endelse//X本身是叶子
begin ifp^.x>xthen
p^.l:=null
else p^.r:=null;
dispose(now);
end;end; |
查找
和一般的二叉排序树一样，但是由于Treap的随机化结构，可以证明Treap中查找的期望复杂度是log( n )。
分离
要把一个Treap按大小分成两个Treap，只要在需要分开的位置加一个虚拟节点，然后旋至根节点删除，左右两个子树就是得出的两个Treap了。根据二叉排序树的性质，这时左子树的所有节点都小于右子树的节点。
时间相当于一次插入操作的复杂度，也就是 log( n )
合并
合并是指把两个Treap合并成一个Treap，其中第一个Treap的所有节点都必须小于或等于第二个Treap中的所有节点，也就是分离的结果所要满足的条件。合并的过程和分离相反，只要加一个虚拟的根，把两棵树分别作为左右子树，然后把根删除就可以了。
时间复杂度和删除一样，也是期望
旋转
旋转就是把random出来的值进行维护堆得性质的操作.因为BST得特殊性质,所以在旋转时,还要维护BST的性质。
|
1
2
3
4
5
6
7
8
9
10
|
void rturn(int &k)
{ int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;
k=t;
}void lturn(int &k)
{ int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;
tk=t;
} |
算法分析
首先我们注意到二叉排序树有一个特性，就是每个子树的形态在优先级唯一确定的情况下都是唯一的，不受其他因素影响，也就是说，左子树的形态与树中大于根节点的值无关，右子树亦然。
这是因为Treap满足堆的性质，Treap的根节点是优先级最大的那个节点，考虑它的左子树，树根也是子树里面最大的一点，右子树亦然。所以Treap相当于先把所有节点按照优先级排序，然后插入，实质上就相当于以随机顺序建立的二叉排序树，只不过它并不需要一次读入所有数据，可以一个一个地插入。而当这个随机顺序确定的时候，这个树是唯一的。
因此在给定优先级的情况下，只要是用符合要求的操作，通过任何方式得出的Treap都是一样的，所以不改变优先级的情况下，特殊的操作不会造成Treap结构的退化。而改变优先级可能会使Treap变得不够随机以致退化。
证明随机建立二叉排序树的大家可以参见CLRS P265 12.4 Randomly built binary search trees，这里略去。
我觉得这个模板挺好的！
模板
支持以下操作
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于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
|
//by hzwer#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;
struct data{
int l,r,v,size,rnd,w;
}tr[100005];int n,size,root,ans;
void update(int k)//更新结点信息
{ tr[k].size=tr[tr[k].l].size+tr[tr[k].r].size+tr[k].w;
}void rturn(int &k)
{ int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;
tr[t].size=tr[k].size;update(k);k=t;
}void lturn(int &k)
{ int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;
tr[t].size=tr[k].size;update(k);k=t;
}void insert(int &k,int x)
{ if(k==0)
{
size++;k=size;
tr[k].size=tr[k].w=1;tr[k].v=x;tr[k].rnd=rand();
return;
}
tr[k].size++;
if(tr[k].v==x)tr[k].w++;
else if(x>tr[k].v)
{
insert(tr[k].r,x);
if(tr[tr[k].r].rnd<tr[k].rnd)lturn(k);
}
else {
insert(tr[k].l,x);
if(tr[tr[k].l].rnd<tr[k].rnd)rturn(k);
}
}void del(int &k,int x)
{ if(k==0)return;
if(tr[k].v==x)
{
if(tr[k].w>1)
{
tr[k].w--;tr[k].size--;return;
}
if(tr[k].l*tr[k].r==0)k=tr[k].l+tr[k].r;
else if(tr[tr[k].l].rnd<tr[tr[k].r].rnd)
rturn(k),del(k,x);
else lturn(k),del(k,x);
}
else if(x>tr[k].v)
tr[k].size--,del(tr[k].r,x);
else tr[k].size--,del(tr[k].l,x);
}int query_rank(int k,int x)
{ if(k==0)return 0;
if(tr[k].v==x)return tr[tr[k].l].size+1;
else if(x>tr[k].v)
return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r,x);
else return query_rank(tr[k].l,x);
}int query_num(int k,int x)
{ if(k==0)return 0;
if(x<=tr[tr[k].l].size)
return query_num(tr[k].l,x);
else if(x>tr[tr[k].l].size+tr[k].w)
return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
else return tr[k].v;
}void query_pro(int k,int x)
{ if(k==0)return;
if(tr[k].v<x)
{
ans=k;query_pro(tr[k].r,x);
}
else query_pro(tr[k].l,x);
}void query_sub(int k,int x)
{ if(k==0)return;
if(tr[k].v>x)
{
ans=k;query_sub(tr[k].l,x);
}
else query_sub(tr[k].r,x);
}int main()
{ scanf("%d",&n);
int opt,x;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&opt,&x);
switch(opt)
{
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_num(root,x));break;
case 5:ans=0;query_pro(root,x);printf("%d\n",tr[ans].v);break;
case 6:ans=0;query_sub(root,x);printf("%d\n",tr[ans].v);break;
}
}
return 0;
} |