面试题：C语言中平衡二叉树（AVL树）的插入操作

Question

假设你已经有一个用C语言实现的AVL树基本结构，包括节点结构体定义等，请编写一个函数实现AVL树的插入操作，插入后需要保持AVL树的平衡性质。要求详细注释代码逻辑。

Answer 1

// AVL树节点结构体定义
typedef struct AVLNode {
    int key;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

// 获取节点高度的函数
int getHeight(AVLNode *node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 更新节点高度的函数
void updateHeight(AVLNode *node) {
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    node->height = (leftHeight > rightHeight? leftHeight : rightHeight) + 1;
}

// 获取平衡因子的函数
int getBalanceFactor(AVLNode *node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

// 右旋操作
AVLNode* rightRotate(AVLNode *y) {
    AVLNode *x = y->left;
    AVLNode *T2 = x->right;

    // 执行旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    return x;
}

// 左旋操作
AVLNode* leftRotate(AVLNode *x) {
    AVLNode *y = x->right;
    AVLNode *T2 = y->left;

    // 执行旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y;
}

// 插入节点的函数
AVLNode* insert(AVLNode *root, int key) {
    // 正常的BST插入
    if (root == NULL) {
        AVLNode *newNode = (AVLNode*)malloc(sizeof(AVLNode));
        newNode->key = key;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->height = 1;
        return newNode;
    }
    if (key < root->key) {
        root->left = insert(root->left, key);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
    } else {
        // 键值已存在，不进行插入
        return root;
    }

    // 更新节点高度
    updateHeight(root);

    // 获取平衡因子
    int balance = getBalanceFactor(root);

    // 左左情况
    if (balance > 1 && key < root->left->key) {
        return rightRotate(root);
    }
    // 右右情况
    if (balance < -1 && key > root->right->key) {
        return leftRotate(root);
    }
    // 左右情况
    if (balance > 1 && key > root->left->key) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    // 右左情况
    if (balance < -1 && key < root->right->key) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}