---
tags: codebook
---

# Splay Tree

#include<iostream>
#include<array>
#include<vector>
using namespace std;
struct splay_tree{
	struct node{
		int val; node *p;
		array<node*,2> ch;
		node(const int& x,node* anc):
			val(x),p(anc){ch[0]=ch[1]=nullptr;}
		bool side() const {
			return this==this->p->ch[1];
		}
		void attach(bool direc, node *const ptr){
			if(ptr) ptr->p=this;
			this->ch[direc]=ptr;
		}
		void rotate(){
			const auto anc = this->p;
			const bool direc=this->side();
			if(anc->p)
				anc->p->attach(this->p->side(), this);
			else
				this->p = nullptr;
			anc->attach(direc, this->ch[!direc]);
			this->attach(!direc, anc);
		}
		node* splay(){
			while(this->p)
				if(!this->p->p) this->rotate();
				else this->p->rotate(), this->rotate();
			return this;
		}
	}*root;	
	bool insert(const int& x){
		node **cur=&root,*anc=nullptr;
		while(*cur&&(*cur)->val!=x)
			anc=*cur,cur=&((*cur)->ch[x>(*cur)->val]);
		if(*cur) return false;
		*cur=new node(x,anc),root=(*cur)->splay();
		return true;
	}
	void merge(splay_tree&& b){
		node *cur=root;
		while(cur->ch[1]) cur=cur->ch[1];
		root=cur->splay();
		this->root->ch[1]=b.root;
		b.root->p=this->root;
		b.root=nullptr;
	}
	bool erase(const int& x){
		node *cur=root;
		while(cur&&cur->val!=x) cur=cur->ch[x>cur->val];
		if(!cur) return false;
		root=cur->splay();
		for(int i=0;i!=2;i++){
			if(!root->ch[i]) {
				root=root->ch[!i];
				return true;
			}
			root->ch[i]->p=nullptr;
		}
		const auto rch=root->ch[1];
		root=root->ch[0];
		this->merge(splay_tree(rch));
		return true;
	}
	splay_tree(node* x):root(x){}
	splay_tree(initializer_list<int> v):root(nullptr){
		for(const auto& i:v)
			insert(i);
	}
};
int main(){
	splay_tree tree({1,5,4,2,0,3,6,7,9,8,0});
	tree.erase(0);
	return 0;
}