package tool;

public class AVLTree {
	boolean isSingle=false,left2right=false;
	int lHeight,rHeight;
	public AVLNode root=null;
	protected int nodecount=0;
	protected int getFactor(AVLNode subroot){
		if (subroot==null){
			return 0;
		}
		if (subroot.left==null){
			lHeight=0;
		}
		else{
			lHeight= subroot.left.height;
		}
		if (subroot.right==null){
			rHeight=0;
		}
		else{
			rHeight=subroot.right.height;
		}
		return lHeight-rHeight;
	}

	protected int getTreeHeight(AVLNode subroot){
		if(subroot==null){
			return 0;
		}
		if (subroot.left==null){
			lHeight=0;
		}
		else{
			lHeight=subroot.left.height;
		}
		if (subroot.right==null){
			rHeight=0;
		}
		else{
			rHeight=subroot.right.height;
		}
		return 1+(lHeight>rHeight?lHeight:rHeight);
		
	}
	protected void adjustHeight(AVLNode subroot){
		if (subroot==null){
			return;
		}
		subroot.height=getTreeHeight(subroot);
	}
	
	protected AVLNode doDouble(AVLNode oldRoot,boolean left2right){
		AVLNode small,mid,big,t1,t2,t3,t4;
		if (left2right){
			big=oldRoot;
			small=oldRoot.left;
			mid=small.right;
			t1=small.left;
			t2=mid.left;
			t3=mid.right;
			t4=big.right;
		}
		else{
			small=oldRoot;
			big=small.right;
			mid=big.left;
			t1=small.left;
			t2=mid.left;
			t3=mid.right;
			t4=big.right;
		}
		mid.left=small;
		mid.right=big;
		small.left=t1;
		small.right=t2;
		big.left=t3;
		big.right=t4;
		adjustHeight(small);
		adjustHeight(big);
		adjustHeight(mid);
		return mid;
	}
	protected AVLNode doubleRotate(AVLNode parent,boolean isRoot,boolean left2right){
			AVLNode oldRoot;
			boolean isLeft;
			if (isRoot){
				oldRoot=parent;
				root=doDouble(oldRoot, left2right);
				return root;
			}
			else{
				isLeft=parent.inLeft;
				oldRoot=parent.getSon(isLeft);
				parent.setSon(doDouble(oldRoot, left2right), isLeft);
				adjustHeight(parent);
				return parent;
			}
	}
	protected AVLNode singleRotate(AVLNode parent,boolean isRoot, boolean left2right){
			AVLNode oldRoot=parent,son,t1;
			boolean isLeft=parent.inLeft;
			if (isRoot){	
				son=parent.getSon(left2right);
				t1=son.getSon(!left2right);
				son.setSon(parent, !left2right);
				parent.setSon(t1, left2right);
				adjustHeight(parent);
				adjustHeight(son);
				root=son;
				return son;
			}
			else{
				
				oldRoot=parent.getSon(isLeft);
				son=oldRoot.getSon(left2right);
				t1=son.getSon(!left2right);
				parent.setSon(son, isLeft);
				oldRoot.setSon(t1, left2right);
				son.setSon(oldRoot, !left2right);
				adjustHeight(oldRoot);
				adjustHeight(son);
				adjustHeight(parent);
				return parent;
			}
		}
	protected void checkDir(AVLNode subroot){
				AVLNode son;
				int parentFactor, sonFactor;
				boolean isLeft;
				isLeft=subroot.inLeft;
				son=subroot.getSon(isLeft);
				parentFactor=getFactor(subroot);
				sonFactor=getFactor(son);
				if (sonFactor==0){
					son=subroot.getSon(!isLeft);
					sonFactor=getFactor(son);
					if (sonFactor==0){
						isSingle=true;
						left2right=parentFactor>0;
						return;
					}
				}
				isSingle=parentFactor*sonFactor>0;
				left2right=parentFactor>0;
	}
	protected void adjust(AVLNode subroot,boolean isRoot){
		AVLNode temp;
		boolean isLeft=false;
		if (isRoot){
			temp=subroot;
		}
		else{
			isLeft=subroot.inLeft;		
			temp=subroot.getSon(isLeft);
		}
		checkDir(temp);
		if (isSingle){
			subroot=singleRotate(subroot, isRoot, left2right);
		}
		else{
			subroot=doubleRotate(subroot, isRoot, left2right);
		}
	}
	protected void updateHeight(AVLNode subroot){
		if (subroot==null){
			return;
		}
		int factor, sonFactor;
		AVLNode son;
		adjustHeight(subroot);
		factor=getFactor(subroot);
		son=subroot.getSon(subroot.inLeft);
		sonFactor=getFactor(son);
		if ((factor==2||factor==-2)&&subroot==root){
			if (sonFactor==1||sonFactor==-1||sonFactor==0){
				adjust(subroot, true);
			}
			else{
				adjust(subroot, false);
			}				
		}
		else{
			if (sonFactor==2||sonFactor==-2)
			{
				adjust(subroot, false);
			}
		}
	}
	protected void inserthelp(AVLNode subroot,final AVLbuff val){
			if (subroot.it == null){
				subroot.Node(val,null,null,1);
				return;
			}
			if(EEComp.eq(val.getAVLnum(), subroot.it.getAVLnum())){
				System.out.println("Same AVLnum"+" "+val.getAVLnum()+" "+subroot.it.getAVLnum());
				return;
			}
			if (EEComp.lt(val.getAVLnum(), subroot.it.getAVLnum())){
				subroot.inLeft=true;
				if(subroot.left==null){
					subroot.left=new AVLNode();
				}
				inserthelp(subroot.left, val);
				updateHeight(subroot);
			}
			else{
				subroot.inLeft=false;
				if(subroot.right==null){
					subroot.right=new AVLNode();
				}
				inserthelp(subroot.right, val);
				updateHeight(subroot);
			}
	}
	public void insert(final AVLbuff val){
		if(root==null){
			root=new AVLNode();
		}
		inserthelp(root,val);
	}
	public AVLbuff find(long num){
		AVLNode ptr=root;
		while(true){
			if(ptr==null){
				return null;
			}
			if(num==ptr.it.getAVLnum()){
				return ptr.it;
			}
			if(num<ptr.it.getAVLnum()){
				ptr=ptr.left;
			}
			else{
				ptr=ptr.right;
			}
			
		}
	}
	public void clear(){
		root=null;
	}
	
}

class AVLNode{
	public AVLbuff it=null;
	public int height=0;
	public AVLNode left=null;
	public AVLNode right=null;
	public boolean inLeft;
	public AVLNode(){
		left=null;
		right=null;
		height=1;
		inLeft=true;
	}
	public void Node(AVLbuff e,AVLNode l,AVLNode r,int newHeight){
		it = e;
		left = l;
		right = r;
		height=newHeight;
		inLeft=true;
	}
	public boolean isLeaf(){ 
		return ((left==null)&&(right==null));
	}
	
	public AVLNode getSon(boolean isLeft){
		return isLeft?left:right;
	}
	
	public void setSon(AVLNode son, boolean isLeft){
		if(isLeft){
			left=son;
		}
		else{
			right=son;
		}
		
	}

}

class EEComp{
	static boolean lt(long e1, long e2)
		{ return e1<e2;}
	static boolean eq(long e1, long e2)
		{ return e1==e2;}
	static boolean gt(long e1, long e2)
		{ return e1>e2;}
}