/**

 * AVL树测试

 * @author taoshihan

 * @param <T>

 *

 */

public class AVLTree<T extends Comparable<T>> {

    private AVLNode mRoot;//根节点

    class AVLNode<T extends Comparable<T>>{

        private T key;//键值

        private int height;//高度

        private AVLNode left;//左子树

        private AVLNode right;//右子树

        public AVLNode(T key,AVLNode left,AVLNode right) {

            this.key=key;

            this.left=left;

            this.right=right;

            this.height=0;

        }

    }

    /**

     * 获取节点高度

     * @param tree

     * @return

     */

    public int height(AVLNode<T> tree){

        if(tree!=null){

            return tree.height;

        }

        return 0;

    }

    /**

     * 取出左右子树中高的那个

     * @param a

     * @param b

     * @return

     */

    public int maxHeight(int a,int b){

        return a>b ? a : b;

    }

    /**

     * 左单旋转

     * @param k2

     * @return

     */

    public AVLNode<T> leftLeftRotation(AVLNode<T> k2){

        AVLNode k1;

        k1 = k2.left;

        k2.left=k1.right;

        k1.right=k2;

        k2.height=maxHeight(height(k2.left), height(k2.right));

        k1.height=maxHeight(height(k1.left), height(k1.right));

        return k1;

    }

    /**

     * 右单旋转

     * @param k2

     * @return

     */

    public AVLNode<T> rightRightRotation(AVLNode<T> k1){

        AVLNode k2;

        k2=k1.right;

        k1.right=k2.left;

        k2.left=k1;

        k2.height=maxHeight(height(k2.left), height(k2.right));

        k1.height=maxHeight(height(k1.left), height(k1.right));

        return k2;

    }