[javaSE] 数据结构（AVL树基本概念）

/**
 * 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;
    }