AVL树4种失衡场景（LL/RR/LR/RL）旋转决策树：1张图解决所有插入/删除调整
在数据结构与算法的世界里，AVL树就像一位始终保持优雅姿态的舞者，即使经历频繁的数据插入删除，也能通过巧妙的旋转保持完美平衡。本文将为你揭示AVL树维持平衡的核心机制——四种旋转场景的判断逻辑与操作流程，并附上可直接用于实战的决策流程图。
1. AVL树平衡原理精要
AVL树得名于其发明者Adelson-Velsky和Landis，是最早的自平衡二叉搜索树。它的核心特性在于：任何节点的左右子树高度差绝对值不超过1。这个高度差我们称之为平衡因子（Balance Factor）：
平衡因子 = 右子树高度 - 左子树高度当插入或删除节点导致平衡因子超出[-1,1]范围时，AVL树会通过四种基本旋转操作恢复平衡。理解这些旋转的关键在于把握三个要点：
- 失衡节点：从新插入/删除的节点向上查找，第一个平衡因子异常的节点
- 失衡方向：确定是左子树过高（平衡因子<-1）还是右子树过高（平衡因子>1）
- 孙节点状态：检查失衡节点的子节点的平衡因子，判断属于哪种旋转类型
2. 四种旋转场景全解析
2.1 LL型失衡与右旋
特征识别：
- 失衡节点平衡因子 = -2
- 左子节点平衡因子 = -1 或 0
操作步骤：
- 以失衡节点的左孩子为支点进行右旋
- 原左孩子的右子树变为失衡节点的左子树
- 失衡节点成为新父节点的右孩子
// 右旋代码示例 Node* rightRotate(Node* y) { Node* x = y->left; y->left = x->right; x->right = y; // 更新高度 y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), y->height) + 1; return x; // 返回新的根节点 }2.2 RR型失衡与左旋
特征识别：
- 失衡节点平衡因子 = +2
- 右子节点平衡因子 = +1 或 0
操作步骤：
- 以失衡节点的右孩子为支点进行左旋
- 原右孩子的左子树变为失衡节点的右子树
- 失衡节点成为新父节点的左孩子
// 左旋代码示例 Node* leftRotate(Node* x) { Node* y = x->right; x->right = y->left; y->left = x; // 更新高度 x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->right), x->height) + 1; return y; // 返回新的根节点 }2.3 LR型失衡与左右双旋
特征识别：
- 失衡节点平衡因子 = -2
- 左子节点平衡因子 = +1
复合操作：
- 先对失衡节点的左孩子执行左旋（转为LL型）
- 再对失衡节点执行右旋
// 左右双旋代码示例 Node* leftRightRotate(Node* z) { z->left = leftRotate(z->left); // 先左旋 return rightRotate(z); // 再右旋 }2.4 RL型失衡与右左双旋
特征识别：
- 失衡节点平衡因子 = +2
- 右子节点平衡因子 = -1
复合操作：
- 先对失衡节点的右孩子执行右旋（转为RR型）
- 再对失衡节点执行左旋
// 右左双旋代码示例 Node* rightLeftRotate(Node* z) { z->right = rightRotate(z->right); // 先右旋 return leftRotate(z); // 再左旋 }3. 旋转决策流程图解
以下决策树涵盖了插入和删除操作中的所有失衡情况判断逻辑：
开始 → 检查当前节点平衡因子 ├── 平衡因子 > 1（右子树高） │ ├── 右子节点平衡因子 ≥ 0 → 执行左旋（RR型） │ └── 右子节点平衡因子 < 0 → 执行右左双旋（RL型） └── 平衡因子 < -1（左子树高） ├── 左子节点平衡因子 ≤ 0 → 执行右旋（LL型） └── 左子节点平衡因子 > 0 → 执行左右双旋（LR型）关键提示：删除操作后可能需要从删除点向上多次旋转，直到根节点
4. 平衡因子更新规则
旋转操作后必须正确更新相关节点的高度和平衡因子：
| 旋转类型 | 新根节点平衡因子 | 原根节点平衡因子 | 其他节点影响 |
|---|---|---|---|
| LL右旋 | 0 | 0 | 无 |
| RR左旋 | 0 | 0 | 无 |
| LR双旋 | 0 | 根据子节点调整 | 需检查孙节点状态 |
| RL双旋 | 0 | 根据子节点调整 | 需检查孙节点状态 |
5. 实战案例演示
假设我们依次插入序列：50, 30, 80, 20, 40, 35：
- 插入35后，50节点失衡（BF=-2）
- 左子节点30的BF=+1 → LR型
- 先对30左旋，再对50右旋
# 插入35后的树结构 50(-2) / 30(1) / \ 20 40 / 35 # 执行左右双旋后 40(0) / \ 30(0) 50(0) / \ 20 356. 删除操作的特殊处理
删除节点后的平衡调整需要特别注意：
- 当删除导致节点平衡因子为±2时
- 需要检查较高子树根节点的平衡因子
- 若为0，执行单旋转
- 若与父节点同号，执行单旋转
- 若与父节点异号，执行双旋转
- 即使当前节点恢复平衡，仍需继续向上检查直到根节点
7. 完整实现要点
在代码实现时，建议采用递归回溯方式更新高度并检查平衡：
// 插入节点后的平衡检查伪代码 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 + max(height(node->left), height(node->right)); // 检查平衡因子 int balance = getBalance(node); // 四种失衡情况处理 if (balance > 1 && key > node->right->key) return leftRotate(node); // RR if (balance < -1 && key < node->left->key) return rightRotate(node); // LL if (balance > 1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); // RL } if (balance < -1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); // LR } return node; }掌握这套决策逻辑后，无论是面试中的手写代码环节，还是实际工程中的性能优化，你都能从容应对AVL树的平衡调整问题。记住，旋转操作的本质是通过局部子树重组，在保持二叉搜索树性质的前提下，将树高差异控制在1以内。
