---
tags: codebook
---
{%hackmd theme-dark %}
# randomized binary search tree

#include<iostream>
#include<vector>
#include<random>
#define size_t unsigned
using namespace std;
template<typename T>
struct rdized_bst{
	mt19937 rd;
	struct node{
		T v; size_t sz; node *l,*r;
		void update(){sz=1+(l?l->sz:0)+(r?r->sz:0);}
		node(const T& x):v(x),sz(1){l=r=nullptr;}
	} *root;
	void _print(ostream& os,node* cur){
		if(!cur) return;
		_print(os,cur->l);
		os<<cur->v<<' ';
		_print(os,cur->r);
	}
	friend ostream& operator<<(ostream& os,rdized_bst& t){
		t._print(os,t.root); return os;
	}
	node* _merge(node* a,node* b){
		if(!a) return b;
		if(!b) return a;
		uniform_int_distribution<size_t> dis(0,a->sz+b->sz);
		if(dis(rd)<a->sz){
			a->r=_merge(a->r,b);
			a->update();
			return a;
		}
		else{
			b->l=_merge(a,b->l);
			b->update();
			return b;
		}
	}
	void _split(node* cur,T x,node*& a,node*& b){
		if(!cur){a=b=nullptr;return;}
		if(cur->v<x)
			a=cur,_split(cur->r,x,a->r,b),a->update();
		else
			b=cur,_split(cur->l,x,a,b->l),b->update();
	}
	void insert(const T& x){
		node *l,*r;
		_split(root,x,l,r);
		root=_merge(_merge(l,new node(x)),r);
	}
	void erase(const T& k){
		node *l,*m,*r;
		_split(root,k,l,m);
		_split(m,k+1,m,r);
		root=_merge(l,r);
	}
	rdized_bst(const vector<T>& v={}):root(nullptr){
		for(const auto& i:v) insert(i);
	}
};
int main(){
	cin.tie(nullptr);cout.tie(nullptr);
	ios::sync_with_stdio(false);
	rdized_bst<int> tree;
	for(int n=0;n!=1e5;n++)
		tree.insert(n);
	cout<<tree<<endl;
	return 0;
}