AVL树插入后平衡因子异常及旋转操作疑问排查

问题概述 #

1. 实现的AVL树在部分测试用例中，遍历二叉搜索树（BST）时节点平衡因子超出[-1,0,1]的允许范围，怀疑leftRotate、rightRotate及Insert函数的返回值存在错误。
2. 对RL旋转场景存在疑问：当树结构为

x
 \ R
  y
 / L
T2

时，是否属于RL情况，需要先执行RR旋转再进行左旋转，而非直接调用leftRotate做单左旋转？

完整代码 #

//Avl tree 

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

typedef struct node{
    int data;
    struct node *left,*right;
} NODE;

NODE* createNode(int ele){
    NODE* newnode = (NODE*)malloc(sizeof(NODE));
    newnode->data = ele;
    newnode->right = newnode->left = NULL;
    return newnode;
}

NODE* createBT(){
    int ele;
    printf("Enter the element(Don't enter any duplicates):\n");
    scanf("%d",&ele);

    if (ele == -1){
        return NULL;
    }

    NODE* newnode = createNode(ele);
    printf("Enter the left child of %d(-1 to stop),\n",ele);
    newnode->left = createBT();
    printf("Enter the right child of %d(-1 to stop),\n",ele);
    newnode->right = createBT();
    return newnode;
}

int max(int a, int b){
    if (a > b)
        return a;
    else 
        return b; 
}

int height(NODE* root){
    if (root == NULL){
        return 0;
    }
    else
        return max(height(root->left),height(root->right)) + 1;
}

int BalFactor(NODE* temp){
    if (temp == NULL){
        printf("Tree is empty\n");
    }
    return height(temp->left) - height(temp->right);
}


//note: The NODE* x is the root element
//Visualise anticlockwise rotation on the root don't think of RL case
NODE* leftRotate(NODE* x){
    NODE* y = x->right;
    NODE* T2 = y->left;
    y->left = x;
    x->right = T2;
    int x_height = max(height(x->left),height(x->right)+1);
    int y_height = max(height(y->left),height(y->right) + 1);
    return y;
}

//note:NODE* y is the root element
NODE* rightRotate(NODE* y){
    NODE* x = y->left;
    NODE* T2 = x->right;
    x->right = y;
    y->left = T2;
    int x_height = max(height(x->left),height(x->right)) + 1;
    int y_height = max(height(y->left),height(y->right)) + 1;
    return x; 
}

//Recursive insert
/*
NODE* insert(NODE* root, int ele){
    if (root == NULL){
        return createNode(ele);
    }

    else if(ele > root->data){
        root->right = insert(root->right,ele);    
    }

    else if(ele < root->data){
        root->left = insert(root->left,ele);    
    }

    else
        return root;
    
    int h = 1 + max(height(root->left),height(root->right));
    int bal = BalFactor(root); 
    
    //balance factor is greater than 1 its either LL or LR 
    //balance factor is lesss than -1  its either RR ot RL

    //LL
    if (bal > 1 && ele < root->left->data){
        return rightRotate(root);
    }
    //RR
    
    if (bal > -1 && ele > root->right->data){
        return leftRotate(root);
    }
    //LR
    if (bal > 1 && ele > root->right->data){
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    //RL
    if (bal < -1 && ele < root->right->data){
        return leftRotate(root);
    }
    return root;
}
*/

//iterative insert function
NODE* insert(NODE* root,int ele){
    NODE* newnode = createNode(ele);
    NODE* x = root;
    NODE* y = NULL;

    while (x != NULL){
        y = x;
        if (ele < x->data)
            x = x->left;
        else
            x = x->right;
    }

    if(y == NULL)
        y = newnode;
    
    else if(ele < y->data)
        y->left = newnode;
    
    else 
        y->right = newnode;

    return y;

    int h = 1 + max(height(y->left),height(y->right));
    int bal = BalFactor(y); 
    //LL
    //balance factor is greater than 1 its either LL or LR 
    //balance factor is lesss than -1  its either RR ot RL
    if (bal > 1 && ele < y->left->data){
        return rightRotate(y);
    }
    //RR
    
    if (bal > -1 && ele > y->right->data){
        return leftRotate(y);
    }
    //LR
    if (bal > 1 && ele > y->right->data){
        y->left = leftRotate(y->left);
        return rightRotate(y);
    }
    //RL
    if (bal < -1 && ele < y->right->data){
        return leftRotate(y);
    }
    return root;
}

void inorder(NODE* root){
    if (root != NULL){
        inorder(root->left);
        printf(" %d (%d)", root->data, BalFactor(root));
        inorder(root->right);
    }
}
 
void postorder(NODE* root){
    if (root != NULL){
        postorder(root->left);
        postorder(root->right);
        printf(" %d (%d)", root->data, BalFactor(root));
    }
}

void preorder(NODE* root){
    if (root != NULL){
        printf(" %d (%d)", root->data, BalFactor(root));
        preorder(root->left);
        preorder(root->right);
    }
}


int main(){
    NODE* root  = NULL;
    root = createBT();
    int ch,ele;
    printf("\nList of operations:\n1.Insert\n2.Traversals and display balance factor\n3.Exit\n");
    while(1){
        printf("\nEnter your choice:\n");
        scanf("%d",&ch);

        if (ch == 1){
            printf("Enter the element to insert:\n");
            scanf("%d",&ele);
            insert(root,ele);
        }

        else if(ch == 2){
            printf("Inorder traversal:\n");
            inorder(root);
            
            printf("\nPreorder traversal:\n");
            preorder(root);
            
            printf("\nPostorder traversal:\n");
            postorder(root);
        }

        else if(ch == 3){
            break;
        }
        else{
            printf("Enter a valid choice\n");
        }
    }
    return 0;
}

测试输出 #

Enter the element(Don't enter any duplicates):
10
Enter the left child of 10(-1 to stop),
Enter the element(Don't enter any duplicates):
9
Enter the left child of 9(-1 to stop),
Enter the element(Don't enter any duplicates):
8
Enter the left child of 8(-1 to stop),
Enter the element(Don't enter any duplicates):
7
Enter the left child of 7(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 7(-1 to stop),
Enter the element(Don't enter any duplicates):
12
Enter the left child of 12(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 12(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 8(-1 to stop),
Enter the element(Don't enter any duplicates):
13
Enter the left child of 13(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 13(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 9(-1 to stop),
Enter the element(Don't enter any duplicates):
20
Enter the left child of 20(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 20(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 10(-1 to stop),
Enter the element(Don't enter any duplicates):
21
Enter the left child of 21(-1 to stop),
Enter the element(Don't enter any duplicates):
-1
Enter the right child of 21(-1 to stop),
Enter the element(Don't enter any duplicates):
-1

 10 (1) 9 (2) 8 (1) 7 (-1) 12 (0) 13 (0) 20 (0) 21 (-2) 30 (-1) 40 (0)
Postorder traversal:
 12 (0) 7 (-1) 13 (0) 8 (1) 20 (0) 9 (2) 40 (0) 30 (-1) 21 (-2) 10 (1)
Enter your choice:
3

问题排查与解答 #

一、平衡因子超范围的核心原因 #

1. 迭代版insert函数致命错误

迭代插入函数中，插入节点后直接return y;，导致后续的平衡检查、旋转逻辑完全未执行。同时：

• main函数调用insert时未接收返回值，即使修复return问题，树的根节点也无法更新。
• 迭代插入未记录路径上的所有祖先节点，AVL树插入需要从新节点向上回溯检查每个节点的平衡因子，当前仅检查父节点y，逻辑不完整。

2. 旋转函数的无效代码

leftRotate和rightRotate中计算x_height、y_height的代码无意义，当前结构体未存储height字段，height函数会自动递归计算，旋转后无需手动赋值。

3. 递归版insert的逻辑错误

递归版存在多处条件判断错误：

• RR旋转条件错误：bal > -1应改为bal < -1
• LR旋转条件错误：ele > root->right->data应改为ele > root->left->data
• RL旋转处理错误：仅执行左旋转，未先对右子树做右旋转。

二、RL旋转场景的澄清 #

你描述的结构确实是RL型失衡，不能直接执行单左旋转：

• 直接左旋转x会导致T2成为x的右子树，旋转后x的平衡因子为-1，y的平衡因子为1，子树仍处于失衡状态。
• 正确步骤：先对y（x的右子树）执行右旋转，将结构转换为RR型，再对x执行左旋转，旋转后整个子树的平衡因子会回到合法范围。

修复后的关键代码示例 #

修复的递归版insert函数

NODE* insert(NODE* root, int ele){
    if (root == NULL){
        return createNode(ele);
    }

    else if(ele > root->data){
        root->right = insert(root->right,ele);    
    }

    else if(ele < root->data){
        root->left = insert(root->left,ele);    
    }

    else
        return root;
    
    int bal = BalFactor(root); 
    
    // LL型
    if (bal > 1 && ele < root->left->data){
        return rightRotate(root);
    }
    // RR型
    if (bal < -1 && ele > root->right->data){
        return leftRotate(root);
    }
    // LR型
    if (bal > 1 && ele > root->left->data){
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    // RL型
    if (bal < -1 && ele < root->right->data){
        root->right = rightRotate(root->right); // 先右旋右子树
        return leftRotate(root);
    }
    return root;
}

修复main函数中的调用

if (ch == 1){
    printf("Enter the element to insert:\n");
    scanf("%d",&ele);
    root = insert(root,ele); // 接收返回的新根节点
}

其他优化建议 #

• 在NODE结构体中添加int height字段，插入、旋转后直接更新，避免递归计算height的性能损耗。
• 修改BalFactor函数，当temp为NULL时不要打印信息，避免干扰正常输出。

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