AVL树插入异常求助：rotationRightLeft函数平衡因子计算错误排查

问题概述 #

怀疑rotationRightLeft函数的平衡因子计算错误，插入测试中rotationLeftRight工作正常，但rotationRightLeft存在问题。以下是代码分析与修正方案：

核心错误点 #

1. 插入右子树时的平衡因子更新错误 #

在insert函数的右子树插入分支中，错误地将节点平衡因子加1，而实际上插入右子树会导致右子树高度增加，平衡因子（左子树高度 - 右子树高度）应该减1。

错误代码片段：

else if(e > node->content){
    if(insert(node->right, e)){
        node->balance++; // 此处错误，应为node->balance--;
        // ...后续判断
    }
    return false;
}

修正后：

else if(e > node->content){
    if(insert(node->right, e)){
        node->balance--; // 修正为减1
        // ...后续判断保持不变
    }
    return false;
}

2. rotationRightLeft函数的平衡因子计算错误 #

原计算逻辑完全不符合AVL树旋转后的平衡因子推导，正确的计算应基于旋转前后的高度差变化。结合你rotationLeftRight的对称逻辑，rotationRightLeft的平衡因子计算应做镜像修正：

错误代码片段：

int eap = - (eb < 0 ? eb : 0) - 1 + ea;
int ebp = eb + (eap > 0 ? eap : 0) - 1;

修正后（标准推导版）：

// 用自定义逻辑替代max函数，max(a,b)等价于a > b ? a : b
int max_ea_0 = ea > 0 ? ea : 0;
int eap = eb + max_ea_0 - 1;
int max_eap_0 = eap > 0 ? eap : 0;
int ebp = eb + ea - max_eap_0;

修正后的完整rotationRightLeft函数 #

template <class T>
void ArbreAVL<T>::rotationRightLeft(Node*& rootChildTree) {
    Node* a = rootChildTree->right;
    Node* b = rootChildTree;
    int ea = a->balance;
    int eb = b->balance;
    
    // 修正后的平衡因子计算
    int max_ea_0 = ea > 0 ? ea : 0;
    int eap = eb + max_ea_0 - 1;
    int max_eap_0 = eap > 0 ? eap : 0;
    int ebp = eb + ea - max_eap_0;
    
    a->balance = eap;
    b->balance = ebp;
    b->right = a->left;
    a->left = b;
    rootChildTree = a;
}

测试验证 #

修正上述两个错误后，重新运行你的测试代码，AVL树的平衡因子将正确更新，插入操作后树的结构会保持AVL平衡特性，size()校验也会正常通过。

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