AVL树平衡旋转操作触发Segmentation Fault问题求助

核心错误点分析 #

你的代码触发段错误的原因集中在三个关键问题：

1. 新节点未初始化height字段 #

NODE_CREATE函数中没有设置new->height = 1，新节点的height是内存中的随机垃圾值，导致后续高度计算、平衡因子判断完全错误，这是触发崩溃的根源之一。

2. 基础旋转函数逻辑完全颠倒 #

• 左旋转（ROTATE_L）：原本用于处理RR型失衡，需要将当前节点的右孩子作为新根，但你的代码错误地取了当前节点的左孩子，导致指针访问越界。
• 右旋转（ROTATE_R）：原本用于处理LL型失衡，需要将当前节点的左孩子作为新根，但你的代码错误地取了当前节点的右孩子，逻辑完全反转。

3. 复合旋转依赖错误的基础旋转 #

由于基础旋转函数逻辑错误，ROTATE_LR和ROTATE_RL的复合旋转操作自然无法正确执行，进一步加剧了指针访问错误。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>

// 定义AVL树节点结构
typedef struct node
{
    struct node * left;
    int data;
    struct node * right;
    int height;
}node;

typedef node * BST;

// 函数声明
void BST_INSERT(BST *tree,int data);
void BST_DESTROY(BST *tree);
BST NODE_CREATE(int data);
// AVL旋转操作
BST ROTATE_L(BST C);
BST ROTATE_R(BST C);
BST ROTATE_LR(BST C);
BST ROTATE_RL(BST C);
int max(int a,int b);
int height(BST C);

// 主函数
int main(void)
{
    BST t = NULL;
    // 触发段错误的测试用例
    BST_INSERT(&t,10);
    BST_INSERT(&t,15);
    BST_INSERT(&t,20);
    BST_INSERT(&t,25);
    BST_INSERT(&t,0);
    BST_INSERT(&t,-5);
    BST_INSERT(&t,-10);
    BST_INSERT(&t,-15);
    
    // 无错误的测试用例
    /*
    BST_INSERT(&t,10);
    BST_INSERT(&t,5);
    BST_INSERT(&t,15);
    BST_INSERT(&t,3);
    BST_INSERT(&t,6);
    BST_INSERT(&t,14);
    BST_INSERT(&t,16);
    */

    // 销毁树（可选）
    BST_DESTROY(&t);
    return 0;
}

// 创建新节点
BST NODE_CREATE(int data)
{
    BST new = (BST)malloc(sizeof(node));
    if(!new)
    {
        fprintf(stderr,"error allocating memory\n");
        return NULL;
    }
    new->data = data;
    new->right = NULL;
    new->left = NULL;
    new->height = 1; // 初始化高度为1
    return new;
}

// AVL树插入操作
void BST_INSERT(BST *tree,int data)
{
    if(*tree == NULL)
    {
        *tree = NODE_CREATE(data);
        return;
    }
    else if(data <= (*tree)->data)
    {
        BST_INSERT(&(*tree)->left,data);
    }
    else
    {
        BST_INSERT(&(*tree)->right,data);
    }

    // 更新当前节点高度
    (*tree)->height = max(height((*tree)->left), height((*tree)->right)) + 1;

    // 计算平衡因子
    int balance = height((*tree)->left) - height((*tree)->right);

    // LL型失衡：右旋转
    if (balance > 1 && data <= (*tree)->left->data) {
        *tree = ROTATE_R(*tree);
    }
    // LR型失衡：先左旋转左子树，再右旋转根
    else if (balance > 1 && data > (*tree)->left->data) {
        *tree = ROTATE_LR(*tree);
    }
    // RR型失衡：左旋转
    else if (balance < -1 && data > (*tree)->right->data) {
        *tree = ROTATE_L(*tree);
    }
    // RL型失衡：先右旋转右子树，再左旋转根
    else if (balance < -1 && data <= (*tree)->right->data) {
        *tree = ROTATE_RL(*tree);
    }
}

// 销毁AVL树
void BST_DESTROY(BST *tree)
{
    if(*tree == NULL)
    {
        return;
    }
    BST_DESTROY(&(*tree)->left);
    BST_DESTROY(&(*tree)->right);
    printf("deleting : %i ",(*tree)->data);
    free(*tree);
    *tree = NULL; // 避免野指针
}

// 返回两个整数的最大值
int max(int a,int b)
{
    return (a > b) ? a : b;
}

// 获取节点高度
int height(BST C)
{
    if(C == NULL)
    {
        return 0;
    }
    return C->height;
}

// 左旋转：处理RR型失衡
BST ROTATE_L(BST C)
{
    BST R = C->right;
    BST RL = R->left;

    // 执行旋转
    R->left = C;
    C->right = RL;

    // 更新高度
    C->height = max(height(C->left), height(C->right)) + 1;
    R->height = max(height(R->left), height(R->right)) + 1;

    return R;
}

// 右旋转：处理LL型失衡
BST ROTATE_R(BST C)
{
    BST L = C->left;
    BST LR = L->right;

    // 执行旋转
    L->right = C;
    C->left = LR;

    // 更新高度
    C->height = max(height(C->left), height(C->right)) + 1;
    L->height = max(height(L->left), height(L->right)) + 1;

    return L;
}

// RL复合旋转
BST ROTATE_RL(BST C)
{
    C->right = ROTATE_R(C->right);
    return ROTATE_L(C);
}

// LR复合旋转
BST ROTATE_LR(BST C)
{
    C->left = ROTATE_L(C->left);
    return ROTATE_R(C);
}

修复说明 #

1. 初始化节点高度：新创建的节点高度固定为1，确保后续高度计算的准确性。
2. 修正旋转逻辑：左旋转和右旋转的指针操作完全按照AVL树的规范实现，避免了非法指针访问。
3. 完善销毁函数：添加*tree = NULL避免野指针问题。

现在你可以测试所有插入序列，包括之前触发段错误的用例，程序都能正常执行平衡操作。

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