Basic Treap

basic_treap.cpp

// Rogerio Junior - @rogerioagjr
// Basic Treap

#include <bits/stdc++.h>

using namespace std;

struct node{
	
	int v, w;
	
	node *l, *r;
	
	node(int v_){
		
		v=v_, w=rand();
		l=r=NULL;
	}
};

bool find(node *t, int x){
	
	if(t==NULL) return false;
	
	if(t->v==x) return true;
	
	if(t->v<x) return find(t->r,x);
	return find(t->l,x);
}

void merge(node *&t, node *l, node *r){
	
	if(l==NULL){
		
		t=r;
		return;
	}
	
	if(r==NULL){
		
		t=l;
		return;
	}
	
	if(l->w>r->w){
		
		merge(l->r,l->r,r);
		t=l;
	}
	else{
		
		merge(r->l,l,r->l);
		t=r;
	}
}

void split(node *t, int v, node *&l, node *&r){
	
	if(t==NULL){
		
		l=r=NULL;
		return;
	}
	
	if(t->v>=v){
		
		split(t->l,v,l,t->l);
		r=t;
	}
	
	else{
		
		split(t->r,v,t->r,r);
		l=t;
	}
}

void insert(node *&t, int x){
	
	if(find(t,x)) return;
	
	node *l=NULL, *r=NULL;
	
	split(t,x,l,r);
	
	node *k=new node(x);
	
	merge(l,l,k);
	
	merge(t,l,r);
}

void erase(node *&t, int x){
	
	if(t==NULL or !find(t,x)) return;
	
	node *l=NULL, *aux=NULL, *r=NULL;
	
	split(t,x,l,r);
	split(r,x+1,aux,r);
	
	merge(t,l,r);
	
	delete aux;
}