如果一个二叉排序树节点插入的顺序是随机的，这样我们得到的二叉排序树大多数情况下是平衡的，Treap正是利用这一点来创建一棵相对平衡的二叉树。Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap。和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级，通过对优先级的随机赋值可以达到上述目的。
Treap的操作
插入
给节点随机分配一个优先级，先和二叉排序树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比根大就旋转，如果当前节点是跟的左儿子就右旋如果当前节点是跟个右儿子就左旋。
我们如果把插入写成递归形式的话，只需要在递归调用完成后判断是否满足堆性质，如果不满足就旋转，实现非常容易。
由于旋转是的，最多进行h次(h是树的高度),插入的复杂度是log( n )的，在期望情况下，所以它的期望复杂度是 O( log( N ) );
删除
有了旋转的操作之后，Treap的删除比二叉排序树还要简单。因为Treap满足堆性质，所以我们只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。
删除最多进行log( n )次旋转，期望复杂度是log( n )。
查找
和一般的二叉排序树一样，但是由于Treap的随机化结构，可以证明Treap中查找的期望复杂度是log( n )。
分离
要把一个Treap按大小分成两个Treap，只要在需要分开的位置加一个虚拟节点，然后旋至根节点删除，左右两个子树就是得出的两个Treap了。根据二叉排序树的性质，这时左子树的所有节点都小于右子树的节点。
时间相当于一次插入操作的复杂度，也就是 log( n )
合并
合并是指把两个Treap合并成一个Treap，其中第一个Treap的所有节点都必须小于或等于第二个Treap中的所有节点，也就是分离的结果所要满足的条件。合并的过程和分离相反，只要加一个虚拟的根，把两棵树分别作为左右子树，然后把根删除就可以了。
时间复杂度和删除一样，也是期望
代码
#include<iostream> #define maxn 100010 using namespace std; struct node{ int key,pri; node *ch[2]; }*root,*Null,tree[maxn]; int n,tot=0; node *New_Node(int x){ node *p=&tree[tot++]; p->key=x,p->pri=rand()*rand(),p->ch[0]=p->ch[1]=Null; return p; } void Rotate(node* &x,int c){ node *y=x->ch[c]; x->ch[c]=y->ch[!c]; y->ch[!c]=x,x=y; } void Insert(node* &now,node* new_node){ if (now==Null){ now=new_node; return; } int t=new_node->key>now->key; Insert(now->ch[t],new_node); if (now->ch[t]->pri>now->pri) Rotate(now,t); } void Mid_Order(node *x) { if (x == Null) return; Min_Order(x->ch[0]); printf("%d ", x->value); Mid_Order(x->ch[1]); } void print(node* x){ if (x==Null) return; print(x->ch[0]),cout< <x->key< <" ",print(x->ch[1]); } int main(){ srand(time(NULL)); cin>>n; Null=New_Node(0),root=Null; for (int i=0;i<n ;i++){ int x; cin>>x; Insert(root,New_Node(x)); } print(root); cout< <"\n"; system("pause"); return 0; }
why no Delete method?