// this is a node for an AVL tree. Balance information is maintained
// by keeping a height variable at the node.
class AVLTreeNode<K extends Comparable, V>
{
    int height;
    K key;
    V value;
    AVLTreeNode<K, V> left, right;

    AVLTreeNode( K k, V v, AVLTreeNode<K, V> l, AVLTreeNode<K, V> r )
    {
        key = k;
        value = v;
        left = l;
        right = r;
        setHeight();
    }

    K getKey() { return key; }

    void setKey( K k ) { key = k; }

    void setValue(V v){ value = v; }

    V getValue(){ return value; }

    void setLeft(AVLTreeNode<K, V> l){ left = l; }

    void setRight(AVLTreeNode<K, V> r){ right = r; }

    AVLTreeNode<K, V> getLeft(){ return left; }

    AVLTreeNode<K, V> getRight(){ return right; }

    int getHeight(){ return height; }

    void setHeight()
    {
        height = 1 + Math.max( getHeight( left ), getHeight( right ) );
    }

    // this is a convenience to avoid special cases where a node's child is null
    // the default is that the height of an empty tree is -1
    public int getHeight( AVLTreeNode<K, V> x )
    {
        if ( x == null ) return -1;
        else return x.getHeight();
    }

    boolean isBalanced()
    {
        return ( Math.abs( getHeight( left ) - getHeight( right ) ) <= 1 );
    }

    // returns the child of this node with the larger height.
    AVLTreeNode<K, V> tallerChild()
    {
        if ( getHeight( left ) > getHeight( right ) )
            return left;
        else return right;
    }
    
    // when doing a deletion in an AVL tree, if there is an unbalanced node
    // z, we want z's tallest child y and y's tallest child x. However, it's
    // possible that y has two children of the same height. In this case, if y
    // is a left child, we want to x to be y's left child. Similarly, if y is
    // a right child, we want x to be y's right child.
    AVLTreeNode<K, V> tallerChild( AVLTreeNode<K, V> parent )
    {
        if ( getHeight( left ) > getHeight( right ) )
            return left;
        else if ( getHeight( left ) < getHeight( right ) )
            return right;
        if ( parent.getLeft() == this )
            return left;
        else 
            return right;
    }
}