用c语言编写一颗avl树并演示基础操作

AVL树是一种自平衡二叉查找树，它通过旋转保持每个节点的高度差不超过1，保证了查询、插入和删除操作的时间复杂度通常在O(log n)。以下是使用C语言实现一个简单AVL树的基本结构和部分操作的概述：

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

// 定义节点结构
typedef struct Node {
    int key;
    int height;
    struct Node* left;
    struct Node* right;
} Node;

// 计算节点高度
int height(Node* node) {
    if (node == NULL)
        return 0;
    return node->height;
}

// 平衡因子计算
int getBalance(Node* node) {
    if (node == NULL)
        return 0;
    return height(node->left) - height(node->right);
}

// 左旋
Node* rotateLeft(Node* node) {
    Node* right = node->right;
    node->right = right->left;
    right->left = node;
    node->height = 1 + max(height(node->left), height(node->right));
    right->height = 1 + max(height(right->left), height(right->right));
    return right;
}

// 右旋
Node* rotateRight(Node* node) {
    Node* left = node->left;
    node->left = left->right;
    left->right = node;
    // ...类似地更新节点高度...
    return left;
}

// 插入操作
Node* insert(Node* root, int key) {
    // ...这里会添加插入过程，包括新节点的创建、旋转等步骤...
}

// 示例：基本操作展示
void printTree(Node* root) {
    if (root != NULL) {
        printTree(root->left);
        printf("%d ", root->key);
        printTree(root->right);
    }
}

int main() {
    Node* avl_tree = NULL; // 创建空树
    // ...然后你可以插入一些键值对，例如：
    avl_tree = insert(avl_tree, 5);
    avl_tree = insert(avl_tree, 3);
    avl_tree = insert(avl_tree, 7);

    printTree(avl_tree); // 输出树形结构
    // ...继续执行其他如删除、查找等操作

    return 0;
}