private static AVLTreeNode rotateWithLeft(AVLTreeNode k2 )
        {
            AVLTreeNode k1 = k2.left;
            k2.left = k1.right;
            k1.right = k2;
            k2.height = Math.max( k2.left.height, k2.right.height ) + 1;
            k1.height = Math.max( k1.left.height, k2.height ) + 1;
            return k1;
        }

        private static AVLTreeNode rotateWithRight( AVLTreeNode k1 )
        {
            AVLTreeNode k2 = k1.right;
            k1.right = k2.left;
            k2.left = k1;
            k1.height = Math.max( k1.left.height, k1.right.height ) + 1;
            k2.height = Math.max( k2.right.height, k1.height ) + 1;
            return k2;
        }

        private static AVLTreeNode doubleWithLeft( AVLTreeNode k3 )
        {
            k3.left = rotateWithRight( k3.left );
            return rotateWithLeft( k3 );
        }

        private static AVLTreeNode doubleWithRight ( AVLTreeNode k1 )
        {
            k1.right = rotateWithLeft( k1.right );
            return rotateWithRight( k1 );
        }