插入节点7后AVL树平衡失败，如何修正平衡算法？

你的AVL树平衡逻辑核心错误在于旋转目标节点错误和RL型旋转顺序颠倒，导致插入节点7后无法生成正确的平衡结构。

具体问题点 #

1. 旋转目标节点错误：AVL树的平衡调整是针对当前失衡节点操作，而非它的孙子节点。你之前的代码错误地选择了子节点的子节点作为旋转对象，完全偏离了AVL树的平衡规则。
2. RL型旋转顺序颠倒：右重且右子树左重的场景（RL型），正确顺序是先右旋右子节点，再左旋当前失衡节点，你之前的操作顺序完全搞反了。

修正后的平衡逻辑代码 #

private void balance(Node node) {
    if (node == null)
        return;

    int balanceFactor = balanceFactor(node);
    if (balanceFactor > 1) {
        // 左子树过重
        int leftBalance = balanceFactor(node.left);
        if (leftBalance > 0) {
            // LL型：对当前节点执行右旋转
            rightRotate(node);
        } else {
            // LR型：先左旋左子节点，再右旋当前节点
            leftRotate(node.left);
            rightRotate(node);
        }
    } else if (balanceFactor < -1) {
        // 右子树过重
        int rightBalance = balanceFactor(node.right);
        if (rightBalance < 0) {
            // RR型：对当前节点执行左旋转
            leftRotate(node);
        } else {
            // RL型：先右旋右子节点，再左旋当前节点
            rightRotate(node.right);
            leftRotate(node);
        }
    }

    balance(node.parent);
}

针对插入7后的场景说明 #

插入7后，真正失衡的节点是根节点3（平衡因子为-2，右子树过重），它的右子节点8的平衡因子为1（左子树过重），属于RL型失衡：

1. 先对节点8执行右旋，将8的左子树5提升为8的父节点，此时节点3的右子节点变为5
2. 再对节点3执行左旋，将5提升为新的根节点
3. 最终就能生成你期望的目标平衡结构

内容的提问来源于stack exchange，提问作者Cardinal System