数据结构——AVL二叉平衡树-开发者社区

AVL 树是史上第一种自平衡二叉搜索树，也是数据结构面试的重中之重。它在普通二叉搜索树（BST）的基础上解决了退化成链表、查询效率暴跌的致命问题。

很多同学只会背概念，但不懂四种旋转机制、平衡因子、失衡修复、插入删除逻辑。本文带你彻底吃透 AVL 底层原理、平衡逻辑、全部旋转场景、完整代码实现以及优缺点对比，看完彻底搞定平衡树。

一、为什么需要 AVL 树？（BST 的致命缺陷）

1.1 回顾二叉搜索树 BST 特性

二叉搜索树规则：

左子树所有节点值 < 根节点
右子树所有节点值 > 根节点
左右子树同样满足上述规则

理想 BST：左右均衡，树高 logN，查找效率 O(logN)

1.2 BST 最大痛点：不平衡

如果插入数据是有序递增/有序递减，BST 会直接退化成单链树：

1→2→3→4→5→6 全部右斜，树高等于节点数 N，查找效率直接退化到 O(N)，和链表没有区别。

AVL 树的诞生目的：强制让二叉树保持平衡，杜绝链表退化，保证查询效率稳定 O(logN)。

二、AVL 树核心定义与核心概念

2.1 AVL 树定义

AVL 树是高度平衡的二叉搜索树，满足两个条件：

首先是一棵合法二叉搜索树（满足大小规则）
任意节点的左右子树高度差绝对值不超过 1

2.2 核心关键词：平衡因子（Balance Factor）

AVL 树判断平衡的唯一标准：平衡因子 BF

平衡因子 = 左子树高度 - 右子树高度

AVL 合法平衡范围：BF ∈ {-1, 0, 1}

BF = 0：左右等高，完全平衡
BF = 1：左子树更高，左偏
BF = -1：右子树更高，右偏
BF = 2 / -2：树失衡，必须旋转修复

2.3 AVL 核心优势

无论怎么插入、删除节点，树高永远维持 logN，查找、插入、删除时间复杂度稳定 O(logN)，不会退化。

三、AVL 四大失衡场景与旋转修复（核心难点）

AVL 所有失衡，只会出现四种情况，对应四种旋转操作，是全文最重要的部分。

失衡判定：最近失衡节点的左右子树高度差超过1。

3.1 LL 型失衡 —— 右旋修复

场景：左子树的左子树插入节点，导致左子树过高（左左失衡）

特征：父节点 BF=2，左孩子 BF=1

修复方式：单次右旋

旋转逻辑：

将失衡节点的左孩子顶替自己成为新根
将左孩子的原有右子树，挂载到失衡节点的左孩子位置
更新高度、平衡因子，恢复平衡

3.2 RR 型失衡 —— 左旋修复

场景：右子树的右子树插入节点，导致右子树过高（右右失衡）

特征：父节点 BF=-2，右孩子 BF=-1

修复方式：单次左旋

和右旋完全对称，是最简单的两种旋转。

3.3 LR 型失衡 —— 先左旋、后右旋

场景：左子树的右子树插入节点，左子树偏高但右侧重（左右失衡）

特征：父节点 BF=2，左孩子 BF=-1

修复方式：双旋转

先对左孩子左旋，转换成 LL 形态
再对失衡根节点右旋，恢复平衡

3.4 RL 型失衡 —— 先右旋、后左旋

场景：右子树的左子树插入节点，右子树偏高但左侧重（右左失衡）

特征：父节点 BF=-2，右孩子 BF=1

修复方式：双旋转

先对右孩子右旋，转换成 RR 形态
再对失衡根节点左旋，恢复平衡

旋转口诀（直接背）

LL 右旋
RR 左旋
LR 先左后右
RL 先右后左

四、AVL 插入完整流程

AVL 插入不是单纯插节点，是插入+回溯更新高度+检测失衡+旋转修复的完整闭环。

按照 BST 规则找到空位，插入新节点
递归回溯更新所有祖先节点的树高
计算每个祖先的平衡因子，判断是否失衡
判定 LL / RR / LR / RL 四种场景
执行对应旋转，修复平衡
整棵树重新恢复 AVL 平衡特性

核心特点：插入最多旋转 2 次即可恢复整树平衡，效率极高。

五、AVL 删除难点（面试高阶考点）

AVL插入简单、删除麻烦。

插入只会影响一条路径的祖先，最多两次旋转；

删除节点可能导致上层连续失衡，需要向上一直回溯旋转，直到根节点。

删除流程：

BST 标准删除（度0/度1/度2节点）
自下而上更新高度、计算平衡因子
遇到失衡节点执行对应旋转
继续向上回溯，直到根节点平衡

因此 AVL 删除比插入慢很多，这也是后来红黑树取代 AVL 的核心原因。

六、AVL 完整 C++ 可运行代码（含四种旋转）

#include <iostream> #include <algorithm> using namespace std; // AVL树节点 struct AVLNode { int val; int height; AVLNode* left; AVLNode* right; AVLNode(int v) : val(v), height(1), left(nullptr), right(nullptr) {} }; class AVLTree { public: // 获取节点高度 int getHeight(AVLNode* node) { return node ? node->height : 0; } // 获取平衡因子 int getBF(AVLNode* node) { return node ? getHeight(node->left) - getHeight(node->right) : 0; } // 更新节点高度 void updateHeight(AVLNode* node) { if(node) node->height = 1 + max(getHeight(node->left), getHeight(node->right)); } // 右旋 - LL AVLNode* rightRotate(AVLNode* y) { AVLNode* x = y->left; AVLNode* T3 = x->right; // 旋转 x->right = y; y->left = T3; // 更新高度（先下后上） updateHeight(y); updateHeight(x); return x; } // 左旋 - RR AVLNode* leftRotate(AVLNode* y) { AVLNode* x = y->right; AVLNode* T2 = x->left; x->left = y; y->right = T2; updateHeight(y); updateHeight(x); return x; } // 插入节点 + 自平衡 AVLNode* insert(AVLNode* root, int val) { // 1. 标准BST插入 if(!root) return new AVLNode(val); if(val < root->val) root->left = insert(root->left, val); else if(val > root->val) root->right = insert(root->right, val); else return root; // 重复值不插入 // 2. 更新高度 updateHeight(root); // 3. 计算平衡因子 int bf = getBF(root); // 4. 四种失衡判断 // LL if(bf == 2 && getBF(root->left) == 1) return rightRotate(root); // RR if(bf == -2 && getBF(root->right) == -1) return leftRotate(root); // LR if(bf == 2 && getBF(root->left) == -1) { root->left = leftRotate(root->left); return rightRotate(root); } // RL if(bf == -2 && getBF(root->right) == 1) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } // 中序遍历（有序输出） void inOrder(AVLNode* root) { if(!root) return; inOrder(root->left); cout << root->val << " "; inOrder(root->right); } }; int main() { AVLTree tree; AVLNode* root = nullptr; // 插入测试数据，触发多种旋转 root = tree.insert(root,10); root = tree.insert(root,20); root = tree.insert(root,30); // RR左旋 root = tree.insert(root,5); root = tree.insert(root,8); // LR双旋 cout << "AVL中序遍历结果："; tree.inOrder(root); return 0; }

七、AVL 树优缺点（面试必背）

✅ 优点

高度绝对平衡，树高最低，查询速度最快
查找、插入、删除稳定 O(logN)
相比普通 BST，彻底杜绝链表退化问题

❌ 缺点（致命）

平衡条件过于严格，容错率极低
每次插入、删除极易触发旋转，维护成本高
删除节点可能需要多次回溯旋转，性能损耗大
写操作频繁的场景性能差

八、AVL 树 vs 红黑树（面试终极对比）

很多面试官最爱问：为什么工程中用红黑树不用 AVL 树？

特性	AVL 树	红黑树
平衡严格度	严格平衡（高度差≤1）	弱平衡（最长路径≤2倍最短路径）
查询性能	更快（树更矮）	略慢一点
插入删除性能	差，频繁旋转	优秀，变色多、旋转极少
适用场景	查多写少	读写均衡、写多场景

结论：数据库索引偶尔用 AVL；C++ map/set、Java TreeMap、内核调度器全部用红黑树。

九、全文面试总结（直接背诵）

1. AVL 是高度平衡二叉搜索树，任意节点左右子树高度差不超过1，依靠平衡因子判断平衡。

2. 失衡分为四种：LL(右旋)、RR(左旋)、LR(先左后右)、RL(先右后左)。

3. 插入最多两次旋转即可平衡，删除可能多次回溯旋转，维护成本高。

4. AVL 查询效率极高，但写操作代价大，适合查多写少场景。

5. 相比于红黑树，AVL 平衡过严、旋转过多，工程中读写均衡场景优先红黑树。

数据结构——AVL二叉平衡树