#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct AVL
{
	int d,h;
	AVL *L,*R;
	AVL(int _d=0)
	{
		d=_d,h=1,L=R=NULL;
	}
}*root;
inline int SIZE(AVL *tr)
{
	return tr?tr->h:0;
}
inline void up(AVL *tr)
{
	tr->h=max(SIZE(tr->L),SIZE(tr->R))+1;
}
inline AVL* RRotate(AVL *tr)
{
	AVL *x=tr,*y=tr->L;
	x->L=y->R;y->R=x;
	up(x);up(y);
	return y;
}
inline AVL* LRotate(AVL *tr)
{
	AVL *x=tr,*y=tr->R;
	x->R=y->L;y->L=x;
	up(x);up(y);
	return y;
}
inline AVL* RLRotate(AVL *tr)
{
	tr->R=RRotate(tr->R);
	return LRotate(tr);
}
inline AVL* LRRotate(AVL *tr)
{
	tr->L=LRotate(tr->L);
	return RRotate(tr);
}
void inorder(AVL* tr)
{
	if(!tr)return;
	inorder(tr->L);
	printf("%d ",tr->d);
	inorder(tr->R);
}
void INORDER(AVL *tr)
{
	inorder(tr);
	printf("size: %d\n",SIZE(tr));
}
AVL* insertnode(AVL *tr,int val)
{
	if(tr==NULL)
	{
		tr=new AVL(val);
		return tr;
	}
	if(tr->d==val)
		return tr;
	if(val<tr->d)
	{
		tr->L=insertnode(tr->L,val);
		if(SIZE(tr->L)-SIZE(tr->R)>1)
		{
			if(val<tr->L->d)
				tr=RRotate(tr);
			else
				tr=LRRotate(tr);
		}
	}
	else if(tr->d<val)
	{
		tr->R=insertnode(tr->R,val);
		if(SIZE(tr->R)-SIZE(tr->L)>1)
		{
			if(val>tr->R->d)
				tr=LRotate(tr);
			else
				tr=RLRotate(tr);
		}
	}
	up(tr);
	return tr;
}
int getmax(AVL* tr)
{
	int res;
	for(res=tr->d;tr;res=max(res,tr->d),tr=tr->R);
	return res;
}
int getmin(AVL* tr)
{
	int res;
	for(res=tr->d;tr;res=min(res,tr->d),tr=tr->L);
	return res;
}
AVL* deletenode(AVL* tr,int val)
{
	if(!tr)return tr;
	if(tr->d==val)
	{
		if(tr->L&&tr->R)
		{
			if(SIZE(tr->L)>SIZE(tr->R))
			{
				tr->d=getmax(tr->L);
				tr->L=deletenode(tr->L,tr->d);
			}
			else
			{
				tr->d=getmin(tr->R);
				tr->R=deletenode(tr->R,tr->d);
			}
			up(tr);
		}
		else
		{
			tr=tr->L?tr->L:tr->R;
		}
	}
	else if(val<tr->d)
	{
		tr->L=deletenode(tr->L,val);
		if(SIZE(tr->R)-SIZE(tr->L)>1)
		{
			if(SIZE(tr->R->L)>SIZE(tr->R->R))
				tr=RLRotate(tr);
			else
				tr=LRotate(tr);
		}
		up(tr);
	}
	else if(tr->d<val)
	{
		tr->R=deletenode(tr->R,val);
		if(SIZE(tr->L)-SIZE(tr->R)>1)
		{
			if(SIZE(tr->L->R)<SIZE(tr->L->L))
				tr=LRotate(tr);
			else
				tr=RRotate(tr);
		}
		up(tr);
	}
	return tr;
}
int main()
{
	root=NULL;
	srand(time(0));
	for(int i=0;i<20;i++)
		root=insertnode(root,i);
	INORDER(root);
	root=deletenode(root,16);
	puts("inorder");
	INORDER(root);
	for(int i=0;i<20;i++)
	{
		printf("deletenode: %d\n",i);
		root=deletenode(root,i);
		INORDER(root);
	}
	return 0;
}