/**simple implementation of an AVL tree*/

public class AVLTree<E extends Comparable<E>> {
  private AVLNode<E> root;
  private int size;
  
  public AVLTree(){
	  root=null;
	  size=0;
  }
  

public AVLNode<E> getRoot() {
	return root;
}

public void setRoot(AVLNode<E> r) {
	this.root = r;
}

public int getSize() {
	return size;
}

public void setSize(int size) {
	this.size = size;
}
//methods specific to AVL tree
/**return height of tree rooted at p*/
public int height(AVLNode<E> p){
	if (p==null) return -1;
	else return p.getHeight();
}

/**is the current node the root?*/
public boolean isRoot(AVLNode<E> p){
	return (p==root);
}

/**reset the heights of all the nodes in the tree starting at node p
 * return root of tree*/
public void resetHeights(AVLNode<E> p){
	if (p!=null){
		resetHeights(p.getLeft());
		resetHeights(p.getRight());
		if(isLeaf(p)) p.setHeight(0);
		else{
			if(p.getLeft()==null) p.setHeight(p.getRight().getHeight()+1);
			else{
				if (p.getRight()==null) p.setHeight(p.getLeft().getHeight()+1);
				else p.setHeight(max(p.getLeft().getHeight(),p.getRight().getHeight())+1);
	        }
		}
	}
}


public void resetHeights(){
	resetHeights(root);
}

private static int max(int i1,int i2){
	if(i1>=i2) return i1;
	else return i2;
}
/**Single right rotation about root node k1*/
public AVLNode<E> sRotateRight(AVLNode<E> k1){
	AVLNode<E> k2=k1.getLeft();
	k1.setLeft(k2.getRight());
	k2.setRight(k1);
	
	k1.setHeight(max(height(k1.getLeft()),height(k1.getRight()))+1);
	k2.setHeight(max(height(k2.getLeft()),height(k1))+1);
	return k2; //k2 is new root
}

/**Single left rotation about root node k1*/
public  AVLNode<E> sRotateLeft(AVLNode<E> k1){
	AVLNode<E> k2=k1.getRight();
	k1.setRight(k2.getLeft());
	k2.setLeft(k1);
	k1.setHeight(max(height(k1.getLeft()),height(k1.getRight()))+1);
	k2.setHeight(max(height(k2.getRight()),height(k1))+1);
	return k2;
	
}

/**Double left-right rotation about root node k1*/
public AVLNode<E> dRotateLeftRight(AVLNode<E> k1){
	AVLNode<E> k2=k1.getLeft();
	AVLNode<E> k3=k2.getRight();
	k1.setLeft(sRotateLeft(k2));
	sRotateRight(k1);
	return k3;
	
}

/**Double right-left rotation about root node k1*/
public AVLNode<E> dRotateRightLeft(AVLNode<E> k1){
	AVLNode<E> k2=k1.getRight();
	AVLNode<E> k3=k2.getLeft();
	k1.setRight(sRotateRight(k2));
	sRotateLeft(k1);
	return k3;
}
	
////////	
	

public boolean isEmpty(){
	return (root==null);
}

public boolean isEmpty(AVLNode<E> p){
	return (p==null);
}

public static boolean isLeaf(AVLNode p){
	return ((p.getLeft()==null)&&(p.getRight()==null));
}


  
/**insert node containing element e if doesn't already exist
 * starting at node p
 * @return root
 */
  public AVLNode<E> insert(E e, AVLNode<E> p){
	  if(p==null){
	    p=new AVLNode<E>(e,null,null,0);  size++; resetHeights();return p;}
	  
	  else{
		  int val=p.getElement().compareTo(e);
		  if (val>0) { //look in left branch
			 // System.out.println("looking in left branch");
			  p.setLeft(insert(e,p.getLeft()));
			  //rotate if necessary
			  
			 
			  if(height(p.getLeft())-height(p.getRight())==2){//too heavy on left now
				  boolean atRoot=isRoot(p);
				  if(e.compareTo(p.getLeft().getElement())<0) {
					//  System.out.println("Need a right rotation, about node containing " 
					//		  + p.getElement());
					  p=sRotateRight(p);
				  }
				  else{
					//  System.out.println("Need a leftright rotation");
					  p=dRotateLeftRight(p);
				  }
				  if(atRoot) root=p;
				  }
			  else resetHeights();
	
		  }
				  
		  else
			  if (val<0){//look in right branch
				  //System.out.println("looking in right branch");
				 p.setRight(insert(e,p.getRight()));
				 //rotate if necessary
				 if(height(p.getRight())-height(p.getLeft())==2){//too heavy on right now
					 boolean atRoot=isRoot(p);
					 if (e.compareTo(p.getRight().getElement())>0) {
						 //System.out.println("Need a left rotation");
						 p=sRotateLeft(p);
					 }
					 else {
						 //System.out.println("Need a rightleft rotation");
						   p=dRotateRightLeft(p);
					     //System.out.println("Returned node has value " + p.getElement());
							 
							// "\n and left child has value " + p.getLeft().getElement());
					 }
					 if(atRoot) root=p;
				 }
				 else resetHeights();
				 
				 }
	  
			
			  return p;
				  
			  
				  
			  
		  }
	 
	  }
  
  /**insert node containing e if doesnt already exist, starting at root*/
  public void insert(E e){
	  if (isEmpty()) {setRoot(new AVLNode<E>(e,null,null,0));size++;}
	  else 
		  setRoot(insert(e,getRoot()));
		  
  
  }

  
  /**see if tree contains value e
   * starting at node p*/
  public boolean contains(E e, AVLNode<E> p){
	  if(p==null) return false;
	  else{
		  int val=p.getElement().compareTo(e);
		  if(val==0) return true;
		  if (val>0) return contains(e,p.getLeft());
		  else return contains(e,p.getRight());
			
		  }
	  }
  
  /**see if tree contains value e*/
   public boolean contains(E e){
	   return contains(e,root);
   }
  
  /**remove the minimum element starting from a given node p
   * @return root
   */
  public AVLNode<E> removeMin(AVLNode<E> p){
	  if (isEmpty(p)) return null;
	  else{
		  if (isLeaf(p)) {size--;p=null;return null;}
		  else{
		    if (p.getLeft()==null){size--;return p.getRight();}
	        else {p.setLeft(removeMin(p.getLeft()));return p;}
		  }
	  }
  }
 
   
 /**this time return reference to minumum node starting from a given node p*/
  public AVLNode<E> findMin(AVLNode<E> p){
   if (isEmpty(p)) return null;
	   else{
		   if (p.getLeft()==null) return p;
		   else return findMin(p.getLeft());
		   }
	   }
  
  /**return reference to minumum node starting from root*/
  public AVLNode<E> findMin(){
   if (isEmpty()) return null;
	   else return(findMin(this.getRoot()));
		   
	   }
	
  /**remove node containing value e, starting from node p, if it exists*/
  public AVLNode<E> delete(E e,AVLNode<E> p){
	  if (p==null) return p; //item not found, do nothing
	  
	  int val=p.getElement().compareTo(e);
	  if(val<0) p.setRight(delete(e,p.getRight()));
	  else{
		  if(val>0) p.setLeft(delete(e,p.getLeft()));
		  else{
			  if (isLeaf(p)) {p=null;return null;} //no subtrees
			  else{
				  if (p.getLeft()==null) return p.getRight(); //no left subtree
				  if (p.getRight()==null) return p.getLeft(); //no right subtree
				  //only other alternative is two children
				  E tempElement=findMin(p.getRight()).getElement();
				  p.setElement(tempElement);
				  p.setRight(delete(tempElement,p.getRight()));
			  }
		  }
	  }
	  
	  
	  
	  return p; //only reach here if not previously returned
  }
   
  
  /**remove node containing value e if it exists, starting from root */
  public AVLNode<E> delete(E e){
	  if (isEmpty()) return null;
	  else return(delete(e,this.getRoot()));
  }
  
  

			  
/**create string using inorder traversal*/
  public String toString(AVLNode<E> p){
	  String s="";
	  if (p==null) return "";
	  s=toString(p.getLeft())+" " + p.getElement()+ " " + toString(p.getRight());
	  return s;
	  }
  
  public String toString(){
	  return this.toString(root);
  }
  
  
  
}