Treap by frp-m.blogspot.com, old variant

treap.cpp

#include <cstdlib>
#include <vector>
using namespace std;
struct node
{
 int x, y;
 node *l, *r;
 node(int _x, int _y) : x(_x), y(y), l(0), r(0) {}
};
class treap
{
 node* root;
public:
 treap():root(0){}
 node* merge(node* a, node* b)
 {
  if(!a || !b)
   return a ? a : b;
  else if(a->y > b->y)
  {
   a->r = merge(a->r, b);
   return a;
  }
  else
  {
   b->l = merge(a, b->l);

   return b;
  }
 }
 pair<node*, node*> split(node* t, int x)
 {
  if(!t)return make_pair((node*)0, (node*)0);
  if(t->x <= x)
  {
   pair<node*, node*> p = split(t->r, x);
   t->r = p.first;
   return make_pair(t, p.second);
  }
  else
  {
   pair<node*, node*> p = split(t->l, x);
   t->l = p.second;
   return make_pair(p.first, t);
  }
 }
 void insert(int x)
 {
  pair<node*, node*> np1 = split(root, x);
  node* m = new node(x, rand());
  root = merge(merge(np1.first, m), np1.second);
 }
 void remove(int x)
 {
  pair<node*, node*> np1 = split(root, x - 1);
  pair<node*, node*> np2 = split(np1.second, x);
  delete np2.first;
  root = merge(np1.first, np2.second);
 }
 void traverse(node* t, vector<int>& res)
 {
  if(!t)return;
  if(t->l)traverse(t->l, res);
  res.push_back(t->x);
  if(t->r)traverse(t->r, res);
 }
 vector<int> traverse()
 {
  vector<int> r;
  traverse(root, r);
  return r;
 }
 bool check(node* t, int k)
 {
  if(!t)return false;
  else if(t->x == k)return true;
  else if(t->x < k)return check(t->l, k);
  else return check(t->r, k);
 }
 bool check(int k)
 {
  return check(root, k);
 }
};