【数据结构】考研数据结构核心考点：平衡二叉树(AVL树)详解——平衡因子与4大旋转操作入门指南

蒙奇D索隆

发布于 2025-10-21 09:31:52

2870

文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

(平衡二叉树)

导读

大家好，很高兴又和大家见面啦！！！

在上一篇内容中，我们深入探讨了二叉排序树（BST），了解了它如何通过 “左子树 < 根结点 < 右子树” 的简单规则实现动态集合的高效查找、插入和删除。其查询性能理想情况下可以达到优秀的

然而，我们也留下了一个关键的悬念：当插入的序列接近有序时，二叉排序树会退化成一条“链”，搜索性能会急剧下降至 O(n)，这与线性表无异，完全丧失了树形结构的优势。

graph TB
a[1]
b[2]
c[3]
b--->a
b--->c
d[5]
e[6]
f[7]
e--->d
e--->f
g[4]
g--->b
g--->e

a1[1]
a1--->a11[NULL]
b1[2]
b1--->b11[NULL]
c1[3]
c1--->c11[NULL]
d1[4]
d1--->d11[NULL]
e1[5]
e1---->e11[NULL]
f1[6]
f1---->f11[NULL]
g1[7]
g1--->g11[NULL]
g1--->g12[NULL]
a1--->b1--->c1--->d1--->e1--->f1--->g1

那么，我们能否创造一种能够“自我约束”、始终保持良好身材的二叉排序树呢？答案是肯定的！

今天，我们就来揭开平衡二叉树（AVL树）的神秘面纱。它正是为了解决 BST 的“退化”问题而诞生的。AVL树 在 BST 的基础上增加了一条简单的“军规”：

任意结点的左右子树高度差不能超过 1。

这条规则看似简单，却蕴含着巨大的能量，它能确保整棵树始终维持着“完美”或“接近完美”的平衡，从而将最坏情况下的时间复杂度牢牢锁定在 O(\log n)。

在本篇中，我们将一起学习：

AVL树是如何通过平衡因子来监控自身平衡状态的。
理解“最小不平衡子树” 这一关键概念，它是我们进行修复的精确目标。
初步认识当平衡被打破时，AVL树赖以维持平衡的四大“旋转”秘籍（LL, RR, LR, RL）。

现在，就让我们正式开始，探索这种兼具 BST 的灵活性与稳定高效查询性能的优雅数据结构吧！

一、基本定义

为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树（Balanced Binary Tree），也称 AVL树 。

AVL树：这个名字的全称为：Adelson-Velsky and Landis Tree(/ˈædəlsən ˈvelski ənd ˈlændɪs triː/)。G.M. Adelson-Velsky 和 E.M. Landis 这两位发明者于1962年的论文中提出该数据结构，因此该数据结构也由这两位提出者的名字命名。

*[AVL树]: Adelson-Velsky and Landis Tree，自平衡二叉排序树 *[BST]: Binary Search Tree，二叉搜索树/二叉排序树

定义结点左子树与右子树的高度差为该结点的平衡因子，则二叉树结点的平衡因子的值只可能是 -1、0、1 这三个值中的一种。

因此平衡二叉树可定义为一棵空树，或是具有以下性质的二叉树：

左子树与右子树均为平衡二叉树
左子树与右子树的高度差的绝对值不超过1

若我们将各结点的平衡因子存储在各结点中，那么二叉树是否平衡可以体现为以下情况：

平衡二叉树

graph TB
a[a<br>1]--->b[b<br>-1]
a--->c[c<br>1]
b--->d[d<br>0]
b--->e[e<br>1]
c--->f[f<br>0]
c--->g[NULL]
e--->h[g<br>0]
e--->i[NULL]

在上述的这棵二叉树中，总共7个结点：

结点a：左子树高度为 3 右子树高度为 2 平衡因子：左子树 - 右子树 = 3 - 2 = 1
结点b：左子树高度为 1 右子树高度为 2 平衡因子：左子树 - 右子树 = 1 - 2 = -1
结点d：左子树高度为 0 右子树高度为 0 平衡因子：左子树 - 右子树 = 0 - 0 = 0

可以看到，这棵二叉树的任意一棵子树均为平衡二叉树，且其左右子树的高度差的绝对值也不超过1，因此这棵树为一棵平衡二叉树

不平衡二叉树

graph TB
a[a<br>2]--->b[b<br>-1]
a--->c[c<br>0]
b--->d[d<br>0]
b--->e[e<br>0]
e--->f[f<br>0]
e--->g[g<br>0]

在上述这棵二叉树中，同样有7个结点

结点a：左子树高度为：3 右子树高度为：1 平衡因子：左子树 - 右子树 = 3 - 1 = 2
结点b：左子树高度为：1 右子树高度为：2 平衡因子：左子树 - 右子树 = 1 - 2 = -1
结点e: 左子树高度为：1 右子树高度为：1 平衡因子：左子树 - 右子树 = 1 - 1 = 0

可以看到虽然该棵树的左右子树均为平衡二叉树，但是其左右子树的高度差的绝对值却大于1，因此该棵树不是一棵平衡二叉树

二、AVL树的插入

二叉排序树保证平衡的基本思想如下：

每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因此次操作而导致了不平衡。
若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点 a
再对以结点 a 为根的子树，在保持二叉排序树特性的前提下，调整各个结点的位置关系，使其重新达到平衡

下面我们通过一个实例来理解该保持平衡的思想；

graph TB
a[27<br>-1]--->b[16<br>0]
a--->c[75<br>1]
c--->d[38<br>0]
c--->e[NULL]

在上述这棵 AVL树 中，第一行是结点中存储的关键字的值，第二行是该结点所在的子树对应的平衡因子。

接下来我们需要在树中插入一个元素：51 。根据二叉排序树的插入规则，我们会得到下面这棵 BST：

graph TB
a[27<br>-2]--->b[16<br>0]
a--->c[75<br>2]
c--->d[38<br>-1]
c--->c1[NULL]
d--->d1[NULL]
d--->e[51<br>0]

可以看到，此时的 BST 中，有两棵子树的平衡因子的绝对值大于 1 ，其对应的子树分别为：

关键字：27 为根结点的子树

graph TB
a[27<br>-2]--->b[16<br>0]
a--->c[75<br>2]
c--->d[38<br>-1]
c--->c1[NULL]
d--->d1[NULL]
d--->e[51<br>0]

classDef redNode fill:#ff9999,color:#000,stroke:#ff0000,stroke-width:2px
class a redNode

关键字：75 为根结点的子树

graph TB
c[75<br>2]
c--->d[38<br>-1]
c--->c1[NULL]
d--->d1[NULL]
d--->e[51<br>0]

classDef redNode fill:#ff9999,color:#000,stroke:#ff0000,stroke-width:2px
class c redNode

按照二叉排序树保证平衡的基本思想，我们需要找到离插入结点最近的不平衡子树（最小不平衡子树），也就是上图中以 75 为根结点的子树；再通过调整该子树中的结点位置，来使其重新达到平衡（具体的调整过程这里我们不展开说明，我们现在只关心最后的调整结果）：

graph TB
c[75<br>0]
d[38<br>0]
e[51<br>0]
e--->d
e--->c

classDef redNode fill:#ff9999,color:#000,stroke:#ff0000,stroke-width:2px
class c redNode

classDef orangeNode fill:#ffcc99, color:#000,stroke:#ff0000, stroke-width:2px
class e orangeNode

上图所示的这棵子树就是我们说的 最小不平衡子树。

当我们完成对该子树的调整后，整棵二叉排序树就被调整为了下面这棵新的 BST：

graph TB
a[27<br>-1]
b[16<br>0]
c[75<br>0]
d[38<br>0]
e[51<br>0]
a--->b
a--->e
e--->d
e--->c

classDef redNode fill:#ff9999,color:#000,stroke:#ff0000,stroke-width:2px
class c redNode

classDef orangeNode fill:#ffcc99, color:#000,stroke:#ff0000, stroke-width:2px
class e orangeNode

可以看到，此时的 BST 又恢复成了一棵 AVL树。