C语言实现AVL树时平衡逻辑异常问题排查

问题根源分析 #

• 指针操作逻辑错误：balance函数接收的是Node *node（值传递的指针），旋转后temp指向新的根节点，但通过*node = *temp将新节点的内容拷贝到旧节点内存中，会导致旧节点的left_node/right_node指向自身（比如示例中原根是1，旋转后temp指向2，拷贝后原1节点的left_node指向自己），形成循环引用，最终打印时触发无限递归。
• 旋转后未更新节点高度：rotate_left和rotate_right函数未更新旋转后节点的height值，导致高度计算持续错误。
• 平衡函数参数设计错误：AVL树平衡操作需要修改父节点的指针指向新根，因此必须传递指针的指针（Node **node），而非单个指针。

具体修正步骤 #

1. 修改balance函数参数为指针的指针 #

void balance(Node **node) {
    int height_diff = get_height_difference(*node);
    Node *temp = *node;

    if (height_diff > 1) {
        Node *left = (*node)->left_node;
        if (get_height_difference(left) < 0) {
            temp = rotate_left(temp);
        }
        temp = rotate_right(temp);
    } else if (height_diff < -1) {
        Node *right = (*node)->right_node;
        if (get_height_difference(right) > 0) {
            temp = rotate_right(temp);
        }
        temp = rotate_left(temp);
    }

    // 更新父节点指针指向新根
    *node = temp;
    // 同步更新新根的高度
    (*node)->height = get_node_height(*node);
}

2. 修改add函数中balance的调用方式 #

if (abs(get_height_difference(*node)) >= 2) {
    balance(node);
}

3. 在旋转函数中补充高度更新 #

Node *rotate_left(Node *node) {
    Node *right = node->right_node;
    node->right_node = right->left_node;
    right->left_node = node;

    // 先更新原节点高度，再更新新根高度
    node->height = get_node_height(node);
    right->height = get_node_height(right);
    return right;
}

Node *rotate_right(Node *node) {
    Node *left = node->left_node;
    node->left_node = left->right_node;
    left->right_node = node;

    node->height = get_node_height(node);
    left->height = get_node_height(left);
    return left;
}

4. 修复to_string_int的内存泄漏（可选但重要） #

原实现每次调用都malloc但未释放，改成静态缓冲区避免泄漏：

char* to_string_int(void *data) {
    static char c[2];
    c[0] = *(int*)data + '0';
    c[1] = '\0';
    return c;
}

修正后的完整代码 #

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

struct Node{
    void *data;
    struct Node *left_node;
    struct Node *right_node;
    int height;
};

typedef struct Node Node;

struct AvlTree{
    Node *root;
    int (*comparator)(void*, void*);
    char* (*to_string)(void*);
};

typedef struct AvlTree AvlTree;

AvlTree *create_avl_tree(int (*)(void*, void*), char* (*)(void*));
void add_to_avl_tree(AvlTree*, void*);
void add(Node**, void*, int(*)(void*, void*));
void balance(Node**);
int get_node_height(Node*);
int get_height_difference(Node*);
Node *rotate_left(Node *node);
Node *rotate_right(Node *node);
char* to_string_int(void *data);
void print_tree(AvlTree *avl_tree);
static void print(Node *node, char* (*to_string)(void*));


AvlTree *create_avl_tree(int (*comparator)(void*, void*), char* (*to_string)(void*)){
    AvlTree *avl_tree = malloc(sizeof(AvlTree));
    if(avl_tree == NULL){
        puts("Out of Memory Exception");
        exit(2);
    }
    avl_tree->root = NULL;
    avl_tree->comparator = comparator;
    avl_tree->to_string = to_string;
    return avl_tree;
}

void add_to_avl_tree(AvlTree *avl_tree, void *data){
    if(avl_tree == NULL){
        puts("Null Pointer Exception");
        exit(2);
    }else{
        if(avl_tree->root == NULL){
            avl_tree->root = malloc(sizeof(Node));
            if(avl_tree->root == NULL){
                puts("Out of Memory Exception");
                exit(2);
            }
            avl_tree->root->data = data;
            avl_tree->root->left_node = NULL;
            avl_tree->root->right_node = NULL;
            avl_tree->root->height = 0;
        }else{
            add(&avl_tree->root, data, avl_tree->comparator);
        }
    }
}

void add(Node **node, void *data, int (*comparator)(void*, void*)){
    int n = comparator((*node)->data, data);
    if(n < 0){
        if((*node)->left_node == NULL){
            (*node)->left_node = malloc(sizeof(Node));
            if((*node)->left_node == NULL){
                puts("Out of Memory Exception");
                exit(2);
            }
            (*node)->left_node->data = data;
            (*node)->left_node->left_node = NULL;
            (*node)->left_node->right_node = NULL;
            (*node)->left_node->height = 0;
        }else{
            add(&(*node)->left_node, data, comparator);
        }
    }
    else if(n > 0){
        if((*node)->right_node == NULL){
            (*node)->right_node = malloc(sizeof(Node));
            if((*node)->right_node == NULL){
                puts("Out of Memory Exception");
                exit(2);
            }
            (*node)->right_node->data = data;
            (*node)->right_node->left_node = NULL;
            (*node)->right_node->right_node = NULL;
            (*node)->right_node->height = 0;
        }else{
            add(&(*node)->right_node, data, comparator);
        }
    }

    (*node)->height = get_node_height(*node);

    if(abs(get_height_difference(*node)) >= 2){
        balance(node);
    }
}

int get_node_height(Node *node){
    if(node == NULL) return -1; // 空节点高度设为-1，叶子节点高度自然为0
    int height_left = get_node_height(node->left_node) + 1;
    int height_right = get_node_height(node->right_node) + 1;
    return height_left > height_right ? height_left : height_right;
}

int get_height_difference(Node *node){
    if(node == NULL) return 0;
    return get_node_height(node->left_node) - get_node_height(node->right_node);
}

void balance(Node **node){
    int height_diff = get_height_difference(*node);
    Node *temp = *node;

    if(height_diff > 1){
        Node *left = (*node)->left_node;
        if(get_height_difference(left) < 0){
            temp = rotate_left(temp);
        }
        temp = rotate_right(temp);
    }else if(height_diff < -1){
        Node *right = (*node)->right_node;
        if(get_height_difference(right) > 0){
            temp = rotate_right(temp);
        }
        temp = rotate_left(temp);
    }

    *node = temp;
    (*node)->height = get_node_height(*node);
}

Node *rotate_left(Node *node){
    Node *right = node->right_node;
    node->right_node = right->left_node;
    right->left_node = node;

    node->height = get_node_height(node);
    right->height = get_node_height(right);
    return right;
}

Node *rotate_right(Node *node){
    Node *left = node->left_node;
    node->left_node = left->right_node;
    left->right_node = node;

    node->height = get_node_height(node);
    left->height = get_node_height(left);
    return left;
}

int int_comp(void *s, void *t){
    return *(int*)t - *(int*)s;
}

char* to_string_int(void *data){
    static char c[2];
    c[0] = *(int*)data + '0';
    c[1] = '\0';
    return c;
}

void print_tree(AvlTree *avl_tree){
    if(avl_tree != NULL){
        print(avl_tree->root, avl_tree->to_string);
    }
}

static void print(Node *node, char* (*to_string)(void*)){
    static int width = 0;
    printf("%*s\n", width, to_string(node->data));

    int next_width = 4; // 固定缩进宽度，简化逻辑
    width += next_width;

    if(node->left_node != NULL)
        print(node->left_node, to_string);
    else
        printf("%*s\n", width, ".");

    if(node->right_node != NULL)
        print(node->right_node, to_string);
    else
        printf("%*s\n", width, ".");

    width -= next_width;
}

int main(){
    AvlTree *avl_tree = create_avl_tree(int_comp, to_string_int);
    int a[] = {1,2,3};
    for(int i =0; i < 3; i++){
        add_to_avl_tree(avl_tree, &a[i]);
    }
    print_tree(avl_tree);
    return 0;
}

输出结果 #

2
    1
        .
        .
    3
        .
        .

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