【数据结构】平衡二叉树
一、平衡二叉树 完整定义
平衡二叉树，简称 AVL 树，是改良版二叉排序树满足两个硬性条件：
具备二叉排序树性质
左子树所有结点值 ＜ 根 ＜ 右子树所有结点值
具备平衡性质
任意结点的左、右子树高度差的绝对值 ≤ 1
左右子树，也必须是平衡二叉树
二、核心概念：平衡因子
公式（死记，不能写反）
平衡因左子树高度右子树高度
合法范围
BF∈{−1, 0, 1}
BF=1：左子树更高（左偏）
BF=0：左右等高（完全平衡）
BF=−1：右子树更高（右偏）
∣BF∣≥2：树失衡，必须旋转调整
三、为什么需要 AVL 树
普通二叉排序树 BST
有序序列插入会变成斜树，查找复杂度退化到 O(n)
AVL 树强制平衡
始终控制树高为 O(log 2 n)
查找、插入、删除稳定高效
四、四大失衡类型 + 完整旋转操作
插入新结点后，从下往上找第一个失衡结点，以该结点为根调整
1. LL 型 左左失衡
成因：在左子树的左子树插入结点
失衡特征：根结点 BF=2，
左孩子 BF=1
调整方式：单次右旋转
原理：
左孩子上位，原根下沉为右孩子，左孩子的右子树过继给原根左子树
2. RR 型 右右失衡
成因：在右子树的右子树插入结点
失衡特征：根结点 BF=−2，
右孩子 BF=−1
调整方式：单次左旋转
原理：
右孩子上位，原根下沉为左孩子，右孩子的左子树过继给原根右子树
3. LR 型 左右失衡
成因：在左子树的右子树插入结点
失衡特征：根 BF=2，
左孩子 BF=−1
调整方式：两次旋转
① 先对左子树 左旋 → 转为 LL 型
② 再对根结点 右旋
4. RL 型 右左失衡
成因：在右子树的左子树插入结点
失衡特征：根
BF=−2，右孩子
BF=1
调整方式：两次旋转
① 先对右子树 右旋 → 转为 RR 型
② 再对根结点 左旋
极简口诀
同侧单旋，异侧双旋LL 右，RR 左LR 先左后右，RL 先右后左
五、插入与删除的区别
插入操作
只会导致一处失衡，最多两次旋转即可全局平衡，向上回溯只走一层
删除操作
会导致祖先链连续失衡，需要逐层向上回溯、多次旋转，调整次数更多
六、高度与时间复杂度
设总结点数 n
AVL 树最大高度：h≈1.44log 2 n
查找、插入、删除时间复杂度：稳定 O(log 2 n)
对比 BST
BST：最好 O(logn)，最坏 O(n)
AVL：无最坏退化，严格平衡
七、超级重要 易错注意点
旋转绝对不能破坏二叉排序树规则
所有旋转后，仍必须满足：左 < 根 < 右
平衡因子计算严禁写反
只能：左高 − 右高，写反整题全错
找失衡结点顺序：从插入结点向上找第一个
∣BF∣≥2的结点
平衡二叉树树形不唯一，平衡方案不唯一，但平衡规则固定
AVL 树是高度平衡，不是完全二叉树、不是满二叉树
平衡因子需要每次旋转后重新更新