在C中实现AVL树

Question

我正在尝试将数组实现为 BST，在打印出 BST（预序）后，我正在平衡它（具有预序输出的 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;
}

struct node *insert(struct node *root, int data) {
    if (root == NULL)
        return new_node(data);
    else {
        if (data < root->data)
            root->left = insert(root->left, data);
        if (data > root->data)
            root->right = insert(root->right, data);
        return root;
    }
}

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

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); 
} 

struct node *AVLbalance(struct node *root, int data) 
{ 
    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; 
} 

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

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

    for (int i = 0; i < n; i++)
        root = insert(root, arr[i]);

    printf("BST Pre-order:\n");
    pre_order(root);

    for (int j = 0; j < n; j++)
       root = AVLbalance(root, arr[j]);
        
    printf("\nBalanced (AVL) Pre-order:\n");
    pre_order(root);

    return 0;
}

尝试了几个小时后，我无法判断树在被要求时是否能够自行平衡。有逻辑错误吗？程序编译时没有任何警告或错误。帮助！

Answer 1

主要问题是你依靠

nn->height

来平衡树，但在插入新节点时不更新节点高度。