在数据结构中，平衡二叉搜索树（Balanced Binary Search Tree）是一种能够自动保持高度平衡的二叉树结构。其中，AVL树是最早被提出的自平衡二叉搜索树之一，由Adelson-Velskii和Landis两位科学家于1962年提出。AVL树通过维护每个节点的平衡因子（Balance Factor），确保树的高度始终处于对数级别，从而保证了查找、插入和删除操作的时间复杂度为O(log n)。
本文将详细介绍AVL树的基本原理，并提供一份基于C语言的完整实现代码，帮助读者理解如何在实际编程中应用这一高效的数据结构。
一、AVL树的基本概念
AVL树是一种二叉搜索树，其关键特性在于：任意节点的左子树与右子树的高度差不超过1。如果某节点的左右子树高度差超过1，则该树被视为不平衡，需要进行旋转操作以恢复平衡。
每个节点通常包含以下信息：
- 数据域（data）
- 左子节点指针（left）
- 右子节点指针（right）
- 高度值（height）
AVL树的平衡因子定义为：`balance_factor = height(left_subtree) - height(right_subtree)`。当平衡因子的绝对值大于1时，表示该节点失衡，需进行调整。
二、AVL树的插入操作
插入操作是AVL树中最常见的操作之一。在插入新节点后，需要从插入点向上回溯，检查每个祖先节点是否仍然满足平衡条件。若发现某个节点失衡，则根据具体情况执行相应的旋转操作。
AVL树有四种基本的旋转方式：
1. 左旋（Left Rotation）：当右子树的高度比左子树高2，且右子节点的右子树更高时。
2. 右旋（Right Rotation）：当左子树的高度比右子树高2，且左子节点的左子树更高时。
3. 左右旋（Left-Right Rotation）：当左子树的高度比右子树高2，但左子节点的右子树更高时。
4. 右左旋（Right-Left Rotation）：当右子树的高度比左子树高2，但右子节点的左子树更高时。
三、AVL树的C语言实现
下面是一个完整的AVL树实现示例，包括节点定义、插入函数、旋转操作以及打印功能。
```c
include
include
// 定义节点结构体
typedef struct Node {
int key;
struct Node left;
struct Node right;
int height;
} Node;
// 创建新节点
Node newNode(int key) {
Node node = (Node)malloc(sizeof(Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // 新节点初始高度为1
return node;
}
// 获取节点的高度
int height(Node node) {
if (node == NULL)
return 0;
return node->height;
}
// 计算平衡因子
int getBalanceFactor(Node node) {
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
// 左旋操作
Node leftRotate(Node x) {
Node y = x->right;
Node T2 = y->left;
// 执行旋转
y->left = x;
x->right = T2;
// 更新高度
x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
return y;
}
// 右旋操作
Node rightRotate(Node y) {
Node x = y->left;
Node T2 = x->right;
// 执行旋转
x->right = y;
y->left = T2;
// 更新高度
y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));
x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));
return x;
}
// 插入新节点
Node insert(Node node, int key) {
// 基本的BST插入
if (node == NULL)
return newNode(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; // 不允许重复键
// 更新高度
node->height = 1 + (height(node->left) > height(node->right) ? height(node->left) : height(node->right));
// 检查平衡因子并进行旋转
int balance = getBalanceFactor(node);
// 左左情况
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// 右右情况
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// 左右情况
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// 右左情况
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 中序遍历输出
void inOrder(Node root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->key);
inOrder(root->right);
}
}
// 主函数测试
int main() {
Node root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("AVL树中序遍历结果：\n");
inOrder(root);
printf("\n");
return 0;
}
```
四、总结
AVL树作为一种高效的自平衡二叉搜索树，广泛应用于需要快速查找、插入和删除操作的场景中。通过合理的旋转机制，它能够在每次操作后保持树的平衡，从而避免最坏情况下的时间复杂度退化。
本文提供了AVL树的C语言实现代码，涵盖了节点定义、插入逻辑、旋转操作和中序遍历等功能。希望这份代码能够帮助读者更好地理解AVL树的原理及其实际应用。
