平衡二叉树（AVL）

2026 大纲 六（五）2 平衡二叉树。编排在"树与二叉树"目录下只是为了连贯阅读，做题定位请按六（五）2；BST 的查找 / 插入 / 删除与 ASL 见《BST》，红黑树对比见《红黑树》。

AVL 要修的是 BST 的什么病

BST 的效率完全写在树高里：树高 $O(\log n)$ 时查找飞快，退化成单支链时和顺序查找一样慢。

麻烦在于退化的触发条件一点也不苛刻——按 $1,2,3,4,5$ 的顺序插入就够了，而"有序输入"在实际数据里太常见。

AVL 的解法很直接：每次插入或删除后检查平衡，一旦某个结点的左右子树高度差超过 1，就通过"旋转"把它掰回来。 代价是每个结点多存一个高度（或平衡因子）。

平衡二叉树（AVL 树，得名于提出者 Adelson-Velskii 和 Landis）或者是空树，或者是具有如下特征的二叉排序树：左右子树的深度之差的绝对值不超过 1，且左右子树也是平衡二叉树。

注意定义里"二叉排序树"这五个字。平衡只是附加约束，"左小右大"一刻也不能破。 后面每做完一次旋转都要查两件事：所有结点的平衡因子合法，以及中序序列仍然递增。后者很多人忘记查——接错指针时平衡因子可能还合法，但树已经不是 BST 了。

平衡因子与最小不平衡子树

平衡因子 $BF(T)=\mathrm{Height}(T\to lchild)-\mathrm{Height}(T\to rchild)$。AVL 中它只能是 $-1$、$0$、$+1$；只要有一个结点的 $|BF|>1$，这棵树就不是 AVL。

typedef struct AVLNode {
    int data;
    int height;              // 以该结点为根的子树的高度（空树记 0，叶结点记 1）
    struct AVLNode *lchild, *rchild;
} AVLNode, *AVLTree;

int GetHeight(AVLNode *T) {
    if (T == NULL) return 0;      // 空树高度约定为 0
    return T->height;
}

int GetBF(AVLNode *T) {
    return GetHeight(T->lchild) - GetHeight(T->rchild);
}

实现上存高度还是存平衡因子：两种都行。存高度的好处是旋转后只需按 max(左,右)+1 重算，不易出错；存平衡因子省一点空间但更新规则更绕。本篇代码存高度，做题时画图标的通常是平衡因子，两者可随时互算。

最小不平衡子树：插入或删除后从操作位置沿路径向上回溯，遇到的第一个 $|BF|>1$ 的结点，以它为根的子树就是最小不平衡子树，记作 $A$。

旋转只在 $A$ 上做。 把这棵子树掰平之后，它的高度会恢复（插入）或减少 1（删除），上层看到的只是一棵子树的高度变化，不需要重新推导整棵树。

先看一眼

加载可视化中...

四种旋转：判别只看两个符号

$BF(A)$	$BF(B)$	类型	怎么转	转完谁是新根
$+2$ 左高	$+1$	LL	对 $A$ 右单旋	$B$（$A$ 的左孩子）
$+2$ 左高	$-1$	LR	先对 $B$ 左旋，再对 $A$ 右旋	$C$（$B$ 的右孩子）
$-2$ 右高	$-1$	RR	对 $A$ 左单旋	$B$（$A$ 的右孩子）
$-2$ 右高	$+1$	RL	先对 $B$ 右旋，再对 $A$ 左旋	$C$（$B$ 的左孩子）
$+2$ / $-2$	$0$	LL / RR	按单旋处理	$B$

一句话判据：$BF(A)$ 与 $BF(B)$ 同号（或 $BF(B)=0$）用单旋，异号用双旋。

名字怎么读：两个字母表示"从 $A$ 出发往哪个方向走两步能到那棵最高的子树"——LL $=$ 左孩子的左子树最高，LR $=$ 左孩子的右子树最高。第一个字母决定最终对 $A$ 转哪个方向（L → 右旋、R → 左旋）；两个字母不同就先对 $B$ 反向转一次，把"折线"掰成"直线"。

前四行插入删除都会出现；末行只在删除时出现——插入使某侧高度 $+1$，$B$ 必然向一侧偏，不可能为 0。这一行还有个特殊之处：旋转后子树高度不变，下面会用到。

// LL：对 A 做右单旋，返回新的子树根
AVLNode* LL_Rotate(AVLNode *A) {
    AVLNode *B = A->lchild;
    A->lchild = B->rchild;   // B 的右子树改挂到 A 的左边（保持 BST 的大小次序）
    B->rchild = A;           // A 成为 B 的右孩子
    // 高度必须先更新 A、再更新 B —— 因为 B 的高度依赖 A 的新高度
    A->height = max(GetHeight(A->lchild), GetHeight(A->rchild)) + 1;
    B->height = max(GetHeight(B->lchild), GetHeight(B->rchild)) + 1;
    return B;                // B 成为新的子树根
}

// RR：对 A 做左单旋，与 LL 完全对称
AVLNode* RR_Rotate(AVLNode *A) {
    AVLNode *B = A->rchild;
    A->rchild = B->lchild;
    B->lchild = A;
    A->height = max(GetHeight(A->lchild), GetHeight(A->rchild)) + 1;
    B->height = max(GetHeight(B->lchild), GetHeight(B->rchild)) + 1;
    return B;
}

// 双旋 = 两次单旋的复合（函数名按失衡类型命名，动作按左旋/右旋读）
AVLNode* LR_Rotate(AVLNode *A) { A->lchild = RR_Rotate(A->lchild); return LL_Rotate(A); }
AVLNode* RL_Rotate(AVLNode *A) { A->rchild = LL_Rotate(A->rchild); return RR_Rotate(A); }

LL 型：对 $A$ 右单旋。 成因是 $A$ 的左孩子 $B$ 的左子树变高。把 $B$ 提升为新根，$A$ 变为 $B$ 的右孩子，$B$ 原来的右子树 $B_R$ 改挂到 $A$ 的左边。

      A (BF=+2)                      B (BF=0)
     /      \                      /      \
    B(+1)    A_R      ──右旋──→   B_L      A (BF=0)
   /   \       h                  h+1     /    \
 B_L    B_R                             B_R    A_R
 h+1     h                               h      h

为什么 $B_R$ 要挂到 $A$ 的左边：BST 性质要求 $B_L<B<B_R<A<A_R$。旋转后 $A$ 成了 $B$ 的右孩子，$A$ 的左子树必须装"比 $B$ 大、比 $A$ 小"的那一段——正是 $B_R$。每一次旋转都用这条不等式链自检，这是保证旋转不破坏 BST 的唯一办法。

高度上：旋转前 $A$ 高 $h+3$；旋转后 $A$ 的两棵子树都高 $h$（$BF(A)=0$），$B$ 的两棵子树都高 $h+1$（$BF(B)=0$），整棵子树高度从 $h+3$ 降回 $h+2$。

RR 型对称，不再重复。

LR 型：先对 $B$ 左旋，再对 $A$ 右旋。 成因是 $A$ 的左孩子 $B$ 的右子树变高（$BF(A)=+2$、$BF(B)=-1$），设 $C=B$ 的右孩子。

单旋为什么不行：若直接对 $A$ 右旋，$B$ 的右子树（最高的那棵）会原封不动挂到 $A$ 的左边，$A$ 这一侧还是太高。必须先把折线 $A\to B\to C$ 掰成直线。

       A (+2)                A                        C
      /    \               /   \                   /     \
    B(−1)   A_R           C     A_R              B         A
   /   \      ──先对 B 左旋──→  / \    ──再对 A 右旋──→  / \       / \
 B_L    C                B    C_R                 B_L  C_L   C_R  A_R
        / \             / \
      C_L  C_R        B_L  C_L

RL 型对称（$C=B$ 的左孩子，先对 $B$ 右旋再对 $A$ 左旋）。

单旋代码里高度更新的次序不能颠倒：旋转后 $A$ 是 $B$ 的孩子，$B$ 的高度由 $A$ 的新高度算出，先更新 $B$ 会用到旧值。这是 AVL 代码最容易写错的一行。

双旋之后三个结点的平衡因子（画图题要标 BF 时展开）

旋转后的平衡因子取决于旋转前的 $BF(C)$，这是很多人漏掉的一层。LR 型：

旋转前 $BF(C)$	含义	旋转后 $BF(B)$	旋转后 $BF(A)$	旋转后 $BF(C)$
$+1$	新结点插在 $C_L$ 中	$0$	$-1$	$0$
$-1$	新结点插在 $C_R$ 中	$+1$	$0$	$0$
$0$	$C$ 自己就是新插入的结点	$0$	$0$	$0$

推导（以 $BF(C)=+1$ 为例）：设 $B_L$ 高 $h$，则 $C$ 高 $h+1$、$B$ 高 $h+2$、$A_R$ 高 $h$；$BF(C)=+1$ 意味着 $C_L$ 高 $h$、$C_R$ 高 $h-1$。旋转后 $B$ 带 $(B_L=h,C_L=h)$ → 高 $h+1$、$BF=0$；$A$ 带 $(C_R=h-1,A_R=h)$ → 高 $h+1$、$BF=-1$；$C$ 带两棵高 $h+1$ 的子树 → 高 $h+2$、$BF=0$。整棵子树高度从 $h+3$ 降回 $h+2$ ✓

RL 型的规律与之镜像：旋转前 $BF(C)=+1$ 时旋转后 $BF(A)=0$、$BF(B)=-1$；$BF(C)=-1$ 时 $BF(A)=+1$、$BF(B)=0$。

插入与删除：旋转次数不一样

两者都是两步：先按 BST 规则插入 / 删除，再沿递归返回的路径逐层更新高度、检查平衡，失衡就按上表旋转。区别只有一条，但很关键：

• 插入：至多旋转一次。 旋转把子树高度恢复到了插入之前——$A$ 的双亲看到"高度没变"，平衡因子也就没变，再往上全部不受影响。
• 删除：可能一路旋转到根。 除 $BF(B)=0$ 那一种外，旋转都会让子树再矮 1，双亲那层可能新出现失衡。最坏 $O(\log n)$ 次旋转。

一句话对比：插入的旋转是"止损"（把多出来的 1 层消掉），删除的旋转是"传染"（自己平了，却把矮了 1 层的问题交给了双亲）。

还有一个容易踩的差别："看新关键字落在哪一侧"这个判别法只对插入有效。 插入时失衡一定是刚插入的那个结点造成的，"它落在 $A$ 的哪一侧的哪一侧"唯一决定了类型；删除没有插入位置，必须回到"看 $BF(A)$ 与 $BF(B)$ 的符号"。

插入与删除的完整代码，与"删除后子树高度怎么变"的分情形推导（要默写代码时展开）

AVLNode* Insert(AVLNode *T, int x) {
    if (T == NULL) {                          // 找到插入位置：新结点必是叶子
        T = (AVLNode*)malloc(sizeof(AVLNode));
        T->data = x; T->height = 1;
        T->lchild = T->rchild = NULL;
        return T;
    }
    if (x < T->data)      T->lchild = Insert(T->lchild, x);
    else if (x > T->data) T->rchild = Insert(T->rchild, x);
    else                  return T;           // 关键字已存在，不插入

    T->height = max(GetHeight(T->lchild), GetHeight(T->rchild)) + 1;   // 回溯时更新高度

    int bf = GetBF(T);
    // 插入时可以用"新关键字落在哪一侧"来判别旋转类型
    if (bf >  1 && x < T->lchild->data)  return LL_Rotate(T);
    if (bf >  1 && x > T->lchild->data)  return LR_Rotate(T);
    if (bf < -1 && x > T->rchild->data)  return RR_Rotate(T);
    if (bf < -1 && x < T->rchild->data)  return RL_Rotate(T);
    return T;
}

AVLNode* Delete(AVLNode *T, int x) {
    if (T == NULL) return NULL;
    if (x < T->data)      T->lchild = Delete(T->lchild, x);
    else if (x > T->data) T->rchild = Delete(T->rchild, x);
    else {
        if (T->lchild && T->rchild) {
            AVLNode *pre = T->lchild;                   // 用中序前驱替代
            while (pre->rchild) pre = pre->rchild;
            T->data = pre->data;
            T->lchild = Delete(T->lchild, pre->data);
        } else {
            AVLNode *child = T->lchild ? T->lchild : T->rchild;
            free(T);
            return child;
        }
    }

    T->height = max(GetHeight(T->lchild), GetHeight(T->rchild)) + 1;

    int bf = GetBF(T);
    // 删除时必须用"较高孩子的平衡因子"判别，不能用"插入位置"
    if (bf >  1 && GetBF(T->lchild) >= 0)  return LL_Rotate(T);   // 同号或为 0 → 单旋
    if (bf >  1 && GetBF(T->lchild) <  0)  return LR_Rotate(T);   // 异号 → 双旋
    if (bf < -1 && GetBF(T->rchild) <= 0)  return RR_Rotate(T);
    if (bf < -1 && GetBF(T->rchild) >  0)  return RL_Rotate(T);
    return T;
}

删除后子树高度怎么变（以 $BF(A)=+2$ 为例）：

$BF(B)$	旋转后	子树高度	上层是否可能继续失衡
$+1$（与 $A$ 同号）	LL 单旋，$BF(A)=BF(B)=0$	比失衡前少 1	可能，要继续回溯
$-1$（异号）	LR 双旋	比失衡前少 1	可能，要继续回溯
$0$（只在删除时出现）	LL 单旋，$BF(B)=-1$、$BF(A)=+1$	不变	不会，调整到此结束

推导第三行：设 $B_L$、$B_R$ 均高 $h+1$（故 $BF(B)=0$），$B$ 高 $h+2$；$BF(A)=+2$ → $A_R$ 高 $h$，$A$ 高 $h+3$。右单旋后：$A$ 带 $(B_R=h+1,A_R=h)$ → 高 $h+2$、$BF(A)=+1$；$B$ 带 $(B_L=h+1,A=h+2)$ → 高 $h+3$、$BF(B)=-1$。子树高度仍是 $h+3$，未变 ✓

删除的旋转次数虽是 $O(\log n)$，但总时间仍是 $O(\log n)$——回溯路径本身就只有 $O(\log n)$ 层，每层至多一次旋转、每次 $O(1)$。

按 (13, 24, 37, 90, 53) 建 AVL 树的逐步演示（第一次学、想跟着走一遍时展开）

插入 13            插入 24              插入 37 → 13 的 BF 变为 −2
  13                13(−1)                 13(−2)                  24(0)
                      \                      \                    /    \
                       24                     24(−1)   ──RR──→  13(0)  37(0)
                                                \
                                                 37

插入 90                                  插入 53 → 37 的 BF 变为 −2
   24(−1)                                   24(−1)                        24(−1)
  /    \                                   /     \                       /     \
13(0)   37(−1)                          13(0)    37(−2)   ──RL──→     13(0)    53(0)
          \                                        \                          /    \
           90(0)                                    90(+1)                 37(0)  90(0)
                                                    /
                                                  53(0)

1. 插入 13、24 后仍平衡（$BF(13)=-1$）
2. 插入 37 后 $BF(13)=-2$、$BF(24)=-1$，同号 → RR 型，对 13 做左单旋，新根为 24
3. 插入 90 后 $BF(37)=-1$、$BF(24)=-1$，仍在允许范围内，不调整
4. 插入 53 时 53 落到 90 的左边。回溯：$BF(90)=+1$（左高）、$BF(37)=-2$（右高），异号 → RL 型：先对 90 右旋，再对 37 左旋

最终自检：所有结点 $|BF|\le 1$ ✓，中序序列 $13,24,37,53,90$ 递增 ✓

最少结点数：AVL 计数题的唯一公式

设 $N_h$ 为高度为 $h$ 的 AVL 树最少含有的结点数。要让结点尽可能少，两棵子树都要尽可能"空"；但根的 $|BF|\le 1$，而其中一棵子树的高度必须是 $h-1$（否则整树高不到 $h$），所以另一棵最矮只能是 $h-2$，且两棵子树本身也要是"同高度下最少结点"的 AVL 树。于是

$$\boxed{{\displaystyle N_h=N_{h-1}+N_{h-2}+1}},N_0=0,N_1=1$$

$h$	1	2	3	4	5	6	7	8	9	10
$N_h$	1	2	4	7	12	20	33	54	88	143

这个递推还有个等价说法：所有非叶结点的平衡因子都是 1（或都是 $-1$）的 AVL 树，就是同高度下结点最少的那棵，称为斐波那契树。题目里出现"所有非叶结点平衡因子均为 1"这句话，就是在说这件事，直接查表即可。

与斐波那契数列的关系：把递推式两边同时加 1 得 $(N_h+1)=(N_{h-1}+1)+(N_{h-2}+1)$——加 1 之后就是标准的斐波那契递推。对照 $F$ 数列可验证 $N_h=F_{h+2}-1$（$h=6$ 时 $F_8-1=21-1=20$ ✓）。

由此得到树高上界：因为 $F_k\approx {\phi }^k/\sqrt{5}$（$\phi \approx 1.618$），有 $n\ge N_h=F_{h+2}-1$，两边取对数整理得

$$h<1.44{\log }_2(n+2)$$

最多比理想的 ${\log }_2(n+1)$ 高约 44%——这就是 AVL"与输入次序无关的 $O(\log n)$"的全部来源。

这条递推配上"最多结点数"，能回答四类问题：

问法	做法
高度为 $h$ 的 AVL 树最少多少个结点	查 $N_h$ 表
高度为 $h$ 的 AVL 树最多多少个结点	满二叉树，$2^h-1$
$n$ 个结点的 AVL 树最大高度	找最大的 $h$ 使 $N_h\le n$。$n=20$ 时 $N_6=20\le 20<N_7=33$，故最大高度 6
$n$ 个结点的 AVL 树最小高度	完全二叉树，$\lceil {\log }_2(n+1)\rceil$

注意 $N_h$ 里的 $h$ 是高度、不是结点数。 "高度为 6 的 AVL 树最少有几个结点"答 20；"20 个结点的 AVL 树最大高度是几"答 6。两个问题互为反问，别把表反着查。

考点速记

三条会被反复调用的结论：

1. 旋转类型只看两个平衡因子的符号：同号（或 $BF(B)=0$）单旋、异号双旋——这条判据插入删除通用，"看插入位置"只对插入有效。
2. 插入至多旋转一次、删除可能 $O(\log n)$ 次，根因是两者旋转后子树高度的变化方向不同。
3. $N_h=N_{h-1}+N_{h-2}+1$ 给出 $h<1.44{\log }_2(n+2)$，AVL 计数题基本都从这条递推出发。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）。三大类：

① 插入一个关键字，问新树的某个局部。 问法有"插入后根中的关键字是什么""某个关键字的左右孩子分别是谁"。做法固定三步：按 BST 规则找到插入位置 → 向上回溯找第一个 $|BF|>1$ 的结点 $A$ → 看 $BF(A)$ 与 $BF(B)$ 的符号定类型、旋转。旋转完把整棵树重画一遍再读答案，别只在脑子里挪。

② 计数题，全部走 $N_h$ 递推。 三种问法：

• "平衡二叉树高度为 6，且所有非叶结点的平衡因子均为 1，结点总数是多少"——这是斐波那契树，$N_6=20$。
• "AVL 树高度为 4，根的左右子树结点数之差最多是多少"——让一棵尽量胖、一棵尽量瘦：胖的高 3、最多 $2^3-1=7$ 个；瘦的高 2、最少 $N_2=2$ 个；差 5。注意两棵子树的高度差不能超过 1，所以不能取"高 3 和高 1"。
• "把 $1,2,\dots ,7$ 依次插入空 AVL 树，平衡因子为 0 的分支结点有几个"——老老实实逐个插入并旋转，最后得到的是一棵满二叉树 $4(2(1,3),6(5,7))$，分支结点 4、2、6 的 $BF$ 都是 0，答 3。

③ 判断与对照题。 "下列哪棵满足平衡二叉树定义"——逐棵算每个结点的 $BF$。"删除某结点再插回去，$T_1$ 与 $T_3$ 是否相同"——与 BST 那一题同一个套路，但 AVL 多了旋转这层，即使删的是叶结点，若删除触发了旋转，插回去也未必复原，所以措辞是"可能不相同"。

易错：删除时用"插入位置"判旋转类型。 删除没有插入位置，只能看两个 $BF$ 的符号。

易错：把 $N_h$ 表反着查。 $h$ 是高度不是结点数。

易错：求"左右子树结点数之差最多"时让两棵子树高度差超过 1。 AVL 的定义先要满足。

易错：旋转后忘了检查中序序列。 接错指针时 $BF$ 可能仍合法，但树已不是 BST。

易错：单旋代码里先更新 $B$ 的高度。 必须先 $A$ 后 $B$。

教材出处

• 平衡二叉树的定义（"或者是空树，或者是具有如下特征的二叉排序树：左子树和右子树的深度之差的绝对值不超过 1；左子树和右子树也是平衡二叉树"）、平衡因子的定义、"平衡二叉树上所有结点的平衡因子只可能是 $-1$、$0$ 和 $1$。只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的"，以及引入 AVL 的动机（"如果数据呈有序排列，则二叉排序树是线性的，查找的时间复杂度为 $O(n)$"）：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p205（7.3.2 节）
• "因为 AVL 树上任何结点的左右子树的深度之差都不超过 1，则可以证明它的深度和 ${\log }_{2}n$ 是同数量级的"；平衡调整方法（"找到离插入结点最近且平衡因子绝对值超过 1 的祖先结点，以该结点为根的子树称为最小不平衡子树"）；以及关键字序列 $(13,24,37,90,53)$ 的建树全过程：印刷 p206
• 四种失衡类型的归纳与调整示意图：LL 型与 RR 型的旋转说明：印刷 p207
• 平衡二叉树插入的递归算法描述，含按"BBST 的左子树根结点的平衡因子"分情形处理（为 1 则单向右旋、为 $-1$ 则先左后右双旋）：印刷 p210

说明：$N_h=N_{h-1}+N_{h-2}+1$ 的递推、它与斐波那契数列的关系、$h<1.44{\log }_2(n+2)$ 的上界，以及双旋后平衡因子随 $BF(C)$ 变化的三行表，在严蔚敏这本教材中没有直接对应的段落，故不标页码；本篇给出的是完整推导过程。

相关知识

二叉排序树（BST）（AVL 的插入删除以它为第一步）｜红黑树（弱平衡方案，那篇有与 AVL 的完整对比）｜折半查找｜B 树（"最少关键字数"与 $N_h$ 同源）｜查找算法的分析与应用｜树与二叉树基本概念

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历
• 由遍历序列构造二叉树
• 线索二叉树
• 二叉排序树（BST）
• 红黑树
• 哈夫曼树
• 堆（大根堆/小根堆）
• 并查集
• 树与森林
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习

相关真题（9题）

2026Q82分2021Q62分2019Q42分2017Q82分2015Q42分2013Q32分2012Q42分2010Q42分2009Q42分