平衡二叉树

基本概念

引入：为什么需要平衡

二叉排序树（BST）的查找、插入、删除，代价都正比于树高。一棵形状匀称的 BST，树高约为 \(\log_2 n\)，一切操作都是 \(O(\log n)\)；可一旦插入序列"不巧"（比如基本有序），BST 就会长成一条斜链，树高变成 \(n\)，所有操作退化成 \(O(n)\) —— 跟链表没区别。

更隐蔽的问题是：普通的删除操作本身就会让树"长歪"。我们删除度为 2 的结点时，习惯用右子树的最小结点（直接后继）来顶替，删来删去，右子树越来越矮，整棵树呈现"左高右低"的趋势。久而久之，平衡就被操作本身磨没了。

平衡 BST：如果一棵 BST 无论经过多少次插入、删除，都能自动把树高维持在 \(O(\log n)\)，就称它为平衡 BST。AVL 树是历史上第一种 自平衡二叉查找树（1962 年由 Adelson-Velsky 和 Landis 提出，名字就是两位作者的姓氏缩写）。

AVL 树的核心约定只有一句话：

任意结点的左、右子树高度差（的绝对值）不超过 1。

一旦某个操作打破了这个约定，就通过旋转把树"掰"回来。旋转的妙处在于：它只改几个指针，中序遍历序列完全不变——也就是说 BST 的"左 < 根 < 右"性质毫发无损，但树的形态重新变得匀称。

下面左图是一棵健康的 AVL 树；右图则不是——结点 40 的左子树高 1、右子树高 4，早就"一边倒"了：

所以 AVL 树有两重身份：它既是二叉搜索树，又是平衡二叉树，两个身份的性质它全都满足，因此也常叫"平衡二叉搜索树"。

结点高度 与 平衡因子

结点高度

AVL 的每次操作都要反复问"这棵子树多高"，如果现场递归去算，旋转的代价就控制不住了。所以 AVL 树的结点里多存一个height字段，随操作顺手维护：

// 平衡二叉树结点
typedef struct AVLNode{
    int val;
    int height;                     // 以该结点为根的子树高度
    struct AVLNode left, right;
} AVLNode, AVLTree;

int height(AVLNode node) {
    if (node == NULL) return 0;     // 空树高度规定为 0
    return node->height;            // 直接读字段，O(1) 拿到
}

/ 更新结点高度：最高的那棵子树 + 自己这一层 /
void updateHeight(AVLNode node) {
    node->height = max(height(node->left), height(node->right)) + 1;
}

平衡因子（Balance Factor, bf）

bf = 左子树高度 − 右子树高度（空结点的 bf 规定为 0）。它就是每个结点头顶的"跷跷板读数"：

• bf = 0：左右一样高，最稳；
• bf = ±1：略有倾斜，允许存在；
• bf = ±2（或更极端）：失衡结点，必须处理。

// 获取平衡因子
int balanceFactor(AVLNode node){
    if (node == NULL) return 0;     // 空结点平衡因子为 0
    return height(node->left) - height(node->right);
}

Note

AVL 树的判定：一棵 BST 是 AVL 树 ⟺ 每个结点的 bf 都落在 \({-1, 0, 1}\) 里。

看一棵标注了 bf 的树，顺便手动验算三个结点：

AVL旋转

AVL 树的特点在于 旋转 操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持树的「二叉搜索树」属性，也能使树重新变为「平衡二叉树」。

我们将平衡因子绝对值 >1 的节点称为「失衡节点」。根据节点失衡情况的不同，旋转操作分为四种：右旋、左旋、先右旋后左旋、先左旋后右旋。

LL型，右旋

如下图所示，节点下方为平衡因子。从底至顶看，二叉树中首个失衡节点是“节点 3”。我们关注以该失衡节点为根节点的子树（最小不平衡子树），将该节点记为 node ，其左子节点记为 child ，执行「右旋」操作。完成右旋后，子树已经恢复平衡，并且仍然保持二叉搜索树的特性

---

此外，如果节点 child 本身有右子节点（记为 grandChild ），则需要在「右旋」中添加一步：将 grandChild 作为 node 的左子节点。

---

“向右旋转”是一种形象化的说法，实际上需要通过修改节点指针来实现，代码如下所示。

//右旋操作，传入最小不平衡子树根结点；
AVLNode rightRotate(AVLNode node) {
    AVLNode child = node -> left;
    AVLNode grandnode = child -> right;
    // 以 child 为原点，将 node 向右旋转
    child -> right = node;
    node -> left = grandnode;
    //更新结点高度；
    updateHeight(node);
    updateHeight(child);
    //返回旋转后子树的根节点；
    return child;
}

RR型，左旋

相应的，如果考虑上述失衡二叉树的“镜像”，则需要执行「左旋」操作。

同理，若节点 child 本身有左子节点（记为 grandChild ），则需要在「左旋」中添加一步：将 grandChild 作为 node 的右子节点。

可以观察到，右旋和左旋操作在逻辑上是镜像对称的，它们分别解决的两种失衡情况也是对称的。基于对称性，我们可以轻松地从右旋的代码推导出左旋的代码。具体地，只需将「右旋」代码中的把所有的 left 替换为 right ，将所有的 right 替换为 left ，即可得到「左旋」代码。

//左旋操作，传入最小不平衡子树根结点；
AVLNode leftRotate(AVLNode node) { 
    AVLNode child = node -> right;
    AVLNode grandnode = child -> left;
    // 以 child 为原点，将 node 向左旋转
    child -> left = node;
    node -> right = grandnode;
    //更新结点高度；
    updateHeight(node);
    updateHeight(child);
    //返回旋转后子树的根节点；
    return child;
}

LR型，先左旋再右旋

对于下图中的失衡节点 3，仅使用左旋或右旋都无法使子树恢复平衡。此时需要先左旋后右旋，即先对child执行「左旋」，再对node执行「右旋」。

RL型，先右旋后左旋

同理，对于上述失衡二叉树的镜像情况，需要先右旋后左旋，即先对child执行「右旋」，然后对node执行「左旋」。

下图展示的四种失衡情况与上述案例逐个对应，分别需要采用右旋、左旋、先右后左、先左后右的旋转操作。

在代码中，我们通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号，来确定失衡节点属于上图中的哪种情况。

失衡结点 node 的 bf	较高一侧 child 的 bf	形态	处理
\(> 1\)（左偏）	\(\geq 0\)	LL	右旋
\(> 1\)（左偏）	\(< 0\)	LR	先左旋后右旋
\(< -1\)（右偏）	\(\leq 0\)	RR	左旋
\(< -1\)（右偏）	\(> 0\)	RL	先右旋后左旋

为了便于使用，我们将旋转操作封装成一个函数。有了这个函数，我们就能对各种失衡情况进行旋转，使失衡节点重新恢复平衡。

/ 执行旋转操作，使该子树重新恢复平衡 /
AVLNode rotate(AVLNode node) {
    // 获取节点 node 的平衡因子
    int _balanceFactor = balanceFactor(node);
    // 左偏树
    if (_balanceFactor > 1) {
        if (balanceFactor(node->left) >= 0) {
            // 右旋
            return rightRotate(node);
        } else {
            // 先左旋后右旋
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }
    // 右偏树
    if (_balanceFactor < -1) {
        if (balanceFactor(node->right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // 先右旋后左旋
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    // 平衡树，无需旋转，直接返回
    return node;
}

插入结点

「AVL 树」的节点插入操作与「二叉搜索树」在主体上类似。唯一的区别在于，在 AVL树中插入节点后，从该节点到根节点的路径上可能会出现失衡节点。因此，我们需要从这个节点开始，自底向上执行旋转操作，使失衡节点恢复平衡。

在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡；

---

---

---

【偷懒方法】：

AVLTree root = nullptr;  
AVLNode insertHelper(AVLNode node, int val);  //先声明辅助函数；

/ 插入节点 /
void insert(int val) {
    root = insertHelper(root, val);
}

/ 递归插入节点（辅助方法） /
AVLNode insertHelper(AVLNode node, int val) {
    if (node == nullptr)
        return new AVLNode{val, 1, nullptr, nullptr};  //创建AVLNode并初始化高度；
    / 1. 查找插入位置，并插入节点 /
    if (val < node->val)
        node->left = insertHelper(node->left, val);
    else if (val > node->val)
        node->right = insertHelper(node->right, val);
    else
        return node;    // 重复节点不插入，直接返回
    updateHeight(node); // 更新节点高度
    / 2. 执行旋转操作，使该子树重新恢复平衡 /
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

删除结点

删除 = BST 删除 + 回溯查平衡，但它比插入麻烦一档：

📌 插入只需调一处，删除可能要一路调到根。 因为删除让某棵子树变矮了，旋转修好之后这棵子树可能比删除前还矮一层，失衡会像涟漪一样继续向上传导，必须反复回溯检查，直到根结点。

🎯 常见考题形式：给一棵 AVL 树，删除指定结点，问调整后的形态（根是谁、根的左右孩子是谁）。一题串考 BST 删除 + 失衡判断 + 旋转，性价比极高，务必练熟。

标准四步走：

1. 按 BST 规则删除：

2. 度为 0（叶子）：直接摘；

3. 度为 1：让唯一的孩子顶替它的位置；

4. 度为 2：用直接后继（右子树最左下的结点）或直接前驱（左子树最右下的结点）的值顶替，转化为删除那个顶替者。

5. 从删除位置向上回溯，找第一个失衡结点，记为 node；取它较高的孩子为 child，child 较高的孩子为 grandChild。（找不到失衡结点就说明全树仍平衡，直接收工。）

6. 对以node的最小不平衡子树进行调整，先观察node、child、grandchild的关系，判断是执行(LL/RR/LR/RL)中的哪一种；然后执行相应的旋转操作，将以node为根的子树调整平衡；

7. 检查失衡是否向上传导：若调整完的子树高度比删除前矮了，回到第 2️⃣ 步继续向上查，直到根。

8. 例子1：

---

• 例子2：

---

• 例子3：

---

• 例子4：该例有多种情况，可以拿前驱或后继代替他，多种情况，得到的最终AVL形态也不同

AVLNode removeHelper(AVLNode node, int val);  //先声明辅助函数；

/ 删除节点 /
void remove(int val) {
    root = removeHelper(root, val);
}

/ 递归删除节点（辅助方法） /
AVLNode removeHelper(AVLNode node, int val) {
    if (node == nullptr)
        return nullptr;
    / 1. 查找节点，并删除之 /
    if (val < node->val)
        node->left = removeHelper(node->left, val);
    else if (val > node->val)
        node->right = removeHelper(node->right, val);
    else {
        if (node->left == nullptr || node->right == nullptr) {
            AVLNode child = node->left != nullptr ? node->left : node->right;  
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == nullptr) {
                delete node;
                return nullptr;
            }
            // 子节点数量 = 1 ，直接删除 node
            else {
                delete node;
                node = child;
            }
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            AVLNode temp = node->right;  
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            int tempVal = temp->val;
            node->right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    updateHeight(node); // 更新节点高度
    / 2. 执行旋转操作，使该子树重新恢复平衡 /
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

AVL 查找

树高为 \(h\) 时，查找最多比较 \(h\) 次。所以要证明查找是 \(O(\log n)\)，等价于证明：\(n\)个结点的 AVL 树，高度是\(O(\log n)\)。

换一个问法更顺手：高度为\(h\)的 AVL 树，最少能有多少个结点？ 记这个最少结点数为 \(n_h\)。要让结点最少，左右子树就得"一高一矮"（正好差 1，把平衡条件用到极限），且各自也是最省结点的 AVL 树：

\(n_1 = 1,\quad n_2 = 2,\quad n_h = n_{h-1} + n_{h-2} + 1\)

递推出来：1, 2, 4, 7, 12, 20, 33, 54, …——它的增长节奏和斐波那契数列一致（可证 \(n_h = F_{h+2} - 1\)），即按指数级增长。结点数十几个，高度就得五六层起步；反过来，结点数为 \(n\) 时高度只有 \(O(\log n)\)。查找、插入、删除的复杂度因此全部锁定在 \(O(\log n)\)。

两类经典考法：

1. 给高度求最少结点数：直接套递推式。如"高 6 层的 AVL 树最少几个结点"→ \(n_6 = 20\)。
2. 给结点数求最大高度（= 最多比较次数）：在数列里找"不超过 \(n\) 的最后一项"。如 20 个结点 → 最高 6 层 → 最多比较 6 次。

AVL 树适合谁用？

• 读多写少的场景：高频查找、低频增删（如数据库索引、字典检索）；
• 追求严格的查找最坏时间保障。

那为什么工程界红黑树更常见？ 红黑树的平衡条件更宽松（只要求"最长路径不超过最短路径 2 倍"），所以插入删除时触发旋转的频率更低，增删平均效率更高；代价是树略微高一点。查找密集型选 AVL，增删频繁选红黑树。

练习题

真题

1. 【2009-04】下列二叉排序树中，满足平衡二叉树定义的是（ ）。

解析

AVL 树要求任一结点的左右子树高度差绝对值不超过 1。

A 是 3 个结点的单支链，根结点一侧高度为 2、另一侧为 0，高度差为 2，不平衡。

B 的结构为：

两个孩子结点的高度差均为 1，根的左右子树高度相同，所有结点都满足 AVL 条件。

C 的右子树形成较长单链，根的左右高度差超过 1。

D 的左下方存在较长链，相关祖先结点高度差超过 1。

答案：B

1. 【2010-04】在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（ ）。

A. 13, 48

B. 24, 48

C. 24, 53

D. 24, 90

解析

48 的插入路径为

插入后，根 24 的右子树过高，而其右孩子 53 的左子树过高，属于 RL 型失衡。

处理 RL 型失衡：

1. 先对 53 做右旋，使 37 上升；
2. 再对 24 做左旋，使 37 成为新的根。

所以 37 的左孩子是 24，右孩子是 53。

答案：C

1. 【2012-04】若平衡二叉树平的高度为 6 ，且所有非叶结点的平衡因子均为 1 ，则该平衡二叉树的结点总数为（ ）。

A. 10

B. 20

C. 32

D. 33

解析

平衡因子为 1 表示每个非叶结点的左子树比右子树高 1。

设满足条件且高度为 h 的树含 个结点，则根的两棵子树高度分别为 和 ：

初值为

依次计算：

答案：B

1. 【2013-03】若将关键字 1,2,3,4,5,6,7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ）。

A. 0

B. 1

C. 2

D. 3

解析

连续递增插入会多次产生 RR 型失衡并进行左旋。

答案：D

1. 【2015-04】现有一棵无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。

A. 根结点的度一定为2

B. 树中最小元素一定是叶结点

C. 最后插入的元素一定是叶结点

D. 树中最大元素一定是无左子树

解析

普通二叉搜索树的中序是升序。本题中序为降序，说明比较方向相反：

• 左子树关键字大于根；
• 右子树关键字小于根。

最大元素位于不断沿左孩子到达的最左端位置。若最大元素还有左子树，其中应存在比最大值更大的关键字，产生矛盾。因此最大元素一定没有左子树，D 正确。

A 不成立，AVL 根可以只有一个孩子。

B 不成立。最小元素不能有右孩子，但可能有左孩子，所以不一定是叶结点。

C 不成立。AVL 插入后可能发生旋转，最后插入的结点可能上升为分支结点。

答案：D

1. 【2019-04】在任意一棵非空平衡二叉树（AVL树） T1 中，删除某结点 v 之后形成平衡二叉树 T2 ， 再将 v 插入 T2 形成平衡二叉树 T3 。下列关于 T1 与 T3 的叙述中，正确的是（ ）。

I.若 v 是 T1 的叶结点，则 T1 与 T3 可能不相同

II.若 v 不是 T1 的叶结点，则 T1 与 T3 一定不相同

III.若 v 不是 T1 的叶结点，则 T1 与 T3 一定相同

A. 仅I

B. 仅II

C. 仅I、II

D. 仅I、III

解析

I 正确。删除叶结点后可能导致祖先失衡并发生旋转；重新插入该关键字时，插入触发的旋转不一定把树恢复为原结构，所以可能不同。

II 错误。“一定不同”过强。例如原树为根 2、左右孩子 1 和 3。删除根 2 后再插入 2，经过 AVL 调整可以重新得到原来的平衡结构。

III 也错误。“一定相同”同样过强。例如原树只有根 2 和右孩子 3。删除非叶根 2 后得到根 3，再插入 2 得到根 3、左孩子 2，与原树不同。

因此只能确定 I。

答案：A

1. 【2021-06】给定平衡二叉树如下图所示，插入关键字23后，根中的关键字是（ ）。

A. 16

B. 20

C. 23

D. 25

解析

23 的插入路径为

根 20 变成右重，而右孩子 30 的左子树增高，形成 RL 型失衡。

先对 30 右旋，再对 20 左旋：

调整后的根为 25。

答案：D

原创练习题

1. 在下图所示的平衡二叉树中，插入关键字 25 后得到一棵新平衡二叉树。新平衡二叉树的根结点中保存的关键字是（ ）。

A. 20\ B. 25\ C. 30\ D. 40

解析

答案：C

插入 25 的路径为 40→20→30→左：

• 结点 30 高变 2，bf = 1；
• 结点 20 左子树（10）高 1、右子树高 2，bf = -1，高变 3；
• 结点 40 左子树高 3、右子树（60）高 1，bf = 2，失衡；其左孩子 20 的 bf = -1（右重），属 LR 型。

LR 型需双旋：

1. 先对 20 做左旋：30 上位，20 成为 30 的左孩子，25"过继"为 20 的右孩子；
2. 再对 40 做右旋：30 上位为根，40 成为 30 的右孩子，40 保留原右孩子 60。

1. 在下图所示的平衡二叉树中，删除关键字 5 后得到一棵新平衡二叉树。新平衡二叉树的根结点中保存的关键字是（ ）。

A. 10\ B. 20\ C. 25\ D. 30

解析

答案：D

删除叶结点 5 后，结点 10 的高度由 2 降为 1。回溯到根 20：左子树高 1、右子树高 3，bf = -2，失衡。右孩子 30 的 bf = -1（右重），属 RR 型，做一次左旋：

• 30 上位为根；
• 20 成为 30 的左孩子；
• 30 原来的左孩子 25"过继"为 20 的右孩子。

1. 在下图所示的平衡二叉树中，删除关键字 10 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 30 所在结点的左、右子结点中保存的关键字分别是（ ）。

A. 20, 35\ B. 20, 50\ C. 20, 40\ D. 35, 60

解析

答案：A

删除叶结点 10 后，结点 20 的高度降为 1。回溯到根 30：左子树高 1、右子树高 3，bf = -2，失衡。右孩子 50 的左子树（40 一支）高 2、右子树（60）高 1，bf = +1（左重），属 RL 型，需双旋：

1. 先对 50 做右旋：40 上位，50 成为 40 的右孩子；
2. 再对 30 做左旋：40 上位为根，30 成为 40 的左孩子，40 原来的左孩子 35"过继"为 30 的右孩子。

故 30 的左、右孩子分别是 20 和 35。

1. 在下图所示的平衡二叉树中，删除根结点 40（用其中序直接前驱顶替）后得到一棵新平衡二叉树。新平衡二叉树的根结点中保存的关键字是（ ）。

A. 10\ B. 20\ C. 30\ D. 60

解析

答案：C

40 的度为 2，其中序直接前驱是左子树中的最大结点 30。用 30 顶替根结点并删去原 30 结点后：

• 左子树变为以 20 为根：20 的左孩子是 10（带左孩子 5，高 2），右孩子为空（高 0）；
• 结点 20 的 bf = 2，失衡，其左孩子 10 的 bf = +1，属 LL 型；
• 对 20 做一次右旋：10 上位，20 成为 10 的右孩子。

新根为 30。注意本题综合了两步：先按 BST 规则"前驱顶替"，再对顶替造成的失衡做旋转——删除度为 2 结点引发的级联后果是真题空白。

---

1. 含有 12 个结点的平衡二叉树的最大高度为（ ）。

A. 3\ B. 4\ C. 5\ D. 6

解析

答案：C

易错点：不要按满二叉树 log₂12 误选 4——题目问的是最大高度，对应"最瘦"的树。

---

1. 在任意一棵非空平衡二叉树 T₁ 中，插入一个新结点 v 之后形成平衡二叉树 T₂，再从 T₂ 中删除 v 形成平衡二叉树 T₃。下列关于 T₁ 与 T₃ 的叙述中，正确的是（ ）。

I. T₁ 与 T₃ 可能不相同\ II. T₁ 与 T₃ 一定不相同\ III. T₁ 与 T₃ 一定相同

A. 仅 I\ B. 仅 II\ C. 仅 I、II\ D. 仅 I、III

解析

答案：A

这是 2019 年真题（"删 v 再插 v"）的操作镜像（"插 v 再删 v"）。

• I 正确。反例：T₁ 为 30(20(10,), 40)，即根 30、左子树 20 带左孩子 10、右孩子 40。插入 5 后结点 20 发生 LL 失衡，右旋得 T₂ = 30(10(5, 20), 40)；再从 T₂ 删除叶结点 5，得 T₃ = 30(10(, 20), 40)——10 成为 30 的左孩子，与 T₁（20 是 30 的左孩子）结构不同。

• II 错误。反例：T₁ 只有单个结点 2，插入 3 得 T₂ = 2(, 3)，再删除 3 即还原为 T₁。
• III 错误。同 I 的反例。

因此只能确定 I。

---

1. 给定下图所示 AVL 树，删除关键字 30。若规定用其中序后继替换被删结点，调整后根 50 的左孩子是（ ）。

A. 10\ B. 20\ C. 40\ D. 60

解析

答案： B

30 有两个孩子，先用其中序后继 40 替换 30，再删除原来的叶结点 40。此时新结点 40 左侧为 20 -> 10，平衡因子为 +2。

对该结点做一次右旋，局部子树根变为 20，因此整棵树根 50 的左孩子为 20。

如果题目不规定使用前驱还是后继，最终形态可能不唯一。

1. 关于 AVL 插入与删除后的调整，有以下叙述：

I. 插入时修复从插入点向上遇到的最低失衡结点后，更高祖先无需再次旋转；

II. 删除后的局部调整可能使子树高度继续降低，因此要继续向根检查；

III. 删除叶结点后整棵树的根关键字一定不变。

正确的是（ ）。

A. 仅 I

B. 仅 II

C. 仅 I、II

D. I、II、III

解析

答案： C

插入时，最低失衡结点经正确单旋或双旋后，该子树高度恢复到插入前，因此更高祖先不会再因本次插入而失衡，I 正确。

删除可能使调整后的子树高度下降，失衡可继续向上传播，II 正确。删除叶结点也可能触发根处旋转并改变根，III 错误。