AVL实现，实现了add,get,remove等方法(有不同见解

package com.hcc.DStructure;

import java.util.ArrayList;
import java.util.concurrent.ArrayBlockingQueue;


/**
 * AVL
 * @author hcc
 *
 * @param <K>
 * @param <V>
 */
public class AVLBST<K extends Comparable<K>,V> {
    private Node root;
    private int size;
    
    public AVLBST() {
        this(null);
    }
    private AVLBST(Node root) {
        this.root = root;
        this.size = 0;
    }
    
    /**
     * 获取根节点的高度
     * @return
     */
    public int getHeight() {
        return getHeight(root);
    }
    /**
     * 获取某个节点的高度（规定没有左右孩子的节点的高度为1）
     * @param node
     * @return
     */
    private int getHeight(Node node) {
        return (null == node?0:node.height);
    }
    
    public int getBalanceFactor() {
        return getBalanceFactor(root);
    }
    /**
     * 获取某个节点的平衡因子 平衡因子：该节点的左孩子高度-该节点的右孩子高度
     * @param node
     * @return
     */
    private int getBalanceFactor(Node node) {
        if(node == null) {
            return 0;
        }
        return getHeight(node.left)-getHeight(node.right);
    }
    public void add(K key,V value) {
        root = add(root,key, value);
    }
    /**
     * 向树中添加数据
     * @param root
     * @param key
     * @param value
     * @return
     */
    private Node add(Node node,K key,V value) {
        if(null == node) {          
            size++;
            return new Node(key,value);
        }else if(key.compareTo(node.key) > 0) {
            node.right = add(node.right,key,value);
        }else if(key.compareTo(node.key) < 0) {
            node.left = add(node.left,key,value);
        }else{
            node.value = value;
        }
        //更新高度 子孩子的高度加1
        node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
        node = rotation(node);
        return node;
    }
    
    /**
     * 判断该树结构是否为二分搜索树(当list为空时，测试一下)
     * @return
     */
    public boolean isBST() {
        ArrayList<K> list = new ArrayList<K>();
        inOrder(root,list);
        for(int i =1;i < list.size();i++) {
            if(list.get(i-1).compareTo(list.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * 判断以根节点开始的树结构是否为平衡二叉树
     * @return
     */
    public boolean isAVLBST() {
        return isAVLBST(root);
    }
    /**
     * 判断以某节点为根的树结构是否为平衡二叉树
     * @return
     */
    public boolean isAVLBST(Node node) {
        if(null == node) {
            return true;
        }
        int balance = getBalanceFactor(node);
        if(Math.abs(balance) > 1) {
            return false;
        }
        return isAVLBST(node.left) && isAVLBST(node.right);
    }
    
    /**
     * 二叉树的中序遍历
     */
    private void inOrder(Node node,ArrayList<K> list) {
        if(null == node) {
            return;
        }
        inOrder(node.left,list);
        list.add(node.key);
        inOrder(node.right,list);
    }
    
    /**
     * 层序遍历
     */
    public void levelTraversal() {
        levelTraversal(root);
    }
    
    private void levelTraversal(Node node) {
        if(null == node) {
            return;
        }
        ArrayBlockingQueue<Node> queue = new ArrayBlockingQueue<Node>(this.size);
        queue.add(root);
        while(!queue.isEmpty()) {
            Node tempNode = queue.remove();
            K temp = tempNode.key;
            System.out.print(temp +" ");
            if(null != tempNode.left) {
                queue.add(tempNode.left);
            }
            if(null != tempNode.right) {
                queue.add(tempNode.right);
            }
        }
    }
    
    private StringBuilder levelTraversal(Node node,StringBuilder str) {
        if(null == node) {
            return null;
        }
        str.append("[key,value]:");
        ArrayBlockingQueue<Node> queue = new ArrayBlockingQueue<Node>(this.size);
        queue.add(root);
        while(!queue.isEmpty()) {
            Node tempNode = queue.remove();
            K tempKey = tempNode.key;
            V tempValue = tempNode.value;
            str.append("["+tempKey+","+tempValue+"]"+" ");
            if(null != tempNode.left) {
                queue.add(tempNode.left);
            }
            if(null != tempNode.right) {
                queue.add(tempNode.right);
            }
        }
        return str;
    }
    /**
     * 左旋转
     * @param node
     * @return
     */
    private Node leftRotation(Node node) {
        Node tempNode1 = node.right;
        Node tempNode2 = tempNode1.left;
        node.right.left = node;
        node.right = tempNode2;
        node.height = 1+Math.max(getHeight(node.left), getHeight(node.right));
        tempNode1.height = 1+Math.max(getHeight(tempNode1.left), getHeight(tempNode1.right));
        return tempNode1;
    }
    
    /**
     * 右旋转
     * @param node
     * @return
     */
    private Node rightRotation(Node node) {
        Node tempNode1 = node.left;
        Node tempNode2 = tempNode1.right;
        node.left.right = node;
        node.left = tempNode2   ;
        node.height = 1+Math.max(getHeight(node.left),getHeight(node.right));
        tempNode1.height = 1+Math.max(getHeight(tempNode1.left), getHeight(tempNode1.right));
        return tempNode1;
    }
    
    /**
     * 执行旋转操作
     * @param node
     */
    private Node rotation(Node node) {
        int balance = getBalanceFactor(node);
        if(balance > 1 && getBalanceFactor(node.left) >= 0) {
            node = rightRotation(node);
        }else if(balance < -1 && getBalanceFactor(node.right) <= 0 ) {
            node = leftRotation(node);
        }else if(balance > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotation(node.left);
            node = rightRotation(node);
        }else if(balance < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotation(node.right);
            node = leftRotation(node);
        }
        return node;
    }
    
    /**
     * 获取树中指定key对应的value值
     * @param key
     * @return
     */
    public V get(K key) {
        return get(root,key);
    }
    
    private V get(Node node,K key) {
        if(null == node) {
            return null;
        }else if(node.key.compareTo(key) == 0){
            return node.value;
        }else if(node.key.compareTo(key) > 0) {
            return get(node.left,key);
        }else {
            return get(node.right,key);
        }
    }
    /**
     * 删除树中指定的数据
     * @param key
     */
    public void remove(K key) {
        root = remove(root, key);
    }
    
    /**
     * 删除的具体的执行方法
     * @param node
     * @param key
     */
    private Node remove(Node node,K key) {
        if(null == node) {
            return null;
        }else if(node.key.compareTo(key) == 0) {
            Node tempNode = null;
            if(null == node.left && null == node.right) {
                size --;
                return tempNode;
            }else if(null != node.left && null == node.right) {
                tempNode = node.left;
                node.left = null;
                size--;
                return tempNode;
            }else  if(null == node.left && null != node.right) {
                tempNode = node.right;
                node.right = null;
                size --;
                return tempNode;
            }else {
                tempNode = removeMin(node.right);
                tempNode.left = node.left;
                tempNode.right = node.right;
                tempNode.height = 1+Math.max(getHeight(tempNode.left), getHeight(tempNode.right));
                node.left = null;
                node.right = null;
                size--;
                return tempNode;
            }
        }else if(node.key.compareTo(key) > 0) {
            node.left = remove(node.left,key);
        }else {
            node.right =remove(node.right,key);
        }
        node.height = 1+Math.max(getHeight(node.left),getHeight(node.right));
        node = rotation(node);
        return node;
    }
    
    /**
     * 
     */
    private Node removeMin(Node node) {
        if(null == node) {
            return null;
        }
        Node tempNode = null;
        while(null != node.left) {
            tempNode = node;
            tempNode.height = 1+Math.max(getHeight(tempNode.left)-1, getHeight(tempNode.right));
            node = node.left;
        }
        if(null !=node.right) {
            tempNode.left = node.right;
            tempNode.height = 1+Math.max(getHeight(tempNode.left), getHeight(tempNode.right));
        }
         node.right = null;
         size --;
         return node;
     }
    
    /**
     * 获取树的数据的个数
     * @return
     */
    public int getSize() {
        return size;
    }
    /**
     * 判空操作
     * @return
     */
    public boolean isEmpty() {
        return null == root;
    }
    
    /**
     * 判断某个元素在树中是否存在
     * @param key
     * @return
     */
    public boolean contains(K key) {
        return contains(root,key);
    }
    
    private boolean contains(Node node,K key) {
        if(null == node) {
            return false;
        }
        if(node.key.compareTo(key) == 0) {
            return true;
        }else if(node.key.compareTo(key) > 0) {
            return contains(node.left, key);
        }else{
            return contains(node.right, key);
        }
    }
    
    public String toString() {
        StringBuilder msgBuilder = new StringBuilder();
        return levelTraversal(root,msgBuilder).toString();
    }
    private class Node{
        //值
        public K key;
        public V value;
        //左右节点
        public Node left,right;
        //高度
        public int height;
        //长度

        public Node(K key,V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            this.height = 1;
        }
    }
}