splay_tree.cpp

// Thiago Mota
// Splay Tree Implementation

#include <iostream>
#include <vector>

using namespace std;

struct node{
	int val;
	node *l, *r;
	node(int val=0):
		val(val),
		l(nullptr), r(nullptr)
	{}	
};

ostream& operator<<(ostream& out, node* root){
	if(root) out << root->l << root->val << " " << root->r;
	return out;
}

inline void zig(node*& root){ // Right Rotate
	node *novo = root->l;
	root->l = novo->r;
	novo->r = root;
	root = novo;
}

inline void zag(node*& root){ // Left Rotate
	node *novo = root->r;
	root->r = novo->l;
	novo->l = root;
	root = novo;
}

void splay(node*& root, int val){
	if(root == nullptr || root->val == val)
		return;
	
	if(val < root->val){ // Left subtree
		if(root->l == nullptr)
			return;

		if(val < root->l->val){ // Zig-Zig
			splay(root->l->l, val);

			zig(root);
		}else if(val > root->l->val){ // Zig-Zag
			splay(root->l->r, val);

			if(root->l->r)
				zag(root->l);
		}

		if(root->l) zig(root);
	}else{ // Right subtree
		if(root->r == nullptr)
			return;

		if(val < root->r->val){ // Zag-Zig;
			splay(root->r->l, val);

			if(root->r->l)
				zig(root->r);
		}else if(val > root->r->val){ // Zag-Zag
			splay(root->r->r, val);

			zag(root);
		}

		if(root->r) zag(root);
	}
}

bool find(node*& root, int val){
	splay(root, val);
	return (root && root->val == val);
}

void insert(node*& root, int val){
	if(root == nullptr){
		root = new node(val);
		return;
	}
	if(root->val == val) return;

	if(val < root->val){ // Left subtree
		if(root->l == nullptr){
			root->l = new node(val);
		}else if(val < root->l->val){ // Zig-Zig
			insert(root->l->l, val);

			zig(root);
		}else if(val > root->l->val){ // Zig-Zag
			insert(root->l->r, val);

			if(root->l->r)
				zag(root->l);
		}

		if(root->l) zig(root);
	}else{ // Right subtree
		if(root->r == nullptr){
			root->r = new node(val);
		}
		else if(val < root->r->val){ // Zag-Zig
			insert(root->r->l, val);

			if(root->r->l)
				zig(root->r);
		}else if(val > root->r->val){ // Zag-Zag
			insert(root->r->r, val);

			zag(root);
		}

		if(root->r) zag(root);
	}
}

inline void erase(node*& root, int val){
	if(root == nullptr)
		return;

	splay(root, val);

	if(root->l == nullptr){
		node *aux = root;
		root = root->r;
		delete aux;
	}else{
		node *aux = root;

		root = root->l;
		splay(root, val);
		root->r = aux->r;
		delete aux;
	}
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	
	return 0;
}