/** Tree class **/


class Tree{
	private	Node root;
	private final Node sentinel;


public Tree(){
	sentinel = new Node(0);
	sentinel.SetColorBlack();
	root = sentinel;

}

/* Find Node containding data */
public Node FindNode(int data){
	Node current = root;
	while(current != sentinel)
	{
		if (data == current.Data())
			return (current);
		else 
			if(data < current.Data())
				current = current.Left();
			else 	current = current.Right();
	} 	
		
	return null;
}

/* Rotate node x to left */
private void RotateLeft(Node x){
	
	Node y = x.Right();
	
	/* establish x.right link */
	x.SetRight(y.Left());
	if (y.Left() != sentinel)
		y.Left().SetParent(x);
		
	/* establish y.parent link */
	if (y != sentinel) y.SetParent(x.Parent());
	if (x.Parent() != null){
		if (x == x.Parent().Left())
			x.Parent().SetLeft(y);
		else 
			x.Parent().SetRight(y);
	}
	else root = y;

	
	/* link x and y */
	y.SetLeft(x);
	if (x != sentinel) x.SetParent(y);
}

/* Rotate node x to right */
private void RotateRight(Node x){

	Node y = x.Left();
	
	/* establish x.left link */
	x.SetLeft(y.Right());
	if (y.Right() != sentinel)
		y.Right().SetParent(x);

	/* establish y.parent link */
        if (y != sentinel) y.SetParent(x.Parent());
        if (x.Parent() != null){
                if (x == x.Parent().Right())
                        x.Parent().SetRight(y);
                else
                        x.Parent().SetLeft(y);
        }
        else root = y;


        /* link x and y */
        y.SetRight(x);
        if (x != sentinel) x.SetParent(y);

}

/* allocate node for data and insert in tree */
public boolean InsertNode(int data){
	Node parent;
	Node current;	
	Node x;
		
	/* find where node belong */
	current = root;
	parent = null;
	while (current != sentinel){
		if (data == current.Data()) return true;
		parent = current;
		if (data < current.Data()) current = current.Left();
		else current = current.Right();
	}
	
	/* setup new node */
	x = new Node(data);
	if (x == null) return false; 	
	x.SetLeft(sentinel);
	x.SetRight(sentinel);
	x.SetParent(parent);

	/* insert node in tree */
	if (parent != null) {
		if (data < parent.Data())
			parent.SetLeft(x);
		else parent.SetRight(x);
	}
	else root = x;
	
	InsertFixup(x);
	return (true);

}

/* delete node z from tree */
public void DeleteNode(Node z){

	Node x;
	Node y;
	
	if ( z == sentinel) return;
	
	if ( z.Left() == sentinel || z.Right() == sentinel){
		/* y has a sentinel node as a child */
		y = z;
	}
	else{
		/* find tree successor with a sentinel node as a child */
		y = z.Right();
		while ( y.Left() != sentinel) y = y.Left();
	}
	
	/* x is y's only child */
	if (y.Left() != sentinel)
		x = y.Left();
	else x = y.Right();

	/* remove y from the parent chain */
	x.SetParent(y.Parent());
	if (y.Parent() != null){
		if (y == y.Parent().Left())
			y.Parent().SetLeft(x);
		else y.Parent().SetRight(x);
	}
	else root = x;
	
	if (y != z) z.SetData(y.Data());
	
	if (y.IsBlack()) DeleteFixup(x);
	
}

/* maintain red-black tree balance after inserting node x */
private void InsertFixup(Node x){
	
	/* check red-black properties */
	while (x != root && x.Parent().IsRed()){
		/* we have a violation */
		if (x.Parent() == x.Parent().Parent().Left()){
			Node y = x.Parent().Parent().Right();
			if (y.IsRed()){
				
				/* uncle is red */
				x.Parent().SetColorBlack();
				y.SetColorBlack();
				x.Parent().Parent().SetColorRed();
				x = x.Parent().Parent();
			}
			else {
				/* uncle is black */
				if (x == x.Parent().Right()){
					/* make x a left child */
					x = x.Parent();
					RotateLeft(x);
				}
				
				/* recolor and rotate */
				x.Parent().SetColorBlack();
				x.Parent().Parent().SetColorRed();
				RotateRight(x.Parent().Parent());
			}
		}
		else{
			/* mirror image of above code */
			Node y = x.Parent().Parent().Left();
			if (y.IsRed()){
				/* uncle is red */
				x.Parent().SetColorBlack();
                                y.SetColorBlack();
                                x.Parent().Parent().SetColorRed();
                                x = x.Parent().Parent();
                        }
                        else {
                                /* uncle is black */
                                if (x == x.Parent().Left()){
                                        x = x.Parent();
                                        RotateRight(x);
                                }
                                
                                x.Parent().SetColorBlack();
                                x.Parent().Parent().SetColorRed();
                                RotateLeft(x.Parent().Parent());
                        }
                }
	}
	root.SetColorBlack();
}

/* maintain red-black tree balance after deleting node x */
private void DeleteFixup(Node x){

        while (x != root && x.IsBlack()){
                if (x == x.Parent().Left()){
                        Node w = x.Parent().Right();

                        if (w.IsRed()){
				w.SetColorBlack();
                                x.Parent().SetColorRed();
                       		RotateLeft(x.Parent());
				w = x.Parent().Right();
			}
                        if (w.Left().IsBlack() && w.Right().IsBlack()){
				w.SetColorRed();
				x = x.Parent();
			}
			else{
					
                                if (w.Right().IsBlack()){
                                       	w.Left().SetColorBlack();
					w.SetColorRed();
					RotateRight(w);
					w = x.Parent().Right();
                                }
               			
				if (x.Parent().IsBlack()) w.SetColorBlack();
				else w.SetColorRed();
				x.Parent().SetColorBlack();
				w.Right().SetColorBlack();
				RotateLeft(x.Parent());
				x = root;
		        }
                }
                else{
       			Node w = x.Parent().Left();

                        if (w.IsRed()){
                                w.SetColorBlack();
                                x.Parent().SetColorRed();
                                RotateRight(x.Parent());
                                w = x.Parent().Left();
                        }
                        if (w.Right().IsBlack() && w.Left().IsBlack()){
                                w.SetColorRed();        
                                x = x.Parent(); 
                        }       
                        else{   
                                        
                                if (w.Left().IsBlack()){
                                        w.Right().SetColorBlack();
                                        w.SetColorRed();
                                        RotateLeft(w);
                                        w = x.Parent().Left();
                                }
                                
                                if (x.Parent().IsBlack()) w.SetColorBlack();
                                else w.SetColorRed();
                                x.Parent().SetColorBlack();
                                w.Left().SetColorBlack();
                                RotateRight(x.Parent());
                                x = root;
                        }
 
	        }
        }
        x.SetColorBlack();

}

/* obtain the blackheight of the tree */
public int BlackHeight(){
	Node x;
	int height = 0;
	
	x = root;
	while (x != sentinel){
 		x = x.Left();
		if (x.IsBlack()) height++;

	}
	return height; 	
}

}