C语言实现AVL树节点删除时平衡异常的问题排查求助

问题核心 #

你的AVL树删除操作后无法维持平衡，根源在于旋转函数的节点高度更新顺序错误，导致平衡因子计算不准确，无法触发正确的旋转操作。此外代码中存在几处语法和拼写错误，需一并修正。

关键修复点 #

1. 右旋转函数（right_int8_rotate）高度更新顺序错误 #

原代码先更新新根节点x的高度，再更新原根节点y的高度，但x的高度依赖于y的高度，必须先更新y的高度：

// 错误顺序
x->height = max_num(int8_node_height(y->left), int8_node_height(y->right)) + 1;
y->height = max_num(int8_node_height(x->left), int8_node_height(x->right)) + 1;

// 修正后顺序
y->height = max_num(int8_node_height(y->left), int8_node_height(y->right)) + 1;
x->height = max_num(int8_node_height(x->left), int8_node_height(x->right)) + 1;

2. 语法与拼写错误修正 #

• Int8BT结构体定义末尾缺少分号，添加分号；
• push_int8_btree中错误提示initializex改为initialized；
• free_int8_btree中错误提示Unitialized改为Uninitialized；
• pop_int8_btree中恢复初始化状态检查，并将Cannon改为Cannot。

修正后的完整代码 #

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

typedef struct int8_btree {
    int8_t key;
    struct int8_btree *left;
    struct int8_btree *right;
    int height;
} int8_btree;

typedef struct {
    size_t active_length;
    struct int8_btree *root;
    bool status;
} Int8BT; // 补充分号

void init_int8_btree(Int8BT *tree) {
    tree->active_length = 0;
    tree->root = NULL;
    tree->status = true;
}

int8_btree *new_int8_node(int8_t key) {
    struct int8_btree *node = malloc(sizeof(int8_btree));
    if (node == NULL) return node;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return node;
}

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

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

int8_btree *right_int8_rotate(int8_btree * y) {
    struct int8_btree *x = y->left;
    struct int8_btree *T2 = x->right;

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

    // 修正高度更新顺序
    y->height = max_num(int8_node_height(y->left), int8_node_height(y->right)) + 1;
    x->height = max_num(int8_node_height(x->left), int8_node_height(x->right)) + 1;
    return x;
}

int8_btree *left_int8_rotate(int8_btree *x) {
    struct int8_btree *y = x->right;
    struct int8_btree *T2 = y->left;

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

    x->height = max_num(int8_node_height(x->left), int8_node_height(x->right)) + 1;
    y->height = max_num(int8_node_height(y->left), int8_node_height(y->right)) + 1;
    return y;
}

int int8_node_balance(int8_btree *node) {
    if (node == NULL) return 0;
    return int8_node_height(node->left) - int8_node_height(node->right);
}

int8_btree *insert_int8_btree(int8_btree *node, int8_t key) {
    if (node == NULL)
        return new_int8_node(key);

    if (key < node->key)
        node->left  = insert_int8_btree(node->left, key);
    else if (key > node->key)
        node->right = insert_int8_btree(node->right, key);
    else
        return node;

    node->height = 1 + max_num(int8_node_height(node->left),
                               int8_node_height(node->right));

    short int balance = int8_node_balance(node);

    if (balance > 1 && key < node->left->key)
        return right_int8_rotate(node);

    if (balance < -1 && key > node->right->key)
        return left_int8_rotate(node);

    if (balance > 1 && key > node->left->key)
    {
        node->left =  left_int8_rotate(node->left);
        return right_int8_rotate(node);
    }

    if (balance < -1 && key < node->right->key)
    {
        node->right = right_int8_rotate(node->right);
        return left_int8_rotate(node);
    }

    return node;
}

int push_int8_btree(Int8BT *btree, int8_t key) {
    if (btree->status != true) {
        fprintf(stderr, "Binary tree struct not initialized\n"); // 修正拼写
        return -1;
    }
    btree->root = insert_int8_btree(btree->root, key);
    if (btree->root == NULL) {
        fprintf(stderr, "Malloc failed in file %s on line %d\n", __FILE__, __LINE__);
        return -1;
    }
    btree->active_length += 1;
    return 1;
}

void freeint8(int8_btree *root) {
    if (root == NULL) return;
    freeint8(root->right);
    freeint8(root->left);
    free(root);
}

void free_int8_btree(Int8BT *btree) {
    if (btree->status != true) {
        fprintf(stderr, "Uninitialized binary tree struct cannot be freed\n"); // 修正拼写
        return;
    }
    freeint8(btree->root);
}

int8_btree *min_int8_node(int8_btree *root) {
    struct int8_btree *current = root;
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}

int8_btree *delete_int8_node(int8_btree *root, int8_t key) {
    if (root == NULL)
        return root;

    if ( key < root->key )
        root->left = delete_int8_node(root->left, key);
    else if( key > root->key )
        root->right = delete_int8_node(root->right, key);
    else
    {
        if( (root->left == NULL) || (root->right == NULL) )
        {
            struct int8_btree *temp = root->left ? root->left : root->right;

            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else
             *root = *temp;
            free(temp);
        }
        else
        {
            struct int8_btree* temp = min_int8_node(root->right);
            root->key = temp->key;
            root->right = delete_int8_node(root->right, temp->key);
        }
    }

    if (root == NULL)
      return root;

    root->height = 1 + max_num(int8_node_height(root->left),
                               int8_node_height(root->right));

    short int balance = int8_node_balance(root);

    if (balance > 1 && int8_node_balance(root->left) >= 0)
        return right_int8_rotate(root);

    if (balance > 1 && int8_node_balance(root->left) < 0)
    {
        root->left =  left_int8_rotate(root->left);
        return right_int8_rotate(root);
    }

    if (balance < -1 && int8_node_balance(root->right) <= 0)
        return left_int8_rotate(root);

    if (balance < -1 && int8_node_balance(root->right) > 0)
    {
        root->right = right_int8_rotate(root->right);
        return left_int8_rotate(root);
    }

    return root;
}

void pop_int8_btree(Int8BT *btree, int8_t key) {
    if (btree->status != true) {
        fprintf(stderr, "Cannot pop binary tree struct that is not initialized\n"); // 修正拼写并恢复检查
        return;
    }
    btree->root = delete_int8_node(btree->root, key);
    btree->active_length -= 1;
}

void print_preorder(int8_btree *root)
{
    if(root != NULL)
    {
        printf("%d ", root->key);
        print_preorder(root->left);
        print_preorder(root->right);
    }
}

void print_int8_tree(Int8BT *tree) {
    print_preorder(tree->root);
    printf("\n");
}

void test_repeat_int8_list(void **state) {
    Int8BT tree;
    init_int8_btree(&tree);
    push_int8_btree(&tree, 9);
    push_int8_btree(&tree, 5);
    push_int8_btree(&tree, 10);
    push_int8_btree(&tree, 0);
    push_int8_btree(&tree, 6);
    push_int8_btree(&tree, 11);
    push_int8_btree(&tree, -1);
    push_int8_btree(&tree, 1);
    push_int8_btree(&tree, 2);

    print_int8_tree(&tree);
    pop_int8_btree(&tree, 10);
    print_int8_tree(&tree); // 现在输出预期结果：1 0 -1 9 5 2 6 11
    free_int8_btree(&tree);
}

验证结果 #

修复后执行测试用例，删除节点10后的前序遍历输出为1 0 -1 9 5 2 6 11，与预期一致，AVL树的平衡特性得到维持。

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