据说平衡树界最经典的三大树是
SBT、Splay、Treap
从一道笔试题开始说起
上午帮舍友助攻阿里笔试的时候，遇上这么一道题：
输入是一些数对<a,b>，要求把它们用树结构存储下来，树的一个结点里面要同时保存a、b两个值，然后保证a是二叉搜索树性质，b是堆的性质。这样的树是唯一的。
我心想…平衡树+堆…Tree+Heap…这不就是Treap嘛!!!
然而几大平衡树里面我学了SBT、Splay，没学Treap哇，当时就心凉了半截。
好在仔细看了看题，感觉实现起来不太难，于是试了下。
以下是上面这棵树的实现：
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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct treenod
{
int left,right,a,b;
} treenode;
treenode tree[10000];
int father[10000];
int treetail,root;
void rleft(int now)
{
int fa=father[now],ffa=father[fa];
father[now]=ffa;
father[fa]=now;
tree[fa].right=tree[now].left;
tree[now].left=fa;
if (!ffa)
{
father[now]=0;
root=now;
} else
{
father[now]=ffa;
if (fa==tree[ffa].left)
{
tree[ffa].left=now;
} else
{
tree[ffa].right=now;
}
}
}
void rright(int now)
{
int fa=father[now],ffa=father[fa];
father[now]=ffa;
father[fa]=now;
tree[fa].left=tree[now].right;
tree[now].right=fa;
if (!ffa)
{
father[now]=0;
root=now;
} else
{
father[now]=ffa;
if (fa==tree[ffa].left)
{
tree[ffa].left=now;
} else
{
tree[ffa].right=now;
}
}
}
void check(int now)
{
while(father[now]&&tree[now].b>tree[father[now]].b)
{
if (now==tree[father[now]].left) rright(now);
else rleft(now);
}
}
void add(int r,int a,int b)
{
if (!treetail)
{
treetail++;
tree[1].a=a;
tree[1].b=b;
} else
{
if (a<tree[r].a)
{
if (!tree[r].left)
{
treetail++;
tree[r].left=treetail;
father[treetail]=r;
tree[treetail].a=a;
tree[treetail].b=b;
check(treetail);
} else add(tree[r].left,a,b);
} else
{
if (!tree[r].right)
{
treetail++;
tree[r].right=treetail;
father[treetail]=r;
tree[treetail].a=a;
tree[treetail].b=b;
check(treetail);
} else add(tree[r].right,a,b);
}
}
}
void outp(int now)
{
printf("<%d,%d>",tree[now].a,tree[now].b);
if (tree[now].left) outp(tree[now].left);
if (tree[now].right) outp(tree[now].right);
}
int main()
{
int a,b;
memset(tree,0,sizeof(tree));
memset(father,0,sizeof(father));
treetail=0;
root=1;
while(scanf("%d%d",&a,&b)==2)
{
add(root,a,b);
}
printf("%d %d\n",tree[root].a,tree[root].b);
outp(root);
return 0;
}
|
首先按照二叉搜索树的标准插入数据，然后进行堆结构调整。
正常的堆是满二叉树，直接使用子节点2倍和2倍+1的标号来维护，调整时是上下交换。而为了保证二叉搜索树的性质不被破坏，这里的调整需要用到子节点与父节点的左右旋来实现。
代码还是比较简单的。
然后既然今天开了这个头，下面顺手学习一下真正的Treap是怎么实现的。
Treap
真正的Treap其实跟上面那个结构已经非常像了，主体是二叉搜索树，然后在一般的结点之外另外加一个优先级的域，并且使用堆来维护优先级。
为什么要加个堆？
我们知道平衡树的出现是为了解决二叉搜索树可能不平衡的问题，因此平衡树越稳定（越平衡），那么进行操作时的渐进复杂度越接近$O(logn)$
Treap通过堆来限定了整棵平衡树的结构：
对于一棵二叉搜索树来说，给定的输入顺序不同，最终生成得到的可能是不同的树结构，而加上堆限定之后，整棵树的形态就固定了。
也就是说：
对于相同的一组数据，输入顺序并不改变Treap的最终形态；数据相同，则Treap的最终形态是唯一的
那么另外一个问题来了，正常情况下我们只会得到a序列，b是哪里来的呢？
答案是随机数！
输入数据时，我们对于每一个a都给它生成一个随机数b，然后按照堆的性质去维护b。给a序列加了个b序列之后，剩下的部分就跟上面的笔试题一样了，实现起来也比较简单。
数学上可以证明，随机数+堆的限定可以保证Treap达到$O(logn)$的期望深度。
后话
网上找到的一些资料上说Treap可以完成Splay的所有操作，我还没找到详细的说明。暂时还没有想明白。
如果只是按照上面那种限定死了的树结构的话，完全不明白这货是怎么可能达到像Splay那样灵活的。
上面的代码是上午临时打的，本来想好好改进下。
…
然后，网上搜了下别人的代码
…
找到一些版本的Treap是没有左右旋的！！
顿时就又吓到了！！
一个之前听说过，然而一直被吓到的新名词出现了：
可持久化数据结构！
可持久化Treap！
没有左右旋，而是使用切分和合并来完成整个结构的维护。
大概只有这种水平才能达到Splay的灵活性吧。
于是瞬间就不想改原来那个左右旋的代码了。待日后有兴趣了，再把可持久化这部分补上吧。