AVL树

定义：首先是BST，而且任何一个节点的左子树和右子树高度差不超过1

AVL定义

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

    private AvlTreeNode root;
    public AvlTree() {
    }

    private class AvlTreeNode<T extends Comparable<T>> {
        private T key;

        private int height;
        private AvlTreeNode<T> left;
        private AvlTreeNode<T> right;

AVL树在插入和删除时会改变它的平衡结构，具体的不平衡情况如下所示：

• LL：节点左子树的左子树的高度高
• LR：节点左子树的右子树的高度高
• RL：节点右子树的左子树的高度高
• RR：节点右子树的右子树的高度高

AVL的旋转

为了保持平很需要进行旋转操作来保持平衡，4种不平衡情况具体的旋转操作情况如下：

LL与RR

LL旋转操作比较简单，只需要将不平衡的节点k2向右旋转，使得其左孩子k1成为“根”节点，然后k2成为其右孩子，k1的右子树称为k2的左子树，此时树已经平衡了，最后把k1和k2的高度进行更新
RR以此类似，只需要把k2向左旋转
LL旋转：

public AvlTreeNode leftLeftRotation(AvlTreeNode <T>node) {
    AvlTreeNode <T>left = node.left;
    node.left = left.right;
    left.right = node;
    node.height = Math.max(height(node.left), height(node.right)) + 1;
    left.height = Math.max(node.height, height(left.left)) + 1;
    return left;
}

RR旋转：

public AvlTreeNode rightRightRotation(AvlTreeNode<T> node) {
    AvlTreeNode <T>right = node.right;
    node.right = right.left;
    right.left = node;
    node.height = Math.max(height(node.left), height(node.right)) + 1;
    right.height = Math.max(node.height, height(right.right)) + 1;
    return right;
}

LR与RL

LR的旋转稍微复杂一点，首先对不平衡节点k3的左孩子k1进行一次“RR”旋转，这样树变成了LL不平衡状态，再进行一次“LL”旋转即可达到平衡
同样RL的旋转情况与之一一对应，先进行一次“LL”旋转然后进行一次“RR”旋转
LR与RL旋转：

public AvlTreeNode leftRightRotation(AvlTreeNode <T>node){
    node.left=rightRightRotation(node.left);
    return leftLeftRotation(node);
}

public AvlTreeNode rightLeftRotation(AvlTreeNode <T>node){
    node.right=leftLeftRotation(node.right);
    return rightRightRotation(node);
}

插入过程

插入过程和BST一样，但它会导致树不平衡，所以需要旋转来维持树的平衡：递归查询插入点，然后判断是否平衡，并根据不平衡类型做相应的旋转

public AvlTreeNode insert(T key, AvlTreeNode <T>node){
    if(node==null){
        node=new AvlTreeNode(key);
        return node;
    }
    if(node.key.compareTo(key)==0){
        throw new RuntimeException("节点值重复了");
    }else if(node.key.compareTo(key)>0){
        node.left=insert(key,node.left);
        if(height(node.left)-height(node.right)>1){
            if(node.left.key.compareTo(key)>0){
                node= leftLeftRotation(node);
            }else {
                node= leftRightRotation(node);
            }
        }
    }else {
        node.right=insert(key,node.right);
        if(height(node.right)-height(node.left)>1){
            if(node.right.key.compareTo(key)<0){
                node=rightRightRotation(node);
            }else {
                node=rightLeftRotation(node);
            }
        }
    }
    node.height=Math.max(height(node.left),height(node.right))+1;
    return node;
}

删除过程

删除过程首先定位到删除的节点，找出最“接近”（左子树高则选择左子树最大节点，然后处理左子树使其平衡，然后递归向上判断平衡；同样对于右子树高的情况，先找出右子树最小的节点来替代当前点，然后处理右子树使其平衡，最后递归向上使其平衡）的节点来替换它，最后处理子树平衡再向上递归处理不平衡
代码如下：

public AvlTreeNode remove(T key,AvlTreeNode <T>node){
    if(node==null||key==null){
        return null;
    }
    if(node.key.compareTo(key)>0){
        node.left=remove(key,node.left);
        if(height(node.right)-height(node.left)>1){
            if(height(node.right.left)>height(node.right.right)){
                node=rightLeftRotation(node);
            }else {
                node=rightRightRotation(node);
            }
        }
    }else if(node.key.compareTo(key)<0){
        node.right=remove(key,node.right);
        if(height(node.left)-height(node.right)>1){
            if(height(node.left.left)>=height(node.left.right)){
                node=leftLeftRotation(node);
            }else {
                node=leftRightRotation(node);
            }
        }
    }else{
        if(node.left==null){
            AvlTreeNode tmp=node;
            node=node.right;
            tmp.right=null;
        }
        else if(node.right==null){
            AvlTreeNode tmp=node;
            node=node.left;
            tmp.left=null;
        }
        else {
            if(height(node.left)>height(node.right)){
                AvlTreeNode<T> tmp=node.left;
                while(tmp.right!=null){
                    tmp=tmp.right;
                }
                node.key=tmp.key;
                node.left=remove(tmp.key,node.left);
            }else{
                AvlTreeNode <T>tmp=node.right;
                while(tmp.left!=null){
                    tmp=tmp.left;
                }
                node.key=tmp.key;
                node.right=remove(tmp.key,node.right);
            }
        }
    }
    if(node!=null) {
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }
    return node;
}

总结

AVL插入删除过程需要处理平衡，删除过程较复杂。所以效率比BST低，但是查询操作稳定为O(lgn)。