According to Wikipedia, in computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.
The treap was first described by Cecilia R. Aragon and Raimund Seidel in 1989;[1][2] its name is a portmanteau of tree and heap. It is a Cartesian tree in which each key is given a (randomly chosen) numeric priority. As with any binary search tree, the inorder traversal order of the nodes is the same as the sorted order of the keys. The structure of the tree is determined by the requirement that it be heap-ordered: that is, the priority number for any non-leaf node must be greater than or equal to the priority of its children. Thus, as with Cartesian trees more generally, the root node is the maximum-priority node, and its left and right subtrees are formed in the same manner from the subsequences of the sorted order to the left and right of that node.
An equivalent way of describing the treap is that it could be formed by inserting the nodes highest-priority-first into a binary search tree without doing any rebalancing. Therefore, if the priorities are independent random numbers (from a distribution over a large enough space of possible priorities to ensure that two nodes are very unlikely to have the same priority) then the shape of a treap has the same probability distribution as the shape of a random binary search tree, a search tree formed by inserting the nodes without rebalancing in a randomly chosen insertion order. Because random binary search trees are known to have logarithmic height with high probability, the same is true for treaps.
Aragon and Seidel also suggest assigning higher priorities to frequently accessed nodes, for instance by a process that, on each access, chooses a random number and replaces the priority of the node with that number if it is higher than the previous priority. This modification would cause the tree to lose its random shape; instead, frequently accessed nodes would be more likely to be near the root of the tree, causing searches for them to be faster.
Naor and Nissim[3] describe an application in maintaining authorization certificates in public-key cryptosystems.
Here is an implementation of treap in very few lines of C++…
|
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 |
#include <iostream> using namespace std; const int INF = 200000000; class treap{ public: class node{ public: int x,y,c; node *l,*r; node(int data=0):x(data),c(0),l(0),r(0){y=((rand()<<15)+rand())%INF;} }; node *root, *null; public: treap(){null=new node(); null->l=null->r=null; null->y=INF; root=null; } void update(node*&p){ if(p!=null){p->c=p->l->c+p->r->c+1; }} void lr(node *&p){ node *q=p->l; p->l=q->r; q->r=p; update(p); update(q); p=q; } void rr(node *&p){ node *q=p->r; p->r=q->l; q->l=p; update(p); update(q); p=q; } void ins(node *&p, int x){ if (p==null){ p=new node(x); p->l=p->r=null; p->c=1; } else if (x<p->x) { ins(p->l,x); if(p->l->y<p->y) lr(p); } else { ins(p->r,x); if(p->r->y<p->y) rr(p); } update(p); } void del(node *&p, int x){ if (p==null) return; if (p->x==x) del(p); else if (x<p->x) del(p->l,x); else del(p->r,x); if (p!=null) update(p); } void del(node *&p){ if (p->l==null&&p->r==null) {delete p; p=null; return; } if (p->l->y<p->r->y) {lr(p); del(p->r); } else {rr(p); del(p->l); } update(p); } bool find(node *&p, int x){ if(p==null) return false; if (x==p->x) return true; if (x<p->x) return find(p->l,x); else return find(p->r,x); } int rfs(node *&p, int k){ if (k<=p->l->c) return rfs(p->l,k); else if (k==p->l->c+1) return p->x; else return rfs(p->r,k-p->l->c-1); } void ins(int x){ ins(root,x); } void del(int x){ del(root,x); } bool find(int x){ return find(root,x); } int rfs(int k){if (k>=1&&k<=root->c) return rfs(root,k); else return -1; } }; treap t; int n,m,x; char s[2]; int main(){ srand(time(0)^141592653); freopen("BST.in","r",stdin); freopen("BST.out","w",stdout); scanf("%d%d",&m,&n); for (int i = 0; i < n; ++i ){ scanf("%s%d",&s,&x); switch (s[0]) { case 'I': t.ins(x); break; case 'D': t.del(x); break; case 'F': printf("%d\n",t.rfs(x)); break; case 'B': printf("%d\n",t.find(x)); break; } } return 0; } //其实我的代码风格不是这样的，我很喜欢打空格...for (int i = 0; i < n; ++i ){ 这个是本来的风格... |
Really cool and elegant implementation, the best I found on the net. There was 1 confusing part though: lr and rr function names are swapped (lr is right rotation, rr is left rotation), which makes it a little bit harder to understand.
Thanks Adam for your correction. I am glad that it could help others. Actually, this is only for my own reference when competing in online algorithm competitions and the code style is horrible 🙂 Nevertheless, it works in several datasets 🙂