public class IntAVLClasses {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

class IntAVLNode {
		
		private int item;
		private int balance;
		private IntAVLNode left, right;
		
		public IntAVLNode(int d)	{
			item = d;
			balance = 0;
			left = null;
			right = null;
		}
		
		public int getBalance() {
			return balance;
		}
		
		public void setBalance(int bal) {
			balance = bal;
		}
		public int getItem(){
			return item;
		}
		public IntAVLNode getLeft() {
			return left;
		}
		public void setLeft(IntAVLNode pt){
			left = pt;
		}
		public IntAVLNode getRight(){
			return right;
		}
		public void setRight(IntAVLNode pt){
			right = pt;
		}
} // IntAVLNode


class IntAVLTree {
	
		private IntAVLNode tree;
		private int height;
		private IntAVLNode root;
		
		public IntAVLTree(){
			root = null;
			height = 0;
		}

// this is here just to make my life easier -- you would never do this
// in real life!
		public IntAVLNode getRoot(){
			return root;
		}

		// Rotate the node to the right
		
		public IntAVLNode rotateRight(IntAVLNode t){
			IntAVLNode temp;
				temp = t.getLeft();
			temp.setRight(t);
			t.setLeft(null);
			t.setBalance(t.getBalance()+2);
			temp.setBalance(temp.getBalance()+1);
			return temp;
			
		}
		public IntAVLNode rotateLeft(IntAVLNode t){
			IntAVLNode temp = t.getRight();
			temp.setLeft(t);
			t.setRight(null);
			t.setBalance(t.getBalance()-2);
			temp.setBalance(temp.getBalance()-1);
			return temp;
			
		}
	
		// Return the height of the tree
		public int height(){
			return height;
		}

		// Return the number of nodes where neither child is null
		/***********************************************
		public int dblCt(){
			if( t == null )
                return t;

            while( t.left != null )
                t = t.left;
            return t;
		}
		************************************************/
		public void insert(int d){
			root = insert( d, root );

		}
		
		
		private IntAVLNode insert(int d, IntAVLNode t) {
			
			
			if (t == null) // easiest case – inserted node goes here
			 t = new IntAVLNode( d );

			else if (d < t.getItem()) {
				int oldBalance = 0;
				int newBalance = 0;
				
				 	 
			//		 get the old balance of the left child (where the insertion
			//		 is taking place) – what should it be if there is no node?
	        
			if (t.getLeft() == null){
				oldBalance = t.getBalance();
				t.setLeft(insert( d, t.getLeft()));
				t.setBalance(t.getBalance()-1);
				newBalance=t.getBalance();
			}
		
				else  {
						oldBalance = t.getLeft().getBalance();
						t.setLeft(insert( d, t.getLeft()));
						t.setBalance(t.getBalance()-1);
						newBalance = t.getLeft().getBalance();					
					}
		
			if (t.getBalance() == -2)
		    t  =   rotateRight(t);
			
			
			
			}
			
			else if (d > t.getItem()) {
				int oldBalance = 0;
				int newBalance = 0;
				
				
				if (t.getRight() == null){
					oldBalance = t.getBalance();
					t.setRight(insert( d, t.getRight()));
					t.setBalance(t.getBalance()+1);
					newBalance=t.getBalance();
				}
			
					else  {
							oldBalance = t.getRight().getBalance();
							t.setRight(insert( d, t.getRight()));
							t.setBalance(t.getBalance()+1);
							newBalance = t.getRight().getBalance();					
						}
				if (t.getBalance() == 2)
				    t  =   rotateLeft(t);
		}
//		 else d is already in the tree
		return t;
		}

		
			
}// end of IntAVLTree class