/* AVL Insertion 

  We will try to not have to implement a parent pointer, as that will place
  an overhead on all other code.  Instead, we will use a recursion stack
  to remember the parent.
*/


public class avlnode<Ty extends Comparable<Ty>> extends node<Ty>
{

    int height; // height of current node, to be dynamically maintained.

    // functions to make code look smoother: hides type-casting.
    public avlnode<Ty> left() { return (avlnode<Ty>)left; }
    public avlnode<Ty> right() { return (avlnode<Ty>)right; }


    // sets height value, and returns current balance (<0 means left heavy)
    int calcheight() // this is a constant time operation.
    {
       int hl = 0;
       int hr = 0;
       if (left!=null) hl = left().height;
       if (right!=null) hr = right().height;
       if (hl>hr) height = hl+1; else height = hr+1;
       return (hr-hl);
    }

    // constructors
    public avlnode(Ty h) { super(h); height = 1; }
    public avlnode(Ty h, avlnode<Ty> l, avlnode<Ty> r) 
     { super(h,l,r); 
       calcheight();
     } // standard constructor
    

    // Rotation operations 
    
    public void LL()  
    {
	if (left() == null) return;
	Ty temphead = head;
	avlnode<Ty> templeft = left();
	avlnode<Ty> tempright = right();
	head = left.head;
	left = left().left();
	right = new avlnode<Ty>(temphead,templeft.right(),tempright);
	calcheight();
    }

    public void RR()
    {
	if (right==null) return;
	Ty temphead = head;
	avlnode<Ty> templeft = left();
	avlnode<Ty> tempright = right();
	head = right.head;
	right = right.right;
	left = new avlnode<Ty>(temphead,templeft,tempright.left());
	calcheight();
    }
    
    // With this implementation, we are folding-in the LR and
    // RL double-rotation operations.  This implementation is not
    // the absolute most efficient, but is the clearest.

    // balance operation
    public void balance()
    {
	int hl = 0;  // height of subtrees
	int hr = 0;
	if (left!=null) hl = left().height;
	if (right!=null) hr = right().height;
	if ((hl-hr)>1) // left subtree too tall - LL or LR
	    {
		int lb = left().calcheight();
		if (lb<=0) // left hevy -single rotation
		    LL();
		else // double rotation   (LR)
		    {
			left().RR();
			LL();
		    }
	    }
	else if ((hr-hl)>1)
	    {
		int rb = right().calcheight();
		if (rb>=0) // right-heavy - single rotation
		    RR();
		else
		    {
			right().LL();     //(RL)
			RR();
		    }
	    }
    } // balance

    // new recursive insert operation; overrides node.insert
    public void insert(Ty x)
    {
	if (x.compareTo(head)<=0) // go left
	    {
		if (left==null) left = new avlnode<Ty>(x);
		else left().insert(x);
	    }
	else  // go right
	    {
		if (right==null) right = new avlnode<Ty>(x);
		else right().insert(x);
	    }
	calcheight();
	balance();
    } // insert



    /******** Revised procedures for deletion   **********/


    // utilities: find and return smallest node in a bst, deleting it if
    // possible
    avlnode<Ty> smallest()
    {
	avlnode<Ty> temp;
	if (this.left==null) return this;
	else if (this.left.left == null)
	    {
		temp = this.left();
		this.left = this.left.right; // null is wrong
		calcheight(); balance();
		return temp;
	    }
	else
	    {
		temp = left().smallest();
		calcheight(); balance();
		return temp;
	    }

    } // smallest


    avlnode<Ty> largest()
    {
	avlnode<Ty> temp;
	if (this.right==null) return this;
	else if (this.right.right == null)
	    {
		temp = this.right();
		this.right = this.right.left; //null;
		calcheight();  balance();
		return temp;
	    }
	else
	    {
		temp = right().largest();
		calcheight();  balance();
		return temp;
	    }

    } // largest


    // note that this method does not override: it's a new method.
    public avlnode<Ty> delete(Ty x) // delete first node found to contain x
    {
	if (x.compareTo(head)<0) // go left
	    {
		if (left!=null) 
		    {
  		      left = left().delete(x);
		      calcheight();
		      balance();
		    }
		return this;
	    }
	else if (x.compareTo(head)>0) // go right
	    {
		if (right!=null) 
		    { right=right().delete(x); calcheight(); balance(); }
		return this;
	    }
	else // node found (x.equals ( this.head ) )
	    {
		if (left==null && right==null) return null;
		if (left!=null) // use largest element on left subtree
		    {
			avlnode<Ty> rep = left().largest();
			if (rep==left()) 
			    {
				head = left.head; 
				this.left = left.left;
				if (left!=null) 
				    { left().calcheight(); left().balance(); }
			    }
			else // parent.right is the largest
			    {
				this.head = rep.head;
			    }
		    }
		else // use smallest element on right subtree
		    {
			node<Ty> rep = right().smallest();
			if (rep==right())
			    {
				head = right.head;
				this.right = right.right;
				if (right!=null) 
				    {right().calcheight(); right().balance();}
			    }
			else
			    {
				this.head = rep.head;
			    }
		    }
		calcheight();
		balance();
		return this;
	    }
    } // delete


} //avlnode