C语言AVL树详解（从零开始掌握平衡二叉搜索树的实现与应用）

AVL树的核心操作

AVL树在普通二叉搜索树的基础上增加了以下关键操作：

• 计算节点高度
• 计算平衡因子
• 四种旋转操作：LL、RR、LR、RL

1. 节点定义

首先，我们定义AVL树的节点结构：

typedef struct Node {    int data;    struct Node* left;    struct Node* right;    int height;  // 记录当前节点的高度} Node;  

2. 辅助函数

我们需要一些辅助函数来获取高度、创建新节点、计算最大值等：

int max(int a, int b) {    return (a > b) ? a : b;}int getHeight(Node* node) {    if (node == NULL)        return 0;    return node->height;}Node* createNode(int data) {    Node* node = (Node*)malloc(sizeof(Node));    node->data = data;    node->left = NULL;    node->right = NULL;    node->height = 1;  // 新节点高度为1    return node;}  

3. 旋转操作

当插入或删除导致树不平衡时，需要通过旋转恢复平衡。以下是右旋（RR）和左旋（LL）的实现：

// 右旋（处理LL情况）Node* rotateRight(Node* y) {    Node* x = y->left;    Node* T2 = x->right;    // 执行旋转    x->right = y;    y->left = T2;    // 更新高度    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;    return x;  // 新的根节点}// 左旋（处理RR情况）Node* rotateLeft(Node* x) {    Node* y = x->right;    Node* T2 = y->left;    // 执行旋转    y->left = x;    x->right = T2;    // 更新高度    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;    return y;  // 新的根节点}  

4. 插入操作

插入是AVL树最核心的操作之一。插入后需检查平衡因子，并根据情况执行旋转：

Node* insert(Node* node, int data) {    // 1. 执行标准BST插入    if (node == NULL)        return createNode(data);    if (data < node->data)        node->left = insert(node->left, data);    else if (data > node->data)        node->right = insert(node->right, data);    else        return node;  // 不允许重复值    // 2. 更新当前节点高度    node->height = 1 + max(getHeight(node->left), getHeight(node->right));    // 3. 获取平衡因子    int balance = getHeight(node->left) - getHeight(node->right);    // 4. 如果不平衡，进行旋转    // Left Left Case    if (balance > 1 && data < node->left->data)        return rotateRight(node);    // Right Right Case    if (balance < -1 && data > node->right->data)        return rotateLeft(node);    // Left Right Case    if (balance > 1 && data > node->left->data) {        node->left = rotateLeft(node->left);        return rotateRight(node);    }    // Right Left Case    if (balance < -1 && data < node->right->data) {        node->right = rotateRight(node->right);        return rotateLeft(node);    }    return node;}  

应用场景

C语言平衡二叉树（如AVL树）广泛应用于数据库索引、内存管理、实时系统等领域，其中对查询效率有严格要求。相比普通BST，AVL树牺牲少量插入/删除开销，换取稳定的查询性能。

总结

通过本教程，你已经掌握了AVL树插入删除的基本原理和C语言实现方法。虽然代码看起来稍显复杂，但只要理解了四种旋转的触发条件和执行逻辑，就能轻松驾驭这一高效的数据结构。

建议你动手编写完整代码并测试不同插入顺序，观察树的结构变化。这不仅能加深理解，还能提升你的C语言AVL树实战能力！

如果你对AVL树实现还有疑问，欢迎在评论区留言交流！