Treap

 1 /**************************************************
 2           Target: Treap
 3           Author: Xue Zhonghao
 4           Date: 2014-4-3 17:53:22 
 5 **************************************************/
 6 #include<cstdio>
 7 #include<iostream>
 8 //#include<fstream>
 9 using namespace std;
10 //ifstream fin("input.txt");
11 //ofstream fout("output.txt");
12 
13 //#define cin fin
14 //#define cout fout
15 
16 #define LL long long
17 
18 struct Node {
19     Node *ch[2];
20     int r;//heap value
21     LL v;//tree value
22     LL cmp(LL x) const {
23       if(x == v) return -1;
24       return x < v ? 0 : 1;
25     }
26 };
27 
28 //0 left rotate | 1 right rotate
29 void rotate(Node* &o, int d) {
30     Node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o = k;
31 }
32 
33 void insert(Node* &o, LL x) {
34     if(o == NULL) { o = new Node(); o->ch[0] = o->ch[1] = NULL; o->v = x; o -> r = rand(); }
35     else {
36       int d = o->cmp(x);
37       insert(o->ch[d], x); if(o->ch[d] ->r > o->r) rotate(o, d^1);;
38     }
39 }
40 
41 void remove(Node* &o, LL x) {
42     if(o == NULL) { cout<<"Delete failed"<<endl; return; }
43     int d = o->cmp(x);
44     if(d == -1) {
45       if(o->ch[0] == NULL) o = o->ch[1];
46       else if(o->ch[1] == NULL) o = o->ch[0];

47       else {
48         int d2 = (o->ch[0] ->r > o->ch[1] ->r ? 1 : 0);
49         rotate(o, d2); remove(o->ch[d2], x);
50       }
51     }
52     else
53       remove(o->ch[d], x);
54 }
55 
56 int find(Node* o, LL x) {
57     while(o != NULL) {
58       int d = o->cmp(x);
59       if(d == -1) return 1;
60       else o = o->ch[d];
61     }
62     return 0;
63 }
64 
65 int main(void)
66 {
67     Node* root = NULL;
68     char ch;
69     LL x;
70     int d;
71     while(1) {
72       do cin>>ch; while (ch == ‘ ‘ || ch == ‘\n‘);
73       if(ch == ‘I‘) {
74         cin>>x;
75         d = find(root, x);
76         if(!d) insert(root, x);
77         else  cout<<"Insert failed"<<endl;
78       }
79       else if(ch == ‘D‘) {
80         cin>>x;
81         remove(root, x);
82       }
83       else if(ch == ‘Q‘) {
84         cin>>x;
85         d = find(root, x);
86         if(d) cout<<"Yes"<<endl;
87         else cout<<"No"<<endl;
88       }
89       else if(ch == ‘C‘) break;
90     }
91     return 0;
92 }