1、基本概念

平衡因子：某个节点的左右子树的高度差
AVL数的特点：
1、每个节点的平衡因子只可能是1、0、-1（绝对值1，如果超过1，称为“失衡”）
2、每个节点的左右子树高度差不超过1
3、搜索添加删除的时间复杂度为O(logn)

平衡二叉树

2、二叉树失衡

往上面二叉树中添加13，会导致二叉树失衡
最坏的情况会导致所有祖先节点失衡。
父节点、非祖先节点，都不可能失衡

3、调整为平衡二叉树的方法

3.1、LL-右旋转（单旋）

右旋

如上图所示通过旋转节点g，将树调整为右侧的二叉树，让p成为二叉树的根节点

3.2、RR-左旋转（单旋）

左旋

如上图所示通过旋转节点g，将树调整为右侧的二叉树，让p成为二叉树的根节点

3.3、LR-RR左旋转，LL右旋转（双旋）

左旋、右旋

如上图所示通过旋转节点p，将n调整为p的左子树（如图中间位置）。在通过旋转g节点，让g成为n的右子树，最终得到平衡二叉树

3.4、RL-LL右旋转，RR左旋转（双旋）

右旋-左旋

如上图所示通过旋转节点p，将n调整为p的右子树（如图中间位置）。在通过步骤2将g成为n的左子树，最终得到平衡二叉树

3.5、统一旋转操作

4、关键代码实现

4.1、分别对每种旋转处理

// 添加每个节点后，调整二叉树的平衡
protected void afterAdd(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            } else {
                // 恢复平衡
                rebalance(node);
                // 整颗树恢复平衡
                break;
            }
        }
}
// 恢复平衡，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);
            }
        }
}

// 平衡因子 <= 1
private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
}

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 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 afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()){
            grand.parent.right = parent;
        } else { // grand是root点
            root = parent;
        }
        // 更新child的parent
        if (child != null) {
            child.parent = grand;
        }
        // 更新grand的parent
        grand.parent = parent;
        // 更新高度
        updateHeight(grand);
        updateHeight(parent);
}
private void  updateHeight(Node<E> node) {
        ((AVLNode<E>) node).updateHeight();
}

4.2、统一操作实现

// 删除子节点后重新调整二叉树的平衡
protected void afterRemove(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            } else {
                rebalance2(node);
            }
        }
}
// grand 高度最低的不平衡点
private void rebalance2(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node =  ((AVLNode<E>)parent).tallerChild();
        if (parent.isLeftChild()) {
            if (node.isLeftChild()) { // LL
                rotate(grand, node.left, node, node.right, parent, parent.right,grand, grand.right);
            } else { // LR
                rotate(grand, parent.left, parent, node.left, node, node.right,grand, grand.right);
            }
        } else {
            if (node.isLeftChild()) { // RL
                rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
            } else { // RR
                rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
            }
        }
}

// rotate2
private void rotate(Node<E> r,
                        Node<E> a, Node<E> b, Node<E> c,
                        Node<E> d,
                        Node<E> e, Node<E> f, Node<E> g) {
        // 让d 成为这颗子树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }
        // a-b-c
        b.left = a;
        if (a != null) {
            a.parent = b;
        }
        b.right = c;
        if (c != null) {
            c.parent = b;
        }
        updateHeight(b);
        // e-f-g
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        f.right = g;
        if (g != null) {
            g.parent = f;
        }
        updateHeight(f);
        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
}