平衡二叉树：AVL树
说到二叉搜索树，你可能会想——这不就是个排好序的树吗？查找、插入、删除都是 O(log n)，挺完美的。但现实往往很骨感。我在项目里遇到过一种情况：数据是按顺序插入的，结果二叉搜索树直接退化成了链表，查找效率从 O(log n) 掉到了 O(n)。
嗯，这就是 AVL 树要解决的问题。它通过一种叫「平衡因子」的机制，让树始终保持平衡。说白了，就是不让树长歪。
什么是 AVL 树？
AVL 树是自平衡二叉搜索树。它的发明者是 Adelson-Velsky 和 Landis，所以叫 AVL。它的核心要求是：任意节点的左右子树高度差不超过 1。
你想想看，如果每个节点都满足这个条件，整棵树的高度就能维持在 O(log n)。查找效率自然就稳了。
核心定义：AVL 树 = 二叉搜索树 + 平衡条件
平衡因子
平衡因子是 AVL 树的灵魂。它的计算公式很简单：
平衡因子 = 左子树高度 - 右子树高度平衡因子的取值范围只有三个：-1、0、1。如果某个节点的平衡因子绝对值大于 1，那就说明这棵树不平衡了，需要旋转。
| 平衡因子 | 含义 |
|---|---|
| 0 | 左右子树等高，完美平衡 |
| 1 | 左子树比右子树高 1，可以接受 |
| -1 | 右子树比左子树高 1，可以接受 |
| 2 或 -2 | 不平衡！需要旋转 |
我个人习惯在节点结构体里直接存高度，而不是平衡因子。因为高度更容易维护，计算平衡因子时直接相减就行。
typedef struct AVLNode {
int key;
struct AVLNode *left;
struct AVLNode *right;
int height; // 节点高度
} AVLNode;旋转操作
旋转是 AVL 树的核心操作。一共有四种情况：LL、RR、LR、RL。别被这些缩写吓到，其实逻辑很清晰。
我曾经在调试一个内存数据库时，因为旋转写错了，导致数据丢失。那次教训让我深刻理解了旋转的本质——旋转不改变中序遍历顺序。
LL 旋转（右旋）
当新节点插入到左子树的左子树时，触发 LL 旋转。说白了就是左边太重了，往右掰一下。
AVLNode* rotateLL(AVLNode *y) {
AVLNode *x = y->left;
AVLNode *T2 = x->right;
// 旋转
x->right = y;
y->left = T2;
// 更新高度
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x; // 新根节点
}RR 旋转（左旋）
新节点插入到右子树的右子树时，触发 RR 旋转。和 LL 对称，往左掰。
AVLNode* rotateRR(AVLNode *x) {
AVLNode *y = x->right;
AVLNode *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}LR 旋转（先左旋后右旋）
新节点插入到左子树的右子树时，需要先对左子树做 RR 旋转，再对当前节点做 LL 旋转。嗯，这里容易搞混，我建议你画图理解。
AVLNode* rotateLR(AVLNode *z) {
z->left = rotateRR(z->left);
return rotateLL(z);
}RL 旋转（先右旋后左旋）
新节点插入到右子树的左子树时，先对右子树做 LL 旋转，再对当前节点做 RR 旋转。
AVLNode* rotateRL(AVLNode *z) {
z->right = rotateLL(z->right);
return rotateRR(z);
}记忆技巧：LL 和 RR 是单旋，LR 和 RL 是双旋。双旋的名字就是旋转顺序——LR 就是先左旋（L）后右旋（R）。
插入操作
AVL 树的插入分三步：
- 像普通二叉搜索树一样插入节点
- 更新沿途节点的高度
- 检查平衡因子，如果不平衡就旋转
AVLNode* insert(AVLNode *node, int key) {
// 1. 普通 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; // 重复键，不插入
// 2. 更新高度
node->height = 1 + max(height(node->left), height(node->right));
// 3. 获取平衡因子
int balance = getBalance(node);
// 4. 判断旋转类型
if (balance > 1 && key < node->left->key)
return rotateLL(node);
if (balance < -1 && key > node->right->key)
return rotateRR(node);
if (balance > 1 && key > node->left->key)
return rotateLR(node);
if (balance < -1 && key < node->right->key)
return rotateRL(node);
return node;
}注意：插入后要递归更新高度。我曾经漏掉了这一步，结果平衡因子算出来全是错的，调试了一下午才发现。
删除操作
删除比插入复杂一些。因为删除后，不仅要考虑当前节点是否平衡，还要考虑它的祖先节点。
删除的步骤：
- 找到要删除的节点（和 BST 一样）
- 处理三种情况：叶子节点、单子节点、双子节点
- 更新高度并检查平衡
AVLNode* delete(AVLNode *root, int key) {
// 1. 标准 BST 删除
if (root == NULL) return root;
if (key < root->key)
root->left = delete(root->left, key);
else if (key > root->key)
root->right = delete(root->right, key);
else {
// 找到要删除的节点
if ((root->left == NULL) || (root->right == NULL)) {
AVLNode *temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
// 双子节点：找中序后继
AVLNode *temp = minValueNode(root->right);
root->key = temp->key;
root->right = delete(root->right, temp->key);
}
}
if (root == NULL) return root;
// 2. 更新高度并平衡
root->height = 1 + max(height(root->left), height(root->right));
int balance = getBalance(root);
// 旋转判断（和插入类似）
if (balance > 1 && getBalance(root->left) >= 0)
return rotateLL(root);
if (balance > 1 && getBalance(root->left) < 0)
return rotateLR(root);
if (balance < -1 && getBalance(root->right) <= 0)
return rotateRR(root);
if (balance < -1 && getBalance(root->right) > 0)
return rotateRL(root);
return root;
}AVL 树知识体系
下面这张图帮你理清 AVL 树的整体脉络：
AVL 树的优缺点
| 优点 | 缺点 |
|---|---|
| 查找效率稳定 O(log n) | 插入/删除需要频繁旋转 |
| 不会退化成链表 | 需要额外存储高度信息 |
| 适合读多写少的场景 | 实现比红黑树复杂 |
我的建议：如果项目对查找性能要求极高，且插入删除不频繁，选 AVL 树。如果插入删除很频繁，红黑树可能更合适。我在做数据库索引时，就根据这个原则做了选择。
AVL 树的核心就这些。记住一句话：平衡是手段，不是目的。我们做平衡，是为了保证查找效率。别为了平衡而平衡，那会陷入过度设计的陷阱。
公众号:蓝海资料掘金营，微信deep3321