public class LLRB {

	public class LLRBNode {
		public boolean color;	// true == red
		public LLRBNode left, right;
		public Comparable key;
	
		public LLRBNode ( Comparable i ) {
			color = true; // red
			left = null;
			right = null;
			key = i;
		}
	}
	
	public LLRBNode root;
	public int size;

	
	public LLRB () {
		root = null;
		size = 0;
	}
	
	public int height() {
		return height(root,1);
	}
	
	private int height(LLRBNode h, int lvl) {
		if (h != null)	return Math.max(height(h.left,lvl+1), height(h.right,lvl+1));
			else return lvl-1;
	}
	
	public LLRBNode search (Comparable key) {
		LLRBNode x = root;
		while (x != null) {
			int cmp = key.compareTo(x.key);
			if (cmp == 0) return x;
				else if (cmp < 0) x = x.left;
					else if (cmp > 0) x = x.right;
		}		
		return null;
	}
	
	public boolean isRed ( LLRBNode h ) {
		if (h != null) return h.color; else return false;
	}	
	
	public LLRBNode fixUp ( LLRBNode h ) {
		if ( isRed(h.right) && !isRed(h.left) ) h = rotateLeft(h);
		if ( isRed(h.left) && isRed(h.left.left) ) h = rotateRight(h);
		return h;
	}
	
	public LLRBNode rotateLeft ( LLRBNode h ) {
		LLRBNode x = h.right;
		h.right = x.left;
		x.left = h;
		x.color = h.color;
		h.color = true; // red
		
		return x;
	}
	
	public LLRBNode rotateRight ( LLRBNode h ) {
		LLRBNode x = h.left;
		h.left = x.right;
		x.right = h;
		x.color = h.color;
		h.color = true; // red
				
		return x;
	}
	
	public void colorFlip ( LLRBNode h ) {
		h.color = !h.color;
		if (h.left != null) h.left.color = !h.left.color;
		if (h.right != null) h.right.color = !h.right.color;
	}

	private LLRBNode moveRedLeft ( LLRBNode h ) {
		colorFlip(h);
		if (h.right != null)  if (isRed(h.right.left)) {
			h.right = rotateRight(h.right);
			h = rotateLeft(h);
			colorFlip(h);
		}
		return h;
	}
	
	private LLRBNode moveRedRight ( LLRBNode h ) {
		colorFlip(h);
		if (h.left != null) if (isRed(h.left.left)) {
			h = rotateRight(h);
			colorFlip(h);
		}
		return h;
	}
	
	public void insert ( Comparable key ) {
		root = insert( root, key );
	}
	
	private LLRBNode insert ( LLRBNode h, Comparable key ) {
		if (h == null) { size++; return new LLRBNode(key); }
		
		if (isRed(h.left) && isRed(h.right)) colorFlip(h);
		
		int cmp = key.compareTo( h.key );
		
		if (cmp < 0) 	h.left = insert( h.left, key );
		else				h.right = insert( h.right, key );

		return fixUp(h);
	}
	
	private LLRBNode deleteMin ( LLRBNode h ) {
		if (h.left == null) { size--; return null;}
		
		if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h);
		
		h.left = deleteMin(h.left);
		
		if ( isRed(h.left) && isRed(h.right) ) colorFlip(h);

		return fixUp(h);
	}
	
	private LLRBNode min ( LLRBNode h ) {
		if (h.left != null) return min(h.left); else return h;
	}
	
	public void delete (Comparable key) {
		root = delete(root, key);
		if (root != null) root.color = false; // black
	}
	
	private LLRBNode delete (LLRBNode h, Comparable key) {
	
		if (key.compareTo(h.key) < 0) {
			if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h);
			h.left = delete( h.left, key );
		} else {
			if ( isRed(h.left) ) h = rotateRight(h);
			if (key.compareTo(h.key) == 0 && (h.right == null)) { size--; return null; }
			if ( !isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
			if (key.compareTo(h.key) == 0) {
 				h.key = min( h.right ).key;
				h.right = deleteMin( h.right);
			} else 
				h.right = delete(h.right, key);
		}
	
		if ( isRed(h.left) && isRed(h.right) ) colorFlip(h);

		return fixUp(h);
	}	
}