Left Leaning Red Black Tree

left leaning red black tree.cpp

// 0 => black , 1 => red
//#define USE_234_TREE
#ifndef LEFT_LEANING_RB_TREE
#define LEFT_LEANING_RB_TREE
template<typename T>
class ll_rb_tree{
	private:
		struct node{
			node *l,*r;
			bool color;
			T data;
			node(const T&d):l(0),r(0),color(1),data(d){}
		}*root;
		inline node *left_rotate(node *a){
			node *b=a->r;
			a->r=b->l;
			b->l=a;
			b->color=a->color;
			a->color=1;
			return b;
		}
		inline node *right_rotate(node *a){
			node *b=a->l;
			a->l=b->r;
			b->r=a;
			b->color=a->color;
			a->color=1;
			return b;
		}
		inline void color_flip(node *o){
			o->color^=1;
			if (o->l)o->l->color^=1;
			if (o->r)o->r->color^=1;
		}
		inline bool is_red(node *o){return o?o->color:0;}
		node *insert(node *o,const T&data){
			if(!o)return new node(data);
	#ifdef USE_234_TREE
			if(is_red(o->l)&&is_red(o->r))color_flip(o);
	#endif
			if(o->data<data)o->r=insert(o->r,data);
			else o->l=insert(o->l,data);
			if(is_red(o->r)&&!is_red(o->l))o=left_rotate(o);
			if(is_red(o->l)&&is_red(o->l->l))o=right_rotate(o);
	#ifndef USE_234_TREE
			if(is_red(o->l)&&is_red(o->r))color_flip(o);
	#endif
			return o;
		}
		inline node *move_red_left(node *o){
			color_flip(o);
			if(o->r&&is_red(o->r->l)){
				o->r=right_rotate(o->r);
				o=left_rotate(o);
				color_flip(o);
			}
			return o;
		}
		inline node *move_red_right(node *o){
			color_flip(o);
			if(o->l&&is_red(o->l->l)){
				o=right_rotate(o);
				color_flip(o);
			}
			return o;
		}
		inline node *fix_up(node *o){
			if(is_red(o->r))o=left_rotate(o);
			if(is_red(o->l)&&is_red(o->l->l))o=right_rotate(o);
			if(is_red(o->l)&&is_red(o->r))color_flip(o);
			return o;
		}
		node *erase_min(node *o){
			if(!o->l){
				delete o;
				return NULL;
			}
			if(!is_red(o->l)&&!is_red(o->l->l))o=move_red_left(o);
			o->l=erase_min(o->l);
			return fix_up(o);
		}
		node *erase(node *o,const T&data){
			if(data<o->data&&o->l){
				if(!is_red(o->l)&&!is_red(o->l->l))o=move_red_left(o);
				o->l=erase(o->l,data);
			}else{
				if(is_red(o->l))o=right_rotate(o);
				bool d=o->data<data;
				if(!d&&!o->r){
					delete o;
					return NULL;
				}
				if(o->r){
					if(!is_red(o->r)&&!is_red(o->r->l))o=move_red_right(o);
					if(d)o->r=erase(o->r,data);
					else{
						node *t=o->r;
						while(t->l)t=t->l;
						o->data=t->data;
						o->r=erase_min(o->r);
					}
				}
			}
			return fix_up(o);
		}
		void clear(node *o){if(o)clear(o->l),clear(o->r),delete o;}
	public:
		ll_rb_tree():root(0){}
		~ll_rb_tree(){clear(root);}
		inline void clear(){clear(root),root=0;}
		inline bool find(const T &data){
			node *p=root;
			while(p)if(p->data==data)return 1;
			else if(p->data<data)p=p->r;
			else p=p->l;
			return 0;
		}
		inline void insert(const T&data){
			root=insert(root,data);
			root->color=0;
		}
		inline void erase(const T&data){
			if(root){
				root=erase(root,data);
				if(root)root->color=0;
			}
		}
};
#endif