如何判断AVL树是否自平衡？我的实现代码是否存在逻辑错误？

核心逻辑错误 #

你的代码存在以下关键问题，导致无法正确将BST转换为AVL树：

• BST插入未维护节点高度与平衡：原始insert函数仅完成普通BST的插入，没有更新节点的height字段，也没有在插入后触发平衡操作。这导致所有节点的height始终是初始化的1，后续平衡函数无法通过height计算正确的平衡因子。
• AVL平衡的调用方式完全错误：main函数中插入所有节点后，循环调用AVLbalance并传入数组元素的做法不符合AVL树的平衡逻辑：
  • AVL树的平衡需要在每个节点插入后的递归回溯过程中进行，针对插入路径上的所有节点检查平衡并调整；
  • AVLbalance函数中通过传入的data判断失衡类型（比如LL/LR等），但插入完成后，这些data与当前树的失衡状态毫无关联，判断条件完全失效。
• AVLbalance函数的逻辑依赖错误：该函数的失衡类型判断依赖于本次插入的data值，但在批量插入完成后调用时，这个参数无法反映当前树的实际失衡原因，导致无法触发正确的旋转操作。

修正后的代码 #

将平衡逻辑整合到插入函数中，让每插入一个节点就自动维护AVL树的性质：

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

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

struct node *new_node(int data) {
    struct node *nn = (struct node *)malloc(sizeof(struct node));
    nn->data = data;
    nn->left = NULL;
    nn->right = NULL;
    nn->height = 1;

    return nn;
}

int height(struct node *n) { 
    if (n == NULL) 
        return 0; 
    return n->height; 
} 

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

struct node *rightRotate(struct node *y) 
{ 
    struct node *x = y->left; 
    struct node *T2 = x->right; 

    x->right = y; 
    y->left = T2; 

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

    return x; 
} 

struct node *leftRotate(struct node *x) { 
    struct node *y = x->right; 
    struct node *T2 = y->left; 

    y->left = x; 
    x->right = T2; 

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

    return y; 
} 

int getBalance(struct node *n) { 
    if (n == NULL) 
        return 0; 
    return height(n->left) - height(n->right); 
} 

// 整合AVL平衡逻辑的插入函数
struct node *insert(struct node *root, int data) {
    // 第一步：普通BST插入
    if (root == NULL)
        return new_node(data);
    
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    else // 不允许重复元素
        return root;

    // 第二步：更新当前节点的高度
    root->height = 1 + max(height(root->left), height(root->right));

    // 第三步：计算平衡因子，判断是否失衡
    int balance = getBalance(root);

    // 处理四种失衡情况
    // Left Left Case
    if (balance > 1 && data < root->left->data)
        return rightRotate(root);

    // Right Right Case
    if (balance < -1 && data > root->right->data)
        return leftRotate(root);

    // Left Right Case
    if (balance > 1 && data > root->left->data) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // Right Left Case
    if (balance < -1 && data < root->right->data) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    // 未失衡则返回原节点
    return root;
}

void pre_order(struct node *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        pre_order(root->left);
        pre_order(root->right);
    }
}

int main() {
    struct node *root = NULL;

    int arr[] = {5, 7, 2, 4, 6};
    int n = sizeof(arr) / sizeof(arr[0]); 

    // 插入时自动维护AVL平衡
    for (int i = 0; i < n; i++)
        root = insert(root, arr[i]);

    printf("BST(已自动平衡为AVL) Pre-order:\n");
    pre_order(root);

    return 0;
}

修正说明 #

1. 将AVLbalance中的逻辑完全整合到insert函数中，在每次插入节点的递归回溯过程中：
   • 更新当前节点的高度；
   • 计算平衡因子，判断是否失衡；
   • 若失衡则根据类型执行对应的旋转操作。
2. 移除了main中无效的循环平衡调用，插入过程直接生成AVL树。
3. 增加了重复元素的处理（直接返回原节点）。

运行修正后的代码，输出的前序遍历即为平衡后的AVL树的前序结果。

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