[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; 
    }