Treap

 1 struct treap_node {
 2     treap_node *left, *right;
 3     int value, fix;
 4 };
 5 void treap_left_rotate(treap_node *&a) {
 6     treap_node *b = a->right;
 7     a->right = b->left;
 8     b->left = a;
 9     a = b;
10 }
11 void treap_right_rotate(treap_node *&a) {
12     treap_node *b = a->left;
13     a->left = b->right;
14     b->right = a;
15     a = b;
16 }
17 void treap_insert(treap_node *&a, int value) {
18     if(a == NULL) {
19         a = new treap_node;
20         a->value = value;
21         a->fix = rand();
22         a->left = a->right = NULL;
23     } else if(value < a->value) {
24         treap_insert(a->left, value);
25         if(a->left->fix < a->fix) treap_right_rotate(a);
26     } else {
27         treap_insert(a->right, value);
28         if(a->right->fix < a->fix) treap_left_rotate(a);
29     }
30 }
31 void treap_delete(treap_node *&a, int value) {
32     if(value == a->value) {
33         if(!a->left || !a->right) {
34             treap_node *t = a;
35             if(!a->left) a = a->right;
36             else a = a->left;
37             delete t;
38         } else {
39             if(a->left->fix < a->right->fix) {
40                 treap_right_rotate(a);
41                 treap_delete(a->right, value);
42             } else {
43                 treap_left_rotate(a);
44                 treap_delete(a->left, value);
45             }
46         }
47     } else {
48         if(value < a->value) treap_delete(a->left, value);
49         else treap_delete(a->right, value);
50     }
51 }