AVL树的旋转及根节点更新

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

typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
    int height;
} Node;

// 返回节点的高度
int getHeight(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 计算节点的平衡因子
int getBalanceFactor(Node* node) {
    if (node == NULL) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

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

// 创建一个新节点
Node* createNode(int key) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    return node;
}

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

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

    updateHeight(y);
    updateHeight(x);

    return x;
}

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

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

    updateHeight(x);
    updateHeight(y);

    return y;
}

// 插入节点到 AVL 树
Node* insert(Node* node, int key) {
    if (node == NULL) {
        return createNode(key);
    }

    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    } else {
        return node; // 不允许插入相同的节点值
    }

    updateHeight(node);

    int balanceFactor = getBalanceFactor(node);
    
    // 左左情况
    if (balanceFactor > 1 && key < node->left->key) {
        return rotateRight(node);
    }

    // 右右情况
    if (balanceFactor < -1 && key > node->right->key) {
        return rotateLeft(node);
    }

    // 左右情况
    if (balanceFactor > 1 && key > node->left->key) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }

    // 右左情况
    if (balanceFactor < -1 && key < node->right->key) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;
}

// 中序遍历 AVL 树（升序输出）
void inorderTraversal(Node* node) {
    if (node != NULL) {
        inorderTraversal(node->left);
        printf("%d ", node->key);
        inorderTraversal(node->right);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 10);
    printf("%d ",root->key);
    root = insert(root, 20);
    printf("%d ",root->key);
    root = insert(root, 30);
    printf("%d ",root->key);
    root = insert(root, 40);
    printf("%d ",root->key);
    root = insert(root, 35);
    printf("%d ",root->key);
    printf("AVL 树中序遍历结果：");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

按这个代码，当输入35后需要进行函数rotateLeft(root)，此时根节点不是更新为3了吗，为什么打印出来还是2
还有一个问题，很多版本的AVL树的实现都不太一样，是没有一个统一的标准吗

在插入节点35后调用函数rotateLeft(root)时，根节点会更新为3而不是2。根据代码中的逻辑，当插入节点35之后，根节点10的平衡因子变为2，因此会触发左旋操作。在左旋操作中，根节点会被更新为其右子节点20，而不是3。

AVL树的实现确实存在一定的灵活性，不同的实现可能会有不同的细节。这是因为AVL树的核心概念是自平衡二叉搜索树，只要满足平衡条件，具体的实现细节可以有所不同。虽然有一些基本的标准和原则，但没有一个统一的标准来定义AVL树的实现。因此，不同的实现可能在旋转操作、平衡因子的计算、插入和删除操作的细节等方面有所不同。

AVL树只要满足平衡条件，即任何节点的左子树和右子树的高度差不超过1就可以了。