一、核心定义

• 本质：二叉搜索树（BST）的优化版本，通过限制左右子树的高度差（平衡因子），避免树退化为链表，保障查询、插入、删除操作的时间复杂度稳定在 O(log n)。
• 平衡因子（BF）：节点左子树高度 - 右子树高度（部分实现为绝对值），平衡二叉树要求所有节点的平衡因子满足 |BF| ≤ 1。
• 常见类型：AVL树（严格平衡）、红黑树（近似平衡，工业界常用）、Splay树（自调整平衡）。
• 资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

二、核心特性（以AVL树为例）

1. 继承BST特性：左子树所有节点值 < 根节点值，右子树所有节点值 > 根节点值，中序遍历为有序序列。
2. 平衡约束：任意节点的左右子树高度差不超过1。
3. 动态调整：插入/删除后若平衡被破坏，通过「旋转操作」恢复平衡。

三、平衡破坏与修复（旋转操作）

1. 失衡场景（4种核心情况）

2. 旋转修复方法（可执行步骤）

（1）LL失衡：右旋转

# 示例：根节点为A，左子树为B，B的左子树为C
1. 将B的右子树设为A的左子树（若B有右子树）；
2. 将A设为B的右子树；
3. 更新A和B的高度（从下往上更新）；
4. 将B设为新的根节点。

（2）RR失衡：左旋转

# 示例：根节点为A，右子树为B，B的右子树为C
1. 将B的左子树设为A的右子树（若B有左子树）；
2. 将A设为B的左子树；
3. 更新A和B的高度；
4. 将B设为新的根节点。

（3）LR失衡：先左旋转再右旋转

1. 对根节点的左子树（B）执行左旋转，将LR转化为LL；
2. 对根节点（A）执行右旋转，恢复平衡。

（4）RL失衡：先右旋转再左旋转

1. 对根节点的右子树（B）执行右旋转，将RL转化为RR；
2. 对根节点（A）执行左旋转，恢复平衡。

四、核心操作时间复杂度

五、AVL树 vs 红黑树（面试高频对比）

六、代码实现示例（Java：AVL树核心逻辑）

class AVLNode {
    int val;
    int height; // 节点高度（默认1）
    AVLNode left, right;

    public AVLNode(int val) {
        this.val = val;
        this.height = 1;
    }
}

class AVLTree {
    private AVLNode root;

    // 获取节点高度
    private int getHeight(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    // 计算平衡因子
    private int getBalance(AVLNode node) {
        return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
    }

    // 更新节点高度
    private void updateHeight(AVLNode node) {
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    }

    // 右旋转
    private AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;

        // 执行旋转
        x.right = y;
        y.left = T2;

        // 更新高度
        updateHeight(y);
        updateHeight(x);

        return x;
    }

    // 左旋转
    private AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;

        // 执行旋转
        y.left = x;
        x.right = T2;

        // 更新高度
        updateHeight(x);
        updateHeight(y);

        return y;
    }

    // 插入节点（递归实现）
    public AVLNode insert(AVLNode node, int val) {
        // 1. 执行BST插入
        if (node == null) return new AVLNode(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        else return node; // 不允许重复值

        // 2. 更新高度
        updateHeight(node);

        // 3. 计算平衡因子，判断是否失衡
        int balance = getBalance(node);

        // 4. 处理4种失衡情况
        // LL
        if (balance > 1 && val < node.left.val)
            return rightRotate(node);
        // RR
        if (balance < -1 && val > node.right.val)
            return leftRotate(node);
        // LR
        if (balance > 1 && val > node.left.val) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // RL
        if (balance < -1 && val < node.right.val) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node; // 未失衡，返回原节点
    }

    // 中序遍历（验证有序性）
    public void inorder(AVLNode node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.val + " ");
            inorder(node.right);
        }
    }
}