二叉树之AVL

AVL是什么？

AVL树又称平衡二叉树，它也是一颗二叉查找树，但在二叉查找树中，某个结点的左右子树高度之差的绝对值可能会超过1，称之为不平衡。而在平衡二叉树中，任何结点的左右子树高度之差的绝对值会小于等于 1。

AVL产生的意义？

在二叉查找树中最坏情况下查找某个元素的时间复杂度为O(n)，而AVL树能保证查找操作的时间复杂度总为O(logn)，如果在检索时这样的效率是有很大的改进的，所以基于此类效率的数据结构会有更大的应用空间。

对于一棵BST树而言，不仅有查找操作，也有插入、删除等改变树的形态的操作。随着不断地插入、删除，BST树有可能会退化成链表的形式（在二叉树基础中的斜二叉树就是极端情况的BST），使得查找的时间复杂度变成O(N)，这种情形下，BST树的结构非常不平衡了。为了保持树的平衡，需要对树的形态做一些限制，因此，引入了AVL树，以保证树的左右子树高度之差的绝对值小于等于1。

AVL通过什么样的操作才可以保持较高的效率？

旋转

何种情况下该如何旋转？

插入、删除

旋转的四种类型，解决所有问题

在旋转是要注意旋转节点和其子节点的左右重新连接。
　　2.1、左左旋转（LL型）
如图，造成A节点的高度差>1的节点为子树为左子节点和左子节点的左子节点，则为LL型，LL型为顺时针旋转。
　　　　如图2-1所示，此时A节点的左树与右树的高度差为2，与AVL的定义不符，此时以B节点为轴心，AB间连线为转轴，将A节点旋转至B节点下方，由B节点的父节点变成子节点。实现所有节点的左右子树高度差小于等于1。如图2-2。

2.2、右右旋转
如图，造成A节点的高度差>1的节点为子树为右子节点和右子节点的右子节点，则为RR型，RR型为逆时针旋转。
　　　　右右旋转与左左旋转类似，但是动作相反，如图2-3，2-4所示，以B节点为轴心，BC间连线为轴，将C节点旋转至B下方，成为B的子节点。实现所有节点的左右子树高度差小于等于1。

2.3、左右旋转
如图，造成A节点的高度差>1的节点为子树为右子节点和右子节点的右子节点，则LR型，LR型为先逆时针旋转，后顺时针旋转。
　　　　　　左右旋转稍复杂一点，需要旋转两次，如果用左左旋转的方式直接旋转图2-5中的树，会变成图2-8的样子，此时B节点的左右子树高度差依然没有平衡，所以要先对2-5的树做一步处理，就是以BC为轴，

将C节点旋转至B节点的位置，如图2-6所示，此时就将树转换成了左左旋转的场景，之后使用左左旋转即可完成平衡。

2.4、右左旋转

右左旋转与左右旋转类似，也是旋转两次，先顺时针旋转，后逆时针旋转。

旋转的代码是啥？

mport java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

public class AVLTree {

    //根节点
    private Node root;
    
    /**
     * 添加节点
     * @param item
     */
    public void add(int item){
        if(root == null)
            root = new Node(item);
        else{
            Node parent = root;
            Node temp = root;
            do{
                parent = temp;
                if(item < parent.getValue()){
                    temp = parent.getLeft();
                }else if(item > parent.getValue()){
                    temp = parent.getRight();
                }else{
                    break;
                }
            }while(temp != null);
            if(temp != null){
                temp.setValue(item);
            }else{
                Node node = new Node(item);
                node.setParent(parent);
                if(item < parent.getValue()){
                    parent.setLeft(node);
                    if(parent.getRight() == null)
                        balance(node);
                    else
                        parent.subAVL();
                }else{
                    parent.setRight(node);
                    if(parent.getLeft() == null)
                        balance(node);
                    else
                        parent.addAVL();
                }
            }
        }
    }
    
    /**
     * 增加节点时修改节点平衡值，对不平衡的子树进行调整
     * 依次向上遍历，修改父节点的平衡因子，直到出现最小不平衡节点
     * @param node
     */
    private void balance(Node node){
        Node parent = node.getParent();
        Node node_middle = node;
        Node node_prev = node;
        
        Boolean avl = true;
        do{
            if(node_middle == parent.getLeft() && (-1 <= parent.getAVL()-1 && parent.getAVL()-1 <= 1)){
                parent.subAVL();
                node_prev = node_middle;
                node_middle = parent;
                if(parent != null && parent.getAVL() == 0)
                    parent = null;
                else
                    parent = parent.getParent();
            }else if(node_middle == parent.getRight() && (-1 <= parent.getAVL()+1 && parent.getAVL()+1 <= 1)){
                parent.addAVL();
                node_prev = node_middle;
                node_middle = parent;
                if(parent != null && parent.getAVL() == 0)
                    parent = null;
                else
                    parent = parent.getParent();
            }else{//出现最小不平衡节点，新增时不需要考虑更高节点，所以直接中断循环，调用平衡方法
                avl = false;
            }
        }while(parent != null && avl);
        
        if(parent == null){
            return;
        }
        chooseCalculation(parent, node_middle, node_prev);
    }
    
    /**
     * 选择合适的转换规则，返回变更的高度值（删除平衡时会用到）。
     * @param parent
     * @param node_middle
     * @param node_prev
     */
    private int chooseCalculation(Node parent, Node node_middle, Node node_prev) {
        
        //变更的高度值
        int height = 0;
        
        if(node_middle == parent.getLeft() && node_prev == node_middle.getLeft()){
            if(node_middle.getAVL() == -1)
                height = -1;
            LeftLeftRotate(node_middle);
        }else if(node_middle == parent.getLeft() && node_prev == node_middle.getRight()){
            height = -1;
            LeftRightRotate(node_middle);
        }else if(node_middle == parent.getRight() && node_prev == node_middle.getLeft()){
            height = -1;
            RightLeftRotate(node_middle);
        }else if(node_middle == parent.getRight() && node_prev == node_middle.getRight()){
            if(node_middle.getAVL() == 1)
                height = -1;
            RightRightRotate(node_middle);
        }
        
        return height;
    }
    
    /**
     * 查询节点
     * @param item
     * @return
     */
    public Node get(int item){
        if(root == null)
            return null;
        if(item == root.getValue()){
            return root;
        }else{
            Node node = root;
            do{
                if(item < node.getValue()){
                    node = node.getLeft();
                }else if(item > node.getValue()){
                    node = node.getRight();
                }else{
                    return node;
                }
            }while(node != null);
        }
        return null;
    }
    
    /**
     * 获取树的高度
     * @return
     */
    public int treeLength(){
        return getLength(root);
    }
    
    /**
     * 获取node到树底的高度
     * @param node
     * @return
     */
    private int getLength(Node node){
        if(node == null)
            return 0;
        int num = 1;
        List<Node> l = new ArrayList<Node>();
        l.add(node);
        num = itrableNode(num, l);
        return num;
    }
    
    private int itrableNode(int num, List<Node> list){
        List<Node> newlist = new ArrayList<Node>();
        list.forEach(new Consumer<Node>() {
            @Override
            public void accept(Node t) {
                if(t.getLeft() != null){
                    newlist.add(t.getLeft());
                }
                if(t.getRight() != null){
                    newlist.add(t.getRight());
                }
            }
        });
        if(newlist.size() > 0){
            num += 1;
            num = itrableNode(num,newlist);
        }
        return num;
    }
    
    /**
     * 打印树形图(仅限10到99的正整数组成的树，否则排版会有问题)，测试用方法
     */
    public void printByPhoto(){
        
        if(root == null){
            return;
        }
        int length = treeLength();
        int blank = countoutBlank(length, 1);
        List<Node> l = new ArrayList<Node>();
        l.add(root);
        printRow(length,blank,1,l);
    }
    
    /**
     * 计算每行的空格数
     * @param length
     * @param row
     * @return
     */
    private int countoutBlank(int length, int row){
        int half = (int)Math.pow(2, length-1-row);
        int blank = 0;
        if(length == 2){
            blank = 2;
        }else if(length > 2){
            if(half == 2){
                blank = 6;
            }else{
                blank = (int) (Math.pow(2, length-2-row) * 6 + (Math.pow(2, length - 2-row) - 1) * 2);
            }
        }else{
            blank = 0;
        }
        return blank;
    }
    
    /**
     * 绘制行
     * @param length
     * @param blank
     * @param row
     * @param list
     */
    private void printRow(int length, int blank, int row, List<Node> list){
        
        for(int n = 0; n < blank; n++){
            System.out.print(" ");
        }
        
        StringBuffer x = new StringBuffer();
        for(int n = 0; n < blank*2; n++){
            x.append(" ");
        }
        x.append("  ");
        StringBuffer y = new StringBuffer();
        for(int n = 0; n < blank*2; n++){
            y.append(" ");
        }
        y.append("  ");
        
        List<Node> newlist = new ArrayList<Node>();
        if(row == 1){
            System.out.print(root.getValue());
            System.out.println("");
            printRow(length,countoutBlank(length, row+1),row+1,list);
        }else{
            for(Node t : list){
                if(t.getLeft() != null){
                    newlist.add(t.getLeft());
                    System.out.print(t.getLeft().getValue()+x.toString());
                }else if(t.getValue() != 0 || row <= length){
                    newlist.add(new Node(0));
                    System.out.print("x "+x.toString());
                }
                if(t.getRight() != null){
                    newlist.add(t.getRight());
                    System.out.print(t.getRight().getValue()+y.toString());
                }else if(t.getValue() != 0 || row <= length){
                    newlist.add(new Node(0));
                    System.out.print("x "+y.toString());
                }
            }
            System.out.println("");
            if(newlist.size() > 0)
                printRow(length,countoutBlank(length, row+1),row+1,newlist);
        }
    }
    
    /**
     * 左左旋转
     * @param node
     */
    private void LeftLeftRotate(Node node){
        
        Node parent = node.getParent();
        
        if(parent.getParent() != null && parent == parent.getParent().getLeft()){
            node.setParent(parent.getParent());
            parent.getParent().setLeft(node);
        }else if(parent.getParent() != null && parent == parent.getParent().getRight()){
            node.setParent(parent.getParent());
            parent.getParent().setRight(node);
        }else{
            root = node;
            node.setParent(null);
        }
        parent.setParent(node);
        parent.setLeft(node.getRight());
        if(node.getRight() != null)
            node.getRight().setParent(parent);
        node.setRight(parent);
        
        if(node.getAVL() == -1){//只有左节点时，parent转换后没有子节点
            parent.setAVL(0);
            node.setAVL(0);
        }else if(node.getAVL() == 0){//node有两个子节点，转换后parent有一个左节点
            parent.setAVL(-1);
            node.setAVL(1);
        }//node.getAVL()为1时会调用左右旋转
    }
    
    /**
     * 右右旋转
     * @param node
     */
    private void RightRightRotate(Node node){
        
        Node parent = node.getParent();
        
        if(parent.getParent() != null && parent == parent.getParent().getLeft()){
            node.setParent(parent.getParent());
            parent.getParent().setLeft(node);
        }else if(parent.getParent() != null && parent == parent.getParent().getRight()){
            node.setParent(parent.getParent());
            parent.getParent().setRight(node);
        }else{
            root = node;
            node.setParent(null);
        }
        parent.setParent(node);
        parent.setRight(node.getLeft());
        if(node.getLeft() != null)
            node.getLeft().setParent(parent);
        node.setLeft(parent);
        
        if(node.getAVL() == 1){
            node.setAVL(0);
            parent.setAVL(0);
        }else if(node.getAVL() == 0){//当node有两个节点时，转换后层数不会更改，左树比右树高1层，parent的右树比左树高一层
            parent.setAVL(1);
            node.setAVL(-1);
        }
    }
    
    /**
     * 左右旋转
     * @param node
     */
    private void LeftRightRotate(Node node){
        
        Node parent = node.getParent();
        Node child = node.getRight();
        
        //左右旋转时node的avl必为1，所以只需考虑child的avl
        if(!child.hasChild()){
            node.setAVL(0);
            parent.setAVL(0);
        }else if(child.getAVL() == -1){
            node.setAVL(0);
            parent.setAVL(1);
        }else if(child.getAVL() == 1){
            node.setAVL(-1);
            parent.setAVL(0);
        }else if(child.getAVL() == 0){
            node.setAVL(0);
            parent.setAVL(0);
        }
        child.setAVL(0);
        
        //第一次交换
        parent.setLeft(child);
        node.setParent(child);
        node.setRight(child.getLeft());
        if(child.getLeft() != null)
            child.getLeft().setParent(node);
        child.setLeft(node);
        child.setParent(parent);
        
        //第二次交换
        if(parent.getParent() != null && parent == parent.getParent().getLeft()){
            child.setParent(parent.getParent());
            parent.getParent().setLeft(child);
        }else if(parent.getParent() != null && parent == parent.getParent().getRight()){
            child.setParent(parent.getParent());
            parent.getParent().setRight(child);
        }else{
            root = child;
            child.setParent(null);
        }
        parent.setParent(child);
        parent.setLeft(child.getRight());
        if(child.getRight() != null)
            child.getRight().setParent(parent);
        child.setRight(parent);
        
        
    }
    
    /**
     * 右左旋转
     * @param node
     */
    private void RightLeftRotate(Node node){
        
        Node parent = node.getParent();
        Node child = node.getLeft();
        
        if(!child.hasChild()){
            node.setAVL(0);
            parent.setAVL(0);
        }else if(child.getAVL() == -1){
            node.setAVL(1);
            parent.setAVL(0);
        }else if(child.getAVL() == 1){
            node.setAVL(0);
            parent.setAVL(-1);
        }else if(child.getAVL() == 0){
            parent.setAVL(0);
            node.setAVL(0);
        }
        child.setAVL(0);
        
        //第一次交换
        parent.setRight(child);
        node.setParent(child);
        node.setLeft(child.getRight()); 
        if(child.getRight() != null)
            child.getRight().setParent(node);
        child.setRight(node);
        child.setParent(parent);
        
        //第二次交换
        if(parent.getParent() != null && parent == parent.getParent().getLeft()){
            child.setParent(parent.getParent());
            parent.getParent().setLeft(child);
        }else if(parent.getParent() != null && parent == parent.getParent().getRight()){
            child.setParent(parent.getParent());
            parent.getParent().setRight(child);
        }else{
            root = child;
            child.setParent(null);
        }
        parent.setParent(child);
        parent.setRight(child.getLeft());
        if(child.getLeft() != null)
            child.getLeft().setParent(parent);
        child.setLeft(parent);
        
    }
    
    /**
     * 删除节点
     * @param item
     */
    public void deleteNode(int item){

        Node node = get(item);
        if(node == null)
            return;
        Node parent = node.getParent();
        if(!node.hasChild()){//叶子节点
            if(parent == null){//删除最后节点
                root = null;
                return;
            }
            if(node.hasBrother()){//node有兄弟节点时，需要判断是否需要调用平衡方法
                if(node == parent.getLeft())
                    isBalance(node, 1);
                else
                    isBalance(node, -1);
                parent.deleteChildNode(node);
            }else{//node没有兄弟节点时，高度减一，需要进行平衡
                deleteAvl(node);
                parent.deleteChildNode(node);
            }
        }else if(node.getLeft() != null && node.getRight() == null){//有一个子节点时，将子节点上移一位，然后进行平衡即可
            if(parent == null){//删除的是跟节点
                root = node;
                return;
            }
            if(node == parent.getLeft()){
                parent.setLeft(node.getLeft());
            }else{
                parent.setRight(node.getLeft());
            }
            node.getLeft().setParent(parent);
            deleteAvl(node.getLeft());
        }else if(node.getLeft() == null && node.getRight() != null){//有一个子节点时，将子节点上移一位，然后进行平衡即可
            if(parent == null){//删除的是跟节点
                root = node;
                return;
            }
            if(node == parent.getRight()){
                parent.setRight(node.getRight());
            }else{
                parent.setLeft(node.getRight());
            }
            node.getRight().setParent(parent);
            deleteAvl(node.getRight());
        }
        else{//有两个子节点时，先在节点左树寻找最大节点last，然后删除last，最后将被删除节点的value替换为last的value
            Node last = findLastNode(node);
            int tmp = last.getValue();
            deleteNode(last.getValue());
            node.setValue(tmp);
        }
        node = null;//GC
    }
    
    /**
     * 判断是否需要平衡
     * @param node
     * @param avl
     */
    private void isBalance(Node node, int avl){
        
        Node parent = node.getParent();
        if(avl == 1){
            if(parent.getAVL() + 1 > 1){
                deleteAvl(node);
            }else{
                parent.addAVL();
            }
        }else if(avl == -1){
            if(parent.getAVL() - 1 < -1){
                deleteAvl(node);
            }else{
                parent.subAVL();
            }
        }
    }

    /**
     * 搜索node节点左树的最大节点，用于替换被删除节点
     * @param n
     * @return
     */
    private Node findLastNode(Node n){
        
        Node last = null;
        Node node = n.getLeft();
        if(node != null){
            do{
                last = node;
                node = node.getRight();
            }while(node != null);
        }
        return last;
    }
    
    /**
     * 删除时平衡上级节点
     * @param node
     */
    private void deleteAvl(Node node){
        
        Node node_middle = node;
        Node parent = node_middle.getParent();
        Node node_prev = node_middle;
        boolean avl = true;
        
        do{
            node_prev = node_middle;
            if(node_middle == parent.getLeft() && (parent.getAVL() + 1 <= 1)){
                if(parent.getAVL() == 0){
                    parent.addAVL(); 
                    return;
                }
                parent.addAVL();
                node_middle = parent;
                parent = node_middle.getParent();
            }else if(node_middle == parent.getRight() && (parent.getAVL() - 1 >= -1)){
                if(parent.getAVL() == 0){
                    parent.subAVL();
                    return;
                }
                parent.subAVL();
                node_middle = parent;
                parent = node_middle.getParent();
            }else{
                //由于删除时有可能进行多次平衡，所以不直接使用node_middle的值，防止影响之后的循环
                Node middle = node_middle.getBrother();
                Node child = middle.getAVL() == -1 ? middle.getLeft() : (middle.getAVL() == 1 ? middle.getRight() : (parent.getAVL() == -1 ? middle.getLeft() : middle.getRight()));
                int height = chooseCalculation(parent, middle, child);
                if(height == 0)
                    return;
                node_middle = parent.getParent();
                parent = node_middle.getParent();
            }
        }while(parent != null && avl);
    }
}

辅助代码

public class Node {

    private Node parent;
    private Node left;
    private Node right;
    private int item;
    private int avl;
    
    public Node(int item) {
        this.item = item;
        this.avl = 0;
    }
    
    public int getValue(){
        return item;
    }
    
    public Node getLeft(){
        return left;
    }
    
    public Node getRight(){
        return right;
    }
    
    public Node getParent(){
        return parent;
    }
    
    public void setValue(int item){
        this.item = item;
    }
    
    public void setParent(Node parent){
        this.parent = parent;
    }
    
    public void setLeft(Node item){
        this.left = item;
    }
    
    public void setRight(Node item){
        this.right = item;
    }
    
    public int getAVL(){
        return avl;
    }
    
    public void setAVL(int avl){
        this.avl = avl;
    }
    
    public int subAVL(){
        avl -= 1;
        return avl;
    }
    
    public int addAVL(){
        avl += 1;
        return avl;
    }
    
    @Override
    public String toString() {
        return String.valueOf(item);
    }
    
    public boolean hasBrother(){
        if(parent == null)
            return false;
        else if(this == parent.getLeft() && parent.getRight() != null)
            return true;
        else if(this == parent.getRight() && parent.getLeft() != null)
            return true;
        else
            return false;
    }
    
    public boolean hasChild(){
        if(left != null || right != null)
            return true;
        else 
            return false;
    }
    
    public Node getBrother(){
        if(parent == null)
            return null;
        else if(this == parent.getLeft())
            return parent.getRight();
        else
            return parent.getLeft();
    }
    
    public void deleteChildNode(Node child){
        if(child == null)
            return;
        else if(child == left)
            left = null;
        else if(child == right)
            right = null;
    }
}