AVL 树

二叉搜索树的复杂度分析

正常情况下，O(h) == O(logn)

但如果退化成链表（斜树）的话，复杂度就变为 O(h) == O(n)

退化成链表的情况：

• 添加节点的时候，一直都是从小到大的顺序添加，就会形成一颗斜树。
• 删除节点的时候，也有可能导致二叉搜索树退化成链表。

有没有办法防止二叉搜索树退化成链表？

让添加、删除、搜索的复杂度维持在 O(logn)。

平衡

平衡：当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡(高度越低)

父节点、非祖先节点，都不可能失衡

理想平衡

最理想的平衡，就是像完全二叉树、满二又树那样，高度是最小的。

改进方案

要达到理想平衡，也就意味着操作次数多，时间久，性能低。

所以，合理的改进方案是：用尽量少的调整次数达到适度平衡即可。

平衡二叉搜索树

英文简称为：BBST（Balanced Binary Search Tree）

经典常见的平衡二又搜索树有

1. AVL 树

   • Windows NT 内核中广泛使用

2. 红黑树

   • C++ STL (比如 map、set )
   • Java 的 TreeMap、TreeSet、HashMap、HashSet
   • Linux 的进程调度
   • Ngix 的 timer 管理

一般也称它们为：自平衡的二叉搜索树 (Self-balancing Binary Search Tree）

继承结构

AVL 树 - 基本概念

❗ 平衡因子(Balance Factor): 某结点的左右子树的高度差（左子树高度 - 右子树的高度）

AVL 树的特点：

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

添加导致的失衡

• 最坏情况：可能会导致所有祖先节点都失衡

• 父节点、非祖先节点，都不可能失衡

删除导致的失衡

• 可能会导致父节点或祖先节点失衡

• 其他节点，都不可能失衡

旋转

LL - 右旋转（单旋）

n node 节点

p parent 父节点

g grandpa 祖父节点

场景：

LL -- n 是 g 的 left.left，平衡因子为 2

具体操作：

• g.left = p.right（✔️）
• p.right = g（✔️）
• 让 p 成为这棵子树的根节点
• 仍然是一棵二叉搜索树：T0 < n < T1 < p < T2 < g < T3
• 整棵树都达到平衡

还需要注意维护的内容：

• T2、p、g 的 parent 属性（✔️）
• 先后更新 g、p 的高度 -- 先更新(旋转后)矮的，即原来的祖父节点 g（✔️）

代码主要实现以上四个内容

RR - 左旋转（单旋）

场景：

RR -- n 是 g 的 right.right，平衡因子为 -2

具体操作：

• g.right = p.left（✔️）
• p.left = g（✔️）
• 让 p 成为这棵子树的根节点
• 仍然是一棵二叉搜索树：T < g < T1 < p < T2 < n < T3

还需要注意维护的内容：

• T1、p、g 的 parent 属性（✔️）
• 先后更新 g、p 的高度（✔️）

LR,RL - 双旋

1、LR 左旋转，LL 右旋转

高处 往 低处 旋转，直到 适度平衡

2、RL 右旋转，RR 左旋转

代码实现

主要点

1. AfterAdd
2. 计算平衡因子
3. 更新高度
4. 恢复平衡
5. 旋转方向的判断
6. 左旋转的实现
7. 右旋转的实现
8. 统一旋转操作
9. afterRemove

完整代码

public class AVLTree<E> extends BST<E> {
  
    public AVLTree() {
        this(null);
    }

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

    /**
     * 新增节点
     * @param node 新添加的节点
     */
    @Override
    protected void afterAdd(Node<E> node) {
        // 从新插入的节点开始,不断向上检查其父节点,直到达到树根(parent 为 null)
        while ((node = node.parent) != null) {
            // 对每个父节点,检查它是否平衡(左右子树高度差是否超过 1)
            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);
            }
        }
    }

    /**
     * 创建一个AVL节点
     * @param element
     * @param parent
     * @return
     */
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }

    /**
     * 恢复平衡
     *
     * @param grand 高度最低的那个不平衡节点
     */
    @SuppressWarnings("unused")
    private void rebalance2(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);
            }
        }
    }

    /**
     * 恢复平衡 -- 统一旋转操作
     *
     * @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
                rotate(grand, node, node.right, parent, parent.right, grand);
            } else { // LR
                rotate(grand, parent, node.left, node, node.right, grand);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                rotate(grand, grand, node.left, node, node.right, parent);
            } else { // RR
                rotate(grand, grand, parent.left, parent, node.left, node);
            }
        }
    }

    /**
     * 旋转
     * @param r 子树的根节点
     * @param b 2
     * @param c 3
     * @param d 4 - ”中间“节点
     * @param e 5
     * @param f 6
     */
    private void rotate(
            Node<E> r,
            Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f) {
        // 让d成为这棵子树的根节点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        // b-c
        b.right = c;
        if (c != null) {
            c.parent = b;
        }
        updateHeight(b);

        // f-e
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        updateHeight(f);

        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
    }

    /**
     * 左旋
     * @param grand
     */
    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);
    }

    /**
     * 右旋
     * @param 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);
    }

    /**
     * 旋转后的操作
     * @param grand
     * @param parent
     * @param child
     */
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // 1. 更新三个节点的parent属性
        // 更新grand的parent - 让parent称为子树的根节点
        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;

        // 2. 更新父节点和祖父节点的高度属性
        updateHeight(grand);
        updateHeight(parent);
    }

    /**
     * 是否平衡
     * @param node
     * @return
     */
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }

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

    /**
     * AVL节点
     * @param <E>
     */
    private static class AVLNode<E> extends Node<E> {
        int height = 1;

        public AVLNode(E element, Node<E> 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;
        }

        /**
         * 更新AVL树节点的高度属性
         */
        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);
        }

        /**
         * 获取较高的子节点
         * @return
         */
        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;
        }

        @Override
        public String toString() {
            String parentString = "null";
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h(" + height + ")";
        }
    }
}

细节分析

1、afterAdd(Node<E> node) 中的 break 设计思路：

• 加上 break 后，代码只会持续检查和恢复从插入节点到根节点之间路径上第一个失衡节点。
• 重新平衡这个节点之后，整棵子树都会重新调整好平衡。之前已经平衡的节点不需要再次检查。（每添加一次都判断是否平衡）

这样可以避免不必要的重复工作。

2、统一所有旋转操作

不难发现，在 AVL 树的这四种失衡情况中，主要变化的一直是那四个节点：b, c, d, e, f

（在这里 a 和 g 可不做处理）

总结

添加

• 可能会导致所有祖先节点都失衡

• 只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡【仅需 O(1) 次调整】

删除

• 可能会导致父节点或祖先节点失衡（只有 1 个节点会失衡）
• 恢复平衡后，可能会导致更高层的祖先节点失衡【最多需要 O(logn) 次调整】

平均时间复杂度 - 和高度有关

• 搜索: O(logn)

• 添加: O(logn)，仅需 O(1) 次的旋转操作

• 删除: O(logn)，最多需要 O(logn) 次的旋转操作

练习题

110. 平衡二叉树 - 力扣（LeetCode） (opens new window)