09_AVL树

平衡因子：某节点的左右子树的高度差

AVL树的特点

• 每个节点的平衡因子只可能是1、0、-1（绝对值<=1，如果超过1，称之为失衡）
• 每个节点的的左右子树的高度差不超过1
• 搜索、添加、删除的时间复杂度是O(logn）

平衡对比

输入数据：35、37、34、56、25、62、57、9、74、32、94、80、75、100、16、82

• 普通二叉搜索树

  
  Snip20200904_4.png

• AVL树

  
  Snip20200904_5.png

添加

示例：往下面这棵子树中添加13

• 最坏情况：可能会导致所有祖先节点都失衡，父节点、非祖先节点都不会失衡
• 只要让高度最低的失衡点恢复平衡，整棵树就恢复平衡，仅需O(1)次调整

Snip20200904_7.png

添加的几种情况：

情况1：LL

判定条件：LL

操作：失衡（祖父）节点右旋，让父节点成为这棵树的根节点，使整棵树都达到平衡（有些教材，右旋也叫做zig，旋转之后的状态叫做zigged）

• g.left = p.right
• p.right = g
• 维护T2,p,g的parent属性

• 先后更新g、p的高度

  
  Snip20200904_8.png

情况2：RR

判定条件：RR

操作：失衡（祖父）节点左旋，让父节点成为这棵树的根节点，使整棵树都达到平衡（有些教程里面，把左旋叫做zag，旋转之后的状态叫做zagged）

• g.right = p.left
• p.left = g
• 维护T1、p、g的parent属性

• 先后更新g、p的高度

  
  Snip20200904_10.png

情况3：LR

判定条件：LR

操作：父节点左旋，祖父节点右旋

Snip20200904_12.png

情况3：RL

判定条件：RL

操作：父节点右旋，祖父节点左旋

Snip20200904_13.png

删除

示例：删除子树中的16

• 可能会导致父节点或祖先节点失衡（只有一个节点会失衡），其他节点都不可能失衡

• 如果恢复平衡之后，树的高度和之前不一样，可能会导致更高层的祖先节点失衡，需要再次恢复平衡，极端情况下，所有祖先节点都需要进行恢复平衡的操作，最多需要O(logn)次调整

Snip20200904_14.png

情况1：LL

判定条件：LL

操作：失衡节点右旋

Snip20200904_15.png

情况2：RR

判定条件：RR

操作：失衡节点左旋

Snip20200904_16.png

情况3：LR

判定条件：LR

操作：p左旋，g右旋

Snip20200904_17.png

情况4：RL

判定条件：RL

操作：p右旋，g左旋

Snip20200904_18.png

添加/删除代码(java)

package AVLTree;

import java.util.Comparator;

public class LZAVLTree<E> extends LZBST<E> {

    public LZAVLTree(){
        this(null);
    }

    public LZAVLTree(Comparator<E> comparator){
        super(comparator);
    }

    @Override
    protected void afterAdd(Node<E> node) {
        while ((node = node.parent) != null){
            if (isBalanced(node)){  //平衡
                updateHeight(node);
            }else {  //失衡
                //恢复平衡
                rebalance(node);
                //整棵树恢复平衡
                break;
            }
        }
    }

    @Override
    protected void afterRemove(Node<E> node) {
        while ((node = node.parent) != null){
            if (isBalanced(node)){
                //更新高度
                updateHeight(node);
            }else {
                //恢复平衡
                rebalance(node);
            }
        }
    }

    /**
     * 恢复平衡
     * @param grand 高度最低的那个不平衡点
     */
    private void rebalance(Node<E> grand){

        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node = ((AVLNode<E>)parent).tallerChild();

        if (parent.isLeftChild()){ //L
            if (node.isLeftChild()){ //LL
                rotateRight(grand);
            }else { //LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        }else { //R
            if (node.isLeftChild()){ //RL
                rotateRight(parent);
                rotateLeft(grand);
            }else { //RR
                rotateLeft(grand);

            }
        }
    }

    private void rotateRight(Node<E> grand){
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;

        afterRotate(grand,parent,child);

    }

    private void rotateLeft(Node<E> grand){
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;

        afterRotate(grand,parent,child);
    }

    private void afterRotate(Node<E> grand,Node<E> parent,Node<E> child){

        // 更新parent的父节点
        parent.parent = grand.parent;

        // 更新parent在父节点中的位置
        if (grand.isLeftChild()){
            grand.parent.left = parent;
        }else if(grand.isRightChild()){
            grand.parent.right = parent;
        }else {
            root = parent;
        }

        //更新child的父节点
        if (child != null){
            child.parent = grand;
        }

        //更新grand的父节点
        grand.parent = parent;

        //更新高度
        updateHeight(grand);
        updateHeight(parent);
    }

    /**
     * 更新node节点的高度
     * @param node
     * @return
     */
    private void updateHeight(Node<E> node){
        ((AVLNode<E>)node).updateHeight();
    }

    /**
     * 判断是否平衡
     * @param node
     * @return
     */
    private boolean isBalanced(Node<E> node){
        // 平衡因子的绝对值小于等于一
        return Math.abs(((AVLNode<E>)node).balanceFactor())<=1;
    }

//    @Override
//    protected Node<E> createNode(Object element, Node parent) {
//        return new AVLNode(element,parent);
//    }

    @Override
    protected Node createNode(Object element, Node parent) {
        return new AVLNode<>(element, parent);
    }

    private static class AVLNode<E> extends Node<E>{
        int height = 1;

        public AVLNode(E element,Node parent){
            super(element,parent);
        }

        /**
         * 平衡因子
         * @return
         */
        public int balanceFactor(){
            int leftHeight = left == null ? 0: ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0: ((AVLNode<E>)right).height;
            return leftHeight - rightHeight;
        }

        /**
         * 更新高度
         * @return
         */
        public void updateHeight(){
            int leftHeight = left == null ? 0: ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0: ((AVLNode<E>)right).height;
            height = 1 + Math.max(leftHeight,rightHeight);
        }

        public Node<E> tallerChild(){
            int leftHeight = left == null ? 0: ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0: ((AVLNode<E>)right).height;
            if (leftHeight>rightHeight) return left;
            if (leftHeight<rightHeight) return right;
            return isLeftChild()?left:right;
        }

    }

}

平均时间复杂度

• 搜索：O(logn)
• 添加：O(logn)，仅需O(1)次的选择操作
• 删除：O(logn)，最多需要O(logn)次的选择操作