AVL树插入出现无必要旋转，求代码错误排查与修复

问题现象 #

插入1、2、3时，前序遍历显示右旋操作执行正确；但插入4后，树本应处于平衡状态，前序遍历却显示又执行了一次右旋操作，树结构异常。

错误定位 #

1. 内存分配错误 #

创建新节点时，malloc的大小计算错误：

t = (struct node*)malloc(sizeof(struct node*));

这里用sizeof(struct node*)分配的是指针大小的内存，远小于struct node结构体的实际大小，导致节点的height等成员内存越界，高度值被随机覆盖，引发后续平衡判断错误。

2. 节点高度更新逻辑错误 #

insert函数末尾无条件执行高度更新：

t->height = max(height(t->left), height(t->right)) + 1;

• 当插入元素与当前节点值相等时，树结构未发生变化，无需更新高度，但这段代码强制更新，破坏了原有高度值。
• 旋转操作已经正确更新了相关节点的高度，末尾的统一更新会覆盖正确的高度计算结果，导致平衡因子判断错误。

修复方法 #

1. 修正内存分配大小：将malloc的参数改为sizeof(struct node)，确保分配足够内存存储完整节点。
2. 调整高度更新逻辑：
   • 仅在树结构发生变化时（创建新节点、插入左/右子树后）更新高度。
   • 移除末尾的统一高度更新，将高度更新嵌入到对应的分支中。
   • 当插入元素与当前节点值相等时，直接返回原节点，不做任何修改。

修复后的完整代码 #

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

typedef struct node *treenode;

struct node
{
    int data;
    int height;
    treenode left;
    treenode right;
};

int height(treenode t)
{
    if(t == NULL)
        return -1;
    else 
        return t->height;
}

int max(int a, int b)
{
    return (a > b)? a : b;
}

treenode singlerotatewithleft(treenode t)
{
    treenode p;
    p = t->left;
    t->left = p->right;
    p->right = t;
    t->height = max(height(t->left), height(t->right)) + 1;
    p->height = max(height(p->left), t->height) + 1;
    return p;
}

treenode singlerotatewithright(treenode t)
{
    treenode p;
    p = t->right;
    t->right = p->left;
    p->left = t;
    t->height = max(height(t->left), height(t->right)) + 1;
    p->height = max(height(p->left), t->height) + 1;
    return p;
}

treenode doublerotatewithleft(treenode t)
{
    t->left = singlerotatewithright(t->left);
    return singlerotatewithleft(t);
}

treenode doublerotatewithright(treenode t)
{
    t->right = singlerotatewithleft(t->right);
    return singlerotatewithright(t);
}

treenode insert(treenode t, int x)
{
    if(t==NULL)
    {
        t = (struct node*)malloc(sizeof(struct node));
        if(t == NULL)
        {
            printf("Out of space");
        }
        else
        {
            t->data = x;
            t->height = 0;
            t->left = t->right = NULL;
        }
        return t;
    }

    if(x < t->data)
    {
        t->left = insert(t->left,x);
        if(height(t->left) - height(t->right) == 2)
        {
            if(x < t->left->data)
                t = singlerotatewithleft(t);
            else
                t = doublerotatewithleft(t);
        }
        t->height = max(height(t->left), height(t->right)) + 1;
    }
    else if(x > t->data)
    {
        t->right = insert(t->right,x);
        if(height(t->right) - height(t->left) == 2)
        {
            if(x > t->right->data)
                t = singlerotatewithright(t);
            else
                t = doublerotatewithright(t);
        }
        t->height = max(height(t->left), height(t->right)) + 1;
    }
    // x等于当前节点值，直接返回原节点，不修改
    return t;
}

void preorder(treenode t)
{
    if(t != NULL)
    {
        printf("%d  ",t->data);
        preorder(t->left);
        preorder(t->right);
    }
}

int main()
{
    int choice;
    treenode root;
    root = NULL;
    do
    {
        printf("\n1.Insert\n2.Preorder traversal\n3.Exit");
        printf("\nEnter choice: ");
        scanf("%d",&choice);

        int x;

        switch(choice)
        {
            case 1:
                printf("\nEnter element to insert: ");
                scanf("%d",&x);
                root = insert(root,x);
                break;
            case 2:
                printf("\nThe preorder traversal is:\n");
                preorder(root);
                printf("\n");
                break;
        }

    }while(choice != 3);
    return 0;
}

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