AVL树 4种失衡场景（LL/RR/LR/RL）旋转决策树：1张图解决所有插入/删除调整

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

操作步骤：

1. 以失衡节点的左孩子为支点进行右旋
2. 原左孩子的右子树变为失衡节点的左子树
3. 失衡节点成为新父节点的右孩子

// 右旋代码示例 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

操作步骤：

1. 以失衡节点的右孩子为支点进行左旋
2. 原右孩子的左子树变为失衡节点的右子树
3. 失衡节点成为新父节点的左孩子

// 左旋代码示例 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

复合操作：

1. 先对失衡节点的左孩子执行左旋（转为LL型）
2. 再对失衡节点执行右旋

// 左右双旋代码示例 Node* leftRightRotate(Node* z) { z->left = leftRotate(z->left); // 先左旋 return rightRotate(z); // 再右旋 }

2.4 RL型失衡与右左双旋

特征识别：

• 失衡节点平衡因子 = +2
• 右子节点平衡因子 = -1

复合操作：

1. 先对失衡节点的右孩子执行右旋（转为RR型）
2. 再对失衡节点执行左旋

// 右左双旋代码示例 Node* rightLeftRotate(Node* z) { z->right = rightRotate(z->right); // 先右旋 return leftRotate(z); // 再左旋 }

3. 旋转决策流程图解

以下决策树涵盖了插入和删除操作中的所有失衡情况判断逻辑：

开始 → 检查当前节点平衡因子 ├── 平衡因子 > 1（右子树高） │ ├── 右子节点平衡因子 ≥ 0 → 执行左旋（RR型） │ └── 右子节点平衡因子 < 0 → 执行右左双旋（RL型） └── 平衡因子 < -1（左子树高） ├── 左子节点平衡因子 ≤ 0 → 执行右旋（LL型） └── 左子节点平衡因子 > 0 → 执行左右双旋（LR型）

关键提示：删除操作后可能需要从删除点向上多次旋转，直到根节点

4. 平衡因子更新规则

旋转操作后必须正确更新相关节点的高度和平衡因子：

5. 实战案例演示

假设我们依次插入序列：50, 30, 80, 20, 40, 35：

1. 插入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 35

6. 删除操作的特殊处理

删除节点后的平衡调整需要特别注意：

1. 当删除导致节点平衡因子为±2时
2. 需要检查较高子树根节点的平衡因子
   • 若为0，执行单旋转
   • 若与父节点同号，执行单旋转
   • 若与父节点异号，执行双旋转
3. 即使当前节点恢复平衡，仍需继续向上检查直到根节点

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以内。