[写在前面的话]
如果想学Treap，请先了解BST和BST的旋转
二叉搜索树（BST）（百度百科）:[here]
可以戳这里(维基百科)
自己的博客:关于旋转（很水，顶多就算是了解怎么旋转，建议自行上百度）[here]
Treap(= binary search Tree + Heap)，中文通常译作树堆，为每个节点附加一个优先值，让优先值满足堆的性质，防止BST退化成一条链。
[节点定义]
每个节点像下面这样定义:
template<typename T>
class TreapNode{
public:
T data; //数据
int r; //（随机）优先级，用于满足堆的性质，防止退化成链
TreapNode* next[]; //两颗子树，0为左子树，1为右子树
TreapNode* father; //父节点，可选
TreapNode(T data, int r, TreapNode* father):data(data), r(r), father(father){
memset(next, , sizeof(next));
}
inline int cmp(T d){ //比较函数
if(d > data) return ;
return ;
}
};
[旋转操作]
如果像之前那张博客那样打旋转操作，那么到Splay的伸展函数的时候只能笑了。
static void rotate(TreapNode<T>*& node, int d){
TreapNode<T>* newRoot = node->next[d ^ ];
newRoot->father = node->father;
node->next[d ^ ] = newRoot->next[d];
node->father = newRoot;
newRoot->next[d] = node;
if(node->next[d ^ ] != NULL) node->next[d ^ ]->father = node;
if(newRoot->father != NULL) newRoot->father->next[newRoot->father->cmp(newRoot->data)] = newRoot;
}这里用d来表示旋转的方向。这样就不至于在旋转的时候后需要用一次if else
其实这里的father可以说用不到，只不过删除操作的时候需要把查找加到一起。
[插入操作]
插入操作时首先按照BST的插入方式进行插入，然后很快就会发现破坏了Heap的性质，比如说上面那张图插入了一个键值为10，优先级为4的节点，按照这个方法，会形成下图这种情形:
新插入的节点破坏了Heap的性质，那么只能同一种只会改变节点的位置，却不破坏BST的性质的方法来维护——旋转。
为了不制造更多的麻烦（就是通过旋转使其他节点破坏堆的性质），所以应该比父节点更小的那个节点以相反的方向（“有问题的节点”是它的右子树则左旋，否则右旋）旋转到“当前位置”。如下图:
最后经过调整，它满足了堆的性质:
下面是关于插入的完整代码:
//实际过程
static boolean insert(TreapNode<T>*& node, TreapNode<T>* father, T data, int d){
if(node == NULL){
node = new TreapNode<T>(data, rand(), father);
if(father != NULL) father->next[d] = node;
return true;
}
int d1 = node->cmp(data);
if(node->data == data) return false;
boolean res = insert(node->next[d1], node, data, d1);
if(node->next[d1]->r > node->r){
rotate(node, d1 ^ );
}
return res;
} //用户调用
boolean insert(T& data){
boolean res = insert(root, NULL, data, );
while(root->father != NULL) root = root->father;
return res;
}
[查找操作]
查找就根据BST的性质进行二分查找就可以了。
//实际过程
static TreapNode<T>* find(TreapNode<T>*& node, T data){
if(node == NULL || node->data == data) return node;
return find(node->next[node->cmp(data)], data);
} //用户调用
TreapNode<T>* find(T data){
return find(root, data);
} boolean count(T data){
return (find(root, data) != NULL);
}
[删除操作]
Treap的删除首先是要找到这个节点。可以试试下面这种情况（删除键值为3的节点）:
是不是看着怪怪的？那换个简单的，就把键值为9的节点删掉，维护很简单，直接用它唯一的子树来代替它的位置。
那么再来思考刚刚的问题，删掉键值为3的节点。既然当要删的节点只有一棵子树（或者没有子树）时特别简单，那么反正这个节点也是要删的，暂时破坏一下堆的性质，把它旋转到能够使它只有一个子树的时候，再把它删掉。为了不制造更多的麻烦（就在旋转时，让除去这个节点其他的节点破坏堆的性质），所以应该把更小的那一个子树旋转上来。如下图:
下面是删除操作的代码。
//实际过程
static void remove(TreapNode<T>*& node, TreapNode<T>*& root){
int direc = ((node->father != NULL) ? (node->father->cmp(node->data)) : (-));
if(node->next[] == NULL && node->next[] == NULL){
if(direc != -) node->father->next[direc] = NULL;
else root = NULL;
delete node;
}else if(node->next[] == NULL || node->next[] == NULL){
TreapNode<T>* stick = (node->next[] == NULL) ? (node->next[]) : (node->next[]);
if(direc == -){
root = stick;
stick->father = NULL;
}else{
node->father->next[direc] = stick;
stick->father = node->father;
}
delete node;
}else{
if(node->next[]->r < node->next[]->r) rotate(node, );
else rotate(node, );
while(root->father != NULL) root = root->father;
remove(node, root);
}
} //用户调用
boolean remove(T data){
TreapNode<T>* node = find(data);
if(node == NULL) return false;
remove(node, root);
return true;
}
这个代码真的写得不简洁，但是还是要注意下面这几个事项:
- 删除要改变父节点还有子节点的指针
- 旋转的方向
- 记得释放节点占用的内存(如果不是单个文件多组数据输入，其实一般也不会超内存)
[其它操作]
·lower_bound(T data)
还是来看刚刚那棵树，这次我们执行lower_bound(5)，很明显，这里结果是6。
首先从根节点开始访问（这不是废话吗），如果遇到相等的或者NULL就可以return了(这有用吗？)
仍然按照和查找一样的方法，以找到和它一样的节点为目标，于是可以得到了如下访问顺序
NULL
看起来被迫得返回了。在返回的过程中，找到的第一个大于它的就是结果，否则不存在。于是得到了6。
下面是代码(至少我认为这个代码还算比较简洁的。。):
//实际过程
static TreapNode<T>* lower_bound(TreapNode<T>*& node, T val){
if(node == NULL || node->data == val) return node;
int to = node->cmp(val);
TreapNode<T>* ret = lower_bound(node->next[to], val);
return (ret == NULL && node->data > val) ? (node) : (ret);
} //用户调用
TreapNode<T>* lower_bound(T data){
return lower_bound(root, data);
}
·upper_bound(T data)
upper_bound和lower_bound差不多，只不过在相等的时候是访问右子树。其它的都是一样的
//实际过程
static TreapNode<T>* upper_bound(TreapNode<T>*& node, T val){
if(node == NULL) return node;
int to = node->cmp(val);
if(val == node->data) to = ;
TreapNode<T>* ret = upper_bound(node->next[to], val);
return (ret == NULL && node->data > val) ? (node) : (ret);
} //用户调用
TreapNode<T>* upper_bound(T data){
return upper_bound(root, data);
}
[完整代码]
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != -);
if(x == -){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
} template<typename T>
class TreapNode{
public:
T data;
int r;
TreapNode* next[];
TreapNode* father;
TreapNode(T data, int r, TreapNode* father):data(data), r(r), father(father){
memset(next, , sizeof(next));
}
inline int cmp(T d){
if(d > data) return ;
return ;
}
}; template<typename T>
class Treap{
protected:
static boolean insert(TreapNode<T>*& node, TreapNode<T>* father, T data, int d){
if(node == NULL){
node = new TreapNode<T>(data, rand(), father);
if(father != NULL) father->next[d] = node;
return true;
}
int d1 = node->cmp(data);
if(node->data == data) return false;
boolean res = insert(node->next[d1], node, data, d1);
if(node->next[d1]->r > node->r){
rotate(node, d1 ^ );
}
return res;
} static TreapNode<T>* find(TreapNode<T>*& node, T data){
if(node == NULL || node->data == data) return node;
return find(node->next[node->cmp(data)], data);
} static void remove(TreapNode<T>*& node, TreapNode<T>*& root){
int direc = ((node->father != NULL) ? (node->father->cmp(node->data)) : (-));
if(node->next[] == NULL && node->next[] == NULL){
if(direc != -) node->father->next[direc] = NULL;
else root = NULL;
delete node;
}else if(node->next[] == NULL || node->next[] == NULL){
TreapNode<T>* stick = (node->next[] == NULL) ? (node->next[]) : (node->next[]);
if(direc == -){
root = stick;
stick->father = NULL;
}else{
node->father->next[direc] = stick;
stick->father = node->father;
}
delete node;
}else{
if(node->next[]->r < node->next[]->r) rotate(node, );
else rotate(node, );
while(root->father != NULL) root = root->father;
remove(node, root);
}
} static TreapNode<T>* lower_bound(TreapNode<T>*& node, T val){
if(node == NULL || node->data == val) return node;
int to = node->cmp(val);
TreapNode<T>* ret = lower_bound(node->next[to], val);
return (ret == NULL && node->data > val) ? (node) : (ret);
} static TreapNode<T>* upper_bound(TreapNode<T>*& node, T val){
if(node == NULL) return node;
int to = node->cmp(val);
if(val == node->data) to = ;
TreapNode<T>* ret = upper_bound(node->next[to], val);
return (ret == NULL && node->data > val) ? (node) : (ret);
} public:
TreapNode<T> *root; boolean insert(T& data){
boolean res = insert(root, NULL, data, );
while(root->father != NULL) root = root->father;
return res;
} TreapNode<T>* find(T data){
return find(root, data);
} boolean count(T data){
return (find(root, data) != NULL);
} boolean remove(T data){
TreapNode<T>* node = find(data);
if(node == NULL) return false;
remove(node, root);
return true;
} TreapNode<T>* lower_bound(T data){
return lower_bound(root, data);
} TreapNode<T>* upper_bound(T data){
return upper_bound(root, data);
} static void rotate(TreapNode<T>*& node, int d){
TreapNode<T>* newRoot = node->next[d ^ ];
newRoot->father = node->father;
node->next[d ^ ] = newRoot->next[d];
node->father = newRoot;
newRoot->next[d] = node;
if(node->next[d ^ ] != NULL) node->next[d ^ ]->father = node;
if(newRoot->father != NULL) newRoot->father->next[newRoot->father->cmp(newRoot->data)] = newRoot;
} //调试用函数
void out(TreapNode<T>* node){
if(node == NULL) return;
out(node->next[]);
printf("%d ", node->data);
out(node->next[]);
} }; Treap<int> t;
int main(){
srand((unsigned)time(NULL));
freopen("treap.in", "r", stdin);
freopen("treap.out", "w", stdout);
int n;
readInteger(n);
for(int i = , a; i <= n; i++){
getchar();
char op = getchar();
readInteger(a);
if(op == 'I'){
boolean aFlag = t.insert(a);
if(aFlag) printf("S\n");
else printf("F\n");
}else if(op == 'D'){
boolean aFlag = t.remove(a);
if(aFlag) printf("S\n");
else printf("F\n");
}else if(op == 'L'){
TreapNode<int>* d = t.lower_bound(a);
if(d == NULL) printf("NONE\n");
else printf("%d\n", d->data);
}else{
TreapNode<int>* d = t.upper_bound(a);
if(d == NULL) printf("NONE\n");
else printf("%d\n", d->data);
}
}
// t.out(t.root);
return ;
}
Treap
[后记]
可以用这份代码和STL的set比比速度，反正在我的电脑上插入、删除都比set快，只有lower_bound和upper_bound稍微比set慢一些。
只不过如果Treap只是做这些的话，直接用set就好了。
于是有了基于普通Treap的数据结构
| 名次树 | 为Treap的节点附加一个s来统计该子树上的节点总数， 然后旋转、插入、删除的时候维护，就可以来求k小值， 和某个数的排名 |
| 可持久化Treap | 实现可快速分裂合并的序列时，无论是代码量还是速度， 都轻松秒杀Splay |
提供测试数据和题目[here]