AVL树插入元素3时触发段错误，请求排查代码问题

插入元素3时触发段错误，核心原因是旋转操作逻辑错误导致二叉树结构断裂，出现野指针访问。以下是具体问题和修复方案：

1. 旋转函数的致命缺陷 #

RR旋转（rr_rotation）的问题 #

原函数仅处理了root节点的情况，非root节点时存在多处错误：

• 仅修改形参tree的值（形参传递不影响外部变量），未更新tree父节点的左/右指针指向新根节点t
• 未处理t的右子树归属，破坏了原树的结构关联
• 未维护节点的parent指针，后续遍历或平衡检查时会访问野指针

LL旋转（ll_rotation）的问题 #

与RR旋转错误一致：

• 非root节点时未更新父节点的指针指向
• 未处理t的左子树挂载逻辑
• 未同步更新parent指针的关联关系

2. 修复后的旋转函数 #

修正RR旋转 #

void AVL::rr_rotation(avl *tree){
    cout<<"RR rotation"<<endl;
    avl* t = tree->left;
    avl* t_right = t->right; // 保存t的右子树，避免丢失

    // 调整tree与t的节点关系
    t->right = tree;
    tree->left = t_right;

    // 更新parent指针关联
    t->parent = tree->parent;
    tree->parent = t;
    if(t_right != nullptr){
        t_right->parent = tree;
    }

    // 更新父节点的指向，确保树结构完整
    if(t->parent == nullptr){
        root = t; // tree原本是根节点
    } else {
        if(t->parent->left == tree){
            t->parent->left = t;
        } else {
            t->parent->right = t;
        }
    }
}

修正LL旋转 #

void AVL::ll_rotation(avl *tree, int l=0){
    cout<<"LL rotation"<<endl;
    avl* t = tree->right;
    avl* t_left = t->left; // 保存t的左子树，避免丢失

    // 调整tree与t的节点关系
    t->left = tree;
    tree->right = t_left;

    // 更新parent指针关联
    t->parent = tree->parent;
    tree->parent = t;
    if(t_left != nullptr){
        t_left->parent = tree;
    }

    // 更新父节点的指向，确保树结构完整
    if(t->parent == nullptr){
        root = t; // tree原本是根节点
    } else {
        if(t->parent->left == tree){
            t->parent->left = t;
        } else {
            t->parent->right = t;
        }
    }
}

3. 其他潜在优化点 #

• check_avl函数的旋转类型判断逻辑不准确：当前仅通过子节点的子树是否存在判断旋转类型，正确逻辑应结合插入节点的方向或子节点的平衡因子判断
• C代码中建议使用new替代malloc分配内存，更符合C语言规范（malloc不会调用构造函数，虽结构体场景影响小，但更严谨）

修复后，插入3时RR旋转会正确调整树结构，不会出现野指针访问，程序可正常执行后续插入和遍历操作。

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