treap cp algorithms

1struct item {
2    int key, prior;
3    item * l, * r;
4    item() { }
5    item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
6};
7typedef item * pitem;
8
9void split (pitem t, int key, pitem & l, pitem & r) {
10    if (!t)
11        l = r = NULL;
12    else if (key < t->key)
13        split (t->l, key, l, t->l),  r = t;
14    else
15        split (t->r, key, t->r, r),  l = t;
16}
17
18void insert (pitem & t, pitem it) {
19    if (!t)
20        t = it;
21    else if (it->prior > t->prior)
22        split (t, it->key, it->l, it->r),  t = it;
23    else
24        insert (it->key < t->key ? t->l : t->r, it);
25}
26
27void merge (pitem & t, pitem l, pitem r) {
28    if (!l || !r)
29        t = l ? l : r;
30    else if (l->prior > r->prior)
31        merge (l->r, l->r, r),  t = l;
32    else
33        merge (r->l, l, r->l),  t = r;
34}
35
36void erase (pitem & t, int key) {
37    if (t->key == key) {
38        pitem th = t;
39        merge (t, t->l, t->r);
40        delete th;
41    }
42    else
43        erase (key < t->key ? t->l : t->r, key);
44}
45
46pitem unite (pitem l, pitem r) {
47    if (!l || !r)  return l ? l : r;
48    if (l->prior < r->prior)  swap (l, r);
49    pitem lt, rt;
50    split (r, l->key, lt, rt);
51    l->l = unite (l->l, lt);
52    l->r = unite (l->r, rt);
53    return l;
54}
55