文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【数据结构】数据结构核心考点：AVL树删除操作详解（附平衡旋转实例）

【数据结构】数据结构核心考点：AVL树删除操作详解（附平衡旋转实例）

作者头像
蒙奇D索隆
发布于 2025-11-20 08:31:41
发布于 2025-11-20 08:31:41
2790
举报
文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

(AVL树的删除)

导读

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

在上一篇内容中我们介绍了AVL树插入操作中的平衡旋转技巧（LL、LR、RR、RL旋转）后，我们了解到旋转是维护AVL树平衡的核心机制。

然而，删除操作可能引发更复杂的不平衡问题，且这种不平衡可能沿父节点路径向上传导，需多次调整。

那么，如何系统处理AVL树的删除，确保树始终保持平衡？现在，让我们直接进入正文，逐步解析删除操作的具体实现。

一、AVL树的删除步骤

AVL树的删除操作与 BST 的删除操作相似但又有所不同：

  • 相同点：对删除结点的处理相同
  • 不同点：会对失去平衡的 BST 进行平衡旋转恢复其平衡状态

下面我们就来熟悉一下 AVL树 的删除操作的具体步骤。AVL树 的删除操作可以总结为5步：

  • 使用 BST 的方法对 AVL树 进行结点的删除操作
  • 完成删除后，开始向上查找，找到第一个最小不平衡子树
    • 若删除操作对 AVL树 的平衡性没有影响，则完成删除操作
    • 若删除操作对 AVL树 的平衡性有影响，则进入第三步
  • 找到 最小不平衡子树 的最高的 孩子 和 孙子
  • 按照 孙子 的位置，对 最小不平衡子树 进行平衡旋转： 孙子 为 最小不平衡子树 的 左孩子 L 的 左子树 L，即满足 LL 平衡旋转，则需要对 最小不平衡子树 进行一次 右单旋转（LL 平衡旋转），使其恢复平衡 孙子 为 最小不平衡子树 的 左孩子 L 的 右子树 R，即满足 LR 平衡旋转，则需要对 最小不平衡子树 的 左孩子 先进行一次 左单旋转 再对该 最小不平衡子树 进行一次 右单旋转（LR 平衡旋转），使其恢复平衡 孙子 为 最小不平衡子树 的 右孩子 R 的 右子树 R，即满足 RR 平衡旋转，则需要对 最小不平衡子树 进行一次 左单旋转（RR 平衡旋转），使其恢复平衡 孙子 为 最小不平衡子树 的 右孩子 R 的 左子树 L，即满足 RL 平衡旋转，则需要对 最小不平衡子树 的 右孩子 先进行一次 右单旋转 再对该 最小不平衡子树 进行一次 左单旋转（RL 平衡旋转），使其恢复平衡
  • 完成平衡旋转后，继续向上查找 最小不平衡子树：
    • 若 AVL树 的不平衡性没有向上传导，则完成删除
    • 若 AVL树 的不平衡性向上传导，则回到第三步，直到整棵树恢复平衡

注： 若各位朋友对 BST 的删除操作不太熟悉，可以回顾：【数据结构】考研数据结构核心考点：二叉排序树(BST)全方位详解与代码实现 若各位朋友对 AVL树 的平衡旋转不太熟悉，可以回顾：【数据结构】考研数据结构核心考点：AVL树插入操作深度解析——从理论到实践的旋转平衡实现

二、AVL树的删除用例

为了更好的理解整个删除的过程，下面我们以具体的例子来进行删除演示：

2.1 用例1：删除结点不影响平衡

在下面这棵 AVL树 中，我们需要对结点 7 进行删除：

代码语言：javascript
复制
graph TB
a[2<br>平衡因子: 0]--->b[1<br>平衡因子: 0]
a--->c[3<br>平衡因子: 0]
d[6<br>平衡因子: 0]--->e[5<br>平衡因子: 0]
d--->f[7<br>平衡因子: 0]
g[4<br>平衡因子: 0]--->a
g--->d

classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class f Red

根据 BST 的删除规则，我们可以直接对其进行删除：

代码语言：javascript
复制
graph TB
a[2<br>平衡因子: 0]--->b[1<br>平衡因子: 0]
a--->c[3<br>平衡因子: 0]
d[6<br>平衡因子: 1]--->e[5<br>平衡因子: 0]
d--->f[NULL]
g[4<br>平衡因子: 0]--->a
g--->d

classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class f Red

可以看到，该结点的删除不影响整个树的平衡，因此完成删除；

2.2 用例2：最小不平衡子树中，孙子位于 LL

在下面这棵 AVL树 中，我们需要删除结点 78：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: 1]--->b[32<br>平衡因子: 1]
a--->c[78<br>平衡因子: 1]
b--->d1[18<br>平衡因子: 0]
b--->d2[40<br>平衡因子: 0]
d1--->e1[6<br>平衡因子: 0]
d1--->e2[24<br>平衡因子: 0]
c--->c1[65<br>平衡因子: 0]
c--->c2[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class c Red

根据 BST 的删除规则，由于该删除结点只有一个孩子，因此完成删除后直接用其孩子替代该结点：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: 2]--->b[32<br>平衡因子: 1]
a--->c[65<br>平衡因子: 0]
b--->d1[18<br>平衡因子: 0]
b--->d2[40<br>平衡因子: 0]
d1--->e1[6<br>平衡因子: 0]
d1--->e2[24<br>平衡因子: 0]

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

当删除完该结点后，通过向上查找，我们找到了 最小不平衡子树 ，其根结点的值存储的值为 44 ，因此我们需要找到该结点最高的孩子与孙子：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: 2<br>h = 4]--->b[32<br>平衡因子: 1<br>h = 3]
a--->c[65<br>平衡因子: 0<br>h = 1]
b--->d1[18<br>平衡因子: 0<br>h = 2]
b--->d2[40<br>平衡因子: 0<br>h = 1]
d1--->e1[6<br>平衡因子: 0<br>h = 1]
d1--->e2[24<br>平衡因子: 0<br>h = 1]

classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class d1 Orange

根结点最高的孩子为其 左孩子 （L），其最高的孙子为其 左孩子 的 左子树（L），因此我们需要对其进行一次 右单旋转：

代码语言：javascript
复制
graph TB
b[32<br>平衡因子: 0<br>h = 3]
d1[18<br>平衡因子: 0<br>h = 2]
b--->d1
a[44<br>平衡因子: 0<br>h = 2]
b--->a
e1[6<br>平衡因子: 0<br>h = 1]
d1--->e1
e2[24<br>平衡因子: 0<br>h = 1]
d1--->e2
d2[40<br>平衡因子: 0<br>h = 1]
a--->d2
c[65<br>平衡因子: 0<br>h = 1]
a--->c
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class d1 Orange

可以看到，在完成旋转后，这棵 BST 已经恢复了平衡，因此完成删除；

2.3 用例3：最小不平衡子树中，孙子位于 LR

在下面这棵 AVL树 中，我们需要删除结点 78：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: 1]--->b[32<br>平衡因子: -1]
a--->c[78<br>平衡因子: 1]
b--->d1[18<br>平衡因子: 0]
b--->d2[40<br>平衡因子: 0]
d2--->e1[35<br>平衡因子: 0]
d2--->e2[42<br>平衡因子: 0]
c--->c1[65<br>平衡因子: 0]
c--->c2[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class c Red

和前一个例子一样，被删除的结点只有一个孩子，因此删除该结点后，直接用其孩子来顶替该结点的位置：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: 2]--->b[32<br>平衡因子: -1]
a--->c[65<br>平衡因子: 0]
b--->d1[18<br>平衡因子: 0]
b--->d2[40<br>平衡因子: 0]
d2--->e1[35<br>平衡因子: 0]
d2--->e2[42<br>平衡因子: 0]

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

删除该结点后，我们通过向上查找，找到第一棵 最小不平衡子树 ，其根结点为 44 。接下来我们需要找到该结点的最高的 孩子 和最高的 孙子 ：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: 2<br>h = 4]--->b[32<br>平衡因子: -1<br>h = 3]
a--->c[65<br>平衡因子: 0<br>h = 1]
b--->d1[18<br>平衡因子: 0<br>h = 1]
b--->d2[40<br>平衡因子: 0<br>h = 2]
d2--->e1[35<br>平衡因子: 0<br>h = 1]
d2--->e2[42<br>平衡因子: 0<br>h = 1]

classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class d2 Orange

其最高的孩子为 左孩子（L），其最高的孙子为其 左孩子 的 右子树（R），因此我们需要对其 左孩子 先进行一次 左单旋转，再对其进行一次 右单旋转：

代码语言：javascript
复制
graph TB
arrow1[先对左孩子: 32<br>进行一次左单旋转<br>->]
a[44<br>平衡因子: 2<br>h = 4]
d2[40<br>平衡因子: 1<br>h = 3]
a--->d2
c[65<br>平衡因子: 0<br>h = 1]
a--->c
b[32<br>平衡因子: 0<br>h = 2]
d2--->b
d1[18<br>平衡因子: 0<br>h = 1]
b--->d1
e1[35<br>平衡因子: 0<br>h = 1]
b--->e1
e2[42<br>平衡因子: 0<br>h = 1]
d2---->e2
e2--->f1[NULL]
e2--->f2[NULL]

arrow2[再对整棵树: 44 <br>进行一次右单旋转<br>->]

D2[40<br>平衡因子: 0<br>h = 3]
B[32<br>平衡因子: 0<br>h = 2]
D2--->B
A[44<br>平衡因子: 0<br>h = 2]
D2--->A
E2[42<br>平衡因子: 0<br>h = 1]
A--->E2
C[65<br>平衡因子: 0<br>h = 1]
A--->C

D1[18<br>平衡因子: 0<br>h = 1]
B--->D1
E1[35<br>平衡因子: 0<br>h = 1]
B--->E1



classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red
class B Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class d2 Orange
class D2 Orange

完成旋转后，这棵 BST 已经恢复了平衡，因此完成删除；

2.4 用例4：最小不平衡子树中，孙子位于 RR

在下面这棵 AVL树 中，我们需要删除结点 32：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: -1]--->b[32<br>平衡因子: -1]
a--->c[78<br>平衡因子: -1]
b--->d1[NULL]
b--->d2[40<br>平衡因子: 0]
c--->c1[65<br>平衡因子: 0]
c--->c2[85<br>平衡因子: 0]
c2--->e1[80<br>平衡因子: 0]
c2--->e2[93<br>平衡因子:0]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red

在这棵 AVL树 中，被删除的结点只有一个孩子，因此删除该结点后，直接用其孩子来顶替该结点的位置：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: -2]--->b[40<br>平衡因子: 0]
a--->c[78<br>平衡因子: -1]
c--->c1[65<br>平衡因子: 0]
c--->c2[85<br>平衡因子: 0]
c2--->e1[80<br>平衡因子: 0]
c2--->e2[93<br>平衡因子:0]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red

删除完结点后，通过向上查找，我们找到了最小不平衡子树：44，因此我们需要找到该棵树的最高的 孩子 和最高的 孙子：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: -2<br>h = 4]--->b[40<br>平衡因子: 0<br>h = 1]
a--->c[78<br>平衡因子: -1<br>h = 3]
c--->c1[65<br>平衡因子: 0<br>h = 1]
c--->c2[85<br>平衡因子: 0<br>h = 2]
c2--->e1[80<br>平衡因子: 0<br>h = 1]
c2--->e2[93<br>平衡因子:0<br>h = 1]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class c Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class c2 Orange

其最高的孩子为 右孩子 （R），其最高的孙子为 右孩子 的 右子树（R），因此我们需要对该树进行一次 左单旋转 ：

代码语言：javascript
复制
graph TB

c[78<br>平衡因子: 0<br>h = 3]
a[44<br>平衡因子: 0<br>h = 2]
c--->a
b[40<br>平衡因子: 0<br>h = 1]
a--->b
c1[65<br>平衡因子: 0<br>h = 1]
a--->c1
c2[85<br>平衡因子: 0<br>h = 2]
c--->c2
e1[80<br>平衡因子: 0<br>h = 1]
c2--->e1
e2[93<br>平衡因子:0<br>h = 1]
c2--->e2
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class c Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class c2 Orange

完成旋转后，这棵 BST 已经恢复了平衡，因此完成删除；

2.5 用例5：最小不平衡子树中，孙子位于 RL

在下面这棵 AVL树 中，我们需要删除结点 32：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: -1]--->b[32<br>平衡因子: -1]
a--->c[78<br>平衡因子: 1]
b--->d1[NULL]
b--->d2[40<br>平衡因子: 0]
c--->c1[65<br>平衡因子: 0]
c--->c2[85<br>平衡因子: 0]
c1--->e1[50<br>平衡因子: 0]
c1--->e2[72<br>平衡因子:0]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red

由于该结点只有一个孩子，根据 BST 删除规则，在删除完该结点后，我们需要直接用其孩子来替代该结点的位置：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: -2]--->b[40<br>平衡因子: 0]
a--->c[78<br>平衡因子: 1]
c--->c1[65<br>平衡因子: 0]
c--->c2[85<br>平衡因子: 0]
c1--->e1[50<br>平衡因子: 0]
c1--->e2[72<br>平衡因子:0]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red

删除完该结点后，通过向上查找，我们找到了 最小不平衡子树 ：44，接下来我们需要找到其最高的 孩子 和最高的 孙子：

代码语言：javascript
复制
graph TB
a[44<br>平衡因子: -2<br>h = 4]--->b[40<br>平衡因子: 0<br>h = 1]
a--->c[78<br>平衡因子: 1<br>h = 3]
c--->c1[65<br>平衡因子: 0<br>h = 2]
c--->c2[85<br>平衡因子: 0<br>h = 1]
c1--->e1[50<br>平衡因子: 0<br>h = 1]
c1--->e2[72<br>平衡因子:0<br>h = 1]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class c Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class c1 Orange

其最高的孩子为 右孩子（R），其最高的孙子为 右孩子 的 左子树（L），因此我们需要先对其 右孩子 进行一次 右单旋转 ，再对其做一次 左单旋转：

代码语言：javascript
复制
graph TB
arrow1[先对右子树: 78<br>做一次右单旋转<br>->]
a[44<br>平衡因子: -2<br>h = 4]
b[40<br>平衡因子: 0<br>h = 1]
a--->b
c1[65<br>平衡因子: -2<br>h = 3]
a--->c1
e1[50<br>平衡因子: 0<br>h = 1]
c1--->e1
c[78<br>平衡因子: 0<br>h = 2]
c1--->c
e2[72<br>平衡因子:0<br>h = 1]
c--->e2
c2[85<br>平衡因子: 0<br>h = 1]
c--->c2
arrow2[再对整棵树<br>做一次左单旋转<br>->]



C1[65<br>平衡因子: 0<br>h = 3]
A[44<br>平衡因子: 0<br>h = 2]
C1--->A
B[40<br>平衡因子: 0<br>h = 1]
A--->B
E1[50<br>平衡因子: 0<br>h = 1]
A--->E1
C[78<br>平衡因子: 0<br>h = 2]
C1--->C
E2[72<br>平衡因子:0<br>h = 1]
C--->E2
C2[85<br>平衡因子: 0<br>h = 1]
C--->C2
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class c Red
class C Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class c1 Orange
class C1 Orange

完成旋转后，该棵 BST 又重新恢复平衡，因此完成删除；

2.6 用例6：最小不平衡子树向上传导

在下面这棵 AVL树 中，我们需要删除结点 44：

代码语言：javascript
复制
graph TB
a[33<br>平衡因子: 1]
b[10<br>平衡因子: -1]
a--->b
c[44<br>平衡因子: -1]
a--->c
d[5<br>平衡因子: 1]
b--->d
e[20<br>平衡因子: -1]
b--->e
f[37<br>平衡因子: 1]
c--->f
g[78<br>平衡因子: 1]
c--->g
h[4<br>平衡因子: 1]
d--->h
i[8<br>平衡因子: 0]
d--->i
j[15<br>平衡因子: 1]
e--->j
k[25<br>平衡因子: 1]
e--->k
l[35<br>平衡因子: 0]
f--->f1[NULL]
f--->l
m[50<br>平衡因子: 1]
g--->m
n[88<br>平衡因子: 0]
g--->n
o[1<br>平衡因子: 0]
h--->o
h--->h1[NULL]
p[12<br>平衡因子: 0]
j--->p
j--->j1[NULL]
q[23<br>平衡因子: 1]
k--->q
k--->k1[28<br>平衡因子: 0]
r[48<br>平衡因子: 0]
m--->r
m--->m1[NULL]
s[21<br>平衡因子: 0]
q--->s
q--->q1[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class c Red

由于该结点有两个孩子，根据 BST 的删除规则，我们在完成结点删除后，可以通过它的直接前驱或者直接后继来替代该结点的位置：

  • 直接前驱：其左子树的最后侧孩子——37
  • 直接后继：其右子树的最左侧孩子——48

旋转不同的孩子结点进行替代，可能会导致不同的结果，这里我们通过肉眼观察不难看出：

  • 当采用直接后继时，失去平衡的为整棵树，因为前面已经探讨过，这里就不再介绍；
  • 当采用直接前驱时，树的不平衡性会向上传导，因此，这里我们重点关注这种情况；

注意：这里是为了给大家介绍不平衡向上传导的情况，因此选择的是直接前驱；而在实际情况中，我们只需要根据自己的需求进行选择就好

接下我们通过结点 44 的直接前驱 37 来替代该结点的位置，由于进行替换的结点只有一个孩子，因此该结点的位置由其孩子进行替代：

代码语言：javascript
复制
graph TB
a[33<br>平衡因子: 1]
b[10<br>平衡因子: -1]
a--->b
c[37<br>平衡因子: -2]
a--->c
d[5<br>平衡因子: 1]
b--->d
e[20<br>平衡因子: -1]
b--->e
f[35<br>平衡因子: 0]
c--->f
g[78<br>平衡因子: 1]
c--->g
h[4<br>平衡因子: 1]
d--->h
i[8<br>平衡因子: 0]
d--->i
j[15<br>平衡因子: 1]
e--->j
k[25<br>平衡因子: 1]
e--->k

m[50<br>平衡因子: 1]
g--->m
n[88<br>平衡因子: 0]
g--->n
o[1<br>平衡因子: 0]
h--->o
h--->h1[NULL]
p[12<br>平衡因子: 0]
j--->p
j--->j1[NULL]
q[23<br>平衡因子: 1]
k--->q
k--->k1[28<br>平衡因子: 0]
r[48<br>平衡因子: 0]
m--->r
m--->m1[NULL]
s[21<br>平衡因子: 0]
q--->s
q--->q1[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class c Red

通过向上查找，我们找到了 最小不平衡子树 ，其根结点为 37 ，因此我们需要找到其最高的 孩子 和最高的 孙子：

代码语言：javascript
复制
graph TB
a[33<br>平衡因子: 1<br>h = 6]
b[10<br>平衡因子: -1<br>h = 5]
a--->b
c[37<br>平衡因子: -2<br>h = 4]
a--->c
d[5<br>平衡因子: 1<br>h = 3]
b--->d
e[20<br>平衡因子: -1<br>h = 4]
b--->e
f[35<br>平衡因子: 0<br>h = 1]
c--->f
g[78<br>平衡因子: 1<br>h = 3]
c--->g
h[4<br>平衡因子: 1<br>h = 2]
d--->h
i[8<br>平衡因子: 0<br>h = 1]
d--->i
j[15<br>平衡因子: 1<br>h = 2]
e--->j
k[25<br>平衡因子: 1<br>h = 3]
e--->k

m[50<br>平衡因子: 1<br>h = 2]
g--->m
n[88<br>平衡因子: 0<br>h = 1]
g--->n
o[1<br>平衡因子: 0<br>h = 1]
h--->o
h--->h1[NULL]
p[12<br>平衡因子: 0<br>h = 1]
j--->p
j--->j1[NULL]
q[23<br>平衡因子: 1<br>h = 2]
k--->q
k--->k1[28<br>平衡因子: 0<br>h = 1]
r[48<br>平衡因子: 0<br>h = 1]
m--->r
m--->m1[NULL]
s[21<br>平衡因子: 0<br>h = 1]
q--->s
q--->q1[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class g Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class m Orange

其最高的孩子为 右孩子（R），其最高的孙子为其 右孩子 的 左子树（L），因此我们需要对 最小不平衡子树 的 右孩子进行一次 右单旋转：

代码语言：javascript
复制
graph TB
a[33<br>平衡因子: 1<br>h = 6]
b[10<br>平衡因子: -1<br>h = 5]
a--->b
c[37<br>平衡因子: -2<br>h = 4]
a--->c
d[5<br>平衡因子: 1<br>h = 3]
b--->d
e[20<br>平衡因子: -1<br>h = 4]
b--->e
f[35<br>平衡因子: 0<br>h = 1]
c--->f

m[50<br>平衡因子: -1<br>h = 3]
c--->m
r[48<br>平衡因子: 0<br>h = 1]
m--->r

g[78<br>平衡因子: -1<br>h = 2]
m--->g
h[4<br>平衡因子: 1<br>h = 2]
d--->h
i[8<br>平衡因子: 0<br>h = 1]
d--->i
j[15<br>平衡因子: 1<br>h = 2]
e--->j
k[25<br>平衡因子: 1<br>h = 3]
e--->k



n[88<br>平衡因子: 0<br>h = 1]
g--->g1[NULL]
g--->n
o[1<br>平衡因子: 0<br>h = 1]
h--->o
h--->h1[NULL]
p[12<br>平衡因子: 0<br>h = 1]
j--->p
j--->j1[NULL]
q[23<br>平衡因子: 1<br>h = 2]
k--->q
k--->k1[28<br>平衡因子: 0<br>h = 1]

s[21<br>平衡因子: 0<br>h = 1]
q--->s
q--->q1[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class g Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class m Orange

再对该 最小不平衡子树 进行一次 左单旋转：

代码语言：javascript
复制
graph TB
a[33<br>平衡因子: 2<br>h = 6]
b[10<br>平衡因子: -1<br>h = 5]
a--->b
m[50<br>平衡因子: 0<br>h = 3]
a--->m


d[5<br>平衡因子: 1<br>h = 3]
b--->d
e[20<br>平衡因子: -1<br>h = 4]
b--->e


c[37<br>平衡因子: 0<br>h = 2]
m--->c
f[35<br>平衡因子: 0<br>h = 1]
c--->f
r[48<br>平衡因子: 0<br>h = 1]
c--->r

g[78<br>平衡因子: -1<br>h = 2]
m--->g
h[4<br>平衡因子: 1<br>h = 2]
d--->h
i[8<br>平衡因子: 0<br>h = 1]
d--->i
j[15<br>平衡因子: 1<br>h = 2]
e--->j
k[25<br>平衡因子: 1<br>h = 3]
e--->k



n[88<br>平衡因子: 0<br>h = 1]
g--->g1[NULL]
g--->n
o[1<br>平衡因子: 0<br>h = 1]
h--->o
h--->h1[NULL]
p[12<br>平衡因子: 0<br>h = 1]
j--->p
j--->j1[NULL]
q[23<br>平衡因子: 1<br>h = 2]
k--->q
k--->k1[28<br>平衡因子: 0<br>h = 1]

s[21<br>平衡因子: 0<br>h = 1]
q--->s
q--->q1[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class g Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class m Orange

完成平衡调整后，我们继续向上查找，发现此时的 最小不平衡子树 为 33 ，因此我们需要找到其最高的 孩子 和最高的 孙子：

代码语言：javascript
复制
graph TB
a[33<br>平衡因子: 2<br>h = 6]
b[10<br>平衡因子: -1<br>h = 5]
a--->b
m[50<br>平衡因子: 0<br>h = 3]
a--->m


d[5<br>平衡因子: 1<br>h = 3]
b--->d
e[20<br>平衡因子: -1<br>h = 4]
b--->e


c[37<br>平衡因子: 0<br>h = 2]
m--->c
f[35<br>平衡因子: 0<br>h = 1]
c--->f
r[48<br>平衡因子: 0<br>h = 1]
c--->r

g[78<br>平衡因子: -1<br>h = 2]
m--->g
h[4<br>平衡因子: 1<br>h = 2]
d--->h
i[8<br>平衡因子: 0<br>h = 1]
d--->i
j[15<br>平衡因子: 1<br>h = 2]
e--->j
k[25<br>平衡因子: 1<br>h = 3]
e--->k



n[88<br>平衡因子: 0<br>h = 1]
g--->g1[NULL]
g--->n
o[1<br>平衡因子: 0<br>h = 1]
h--->o
h--->h1[NULL]
p[12<br>平衡因子: 0<br>h = 1]
j--->p
j--->j1[NULL]
q[23<br>平衡因子: 1<br>h = 2]
k--->q
k--->k1[28<br>平衡因子: 0<br>h = 1]

s[21<br>平衡因子: 0<br>h = 1]
q--->s
q--->q1[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class e Orange

其最高的孩子为其 左孩子（L），其最高的孙子为 左孩子 的 左子树（L），因此我们需要先对其 左孩子 进行一次左单旋转：

代码语言：javascript
复制
graph TB
a[33<br>平衡因子: 2<br>h = 6]
e[20<br>平衡因子: 1<br>h = 5]
a--->e
b[10<br>平衡因子: 1<br>h = 4]
e--->b

m[50<br>平衡因子: 0<br>h = 3]
a--->m

d[5<br>平衡因子: 1<br>h = 3]
b--->d



c[37<br>平衡因子: 0<br>h = 2]
m--->c
f[35<br>平衡因子: 0<br>h = 1]
c--->f
r[48<br>平衡因子: 0<br>h = 1]
c--->r

g[78<br>平衡因子: -1<br>h = 2]
m--->g
h[4<br>平衡因子: 1<br>h = 2]
d--->h
i[8<br>平衡因子: 0<br>h = 1]
d--->i
j[15<br>平衡因子: 1<br>h = 2]
b--->j
k[25<br>平衡因子: 1<br>h = 3]
e--->k



n[88<br>平衡因子: 0<br>h = 1]
g--->g1[NULL]
g--->n
o[1<br>平衡因子: 0<br>h = 1]
h--->o
h--->h1[NULL]
p[12<br>平衡因子: 0<br>h = 1]
j--->p
j--->j1[NULL]
q[23<br>平衡因子: 1<br>h = 2]
k--->q
k--->k1[28<br>平衡因子: 0<br>h = 1]

s[21<br>平衡因子: 0<br>h = 1]
q--->s
q--->q1[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class e Orange

再对该 最小不平衡子树 进行一次 右单旋转：

代码语言：javascript
复制
graph TB

e[20<br>平衡因子: 0<br>h = 5]
b[10<br>平衡因子: 1<br>h = 4]
e--->b
a[33<br>平衡因子: 2<br>h = 4]
e--->a

k[25<br>平衡因子: 1<br>h = 3]
a--->k
m[50<br>平衡因子: 0<br>h = 3]
a--->m

d[5<br>平衡因子: 1<br>h = 3]
b--->d

c[37<br>平衡因子: 0<br>h = 2]
m--->c
f[35<br>平衡因子: 0<br>h = 1]
c--->f
r[48<br>平衡因子: 0<br>h = 1]
c--->r

g[78<br>平衡因子: -1<br>h = 2]
m--->g
h[4<br>平衡因子: 1<br>h = 2]
d--->h
i[8<br>平衡因子: 0<br>h = 1]
d--->i
j[15<br>平衡因子: 1<br>h = 2]
b--->j

n[88<br>平衡因子: 0<br>h = 1]
g--->g1[NULL]
g--->n
o[1<br>平衡因子: 0<br>h = 1]
h--->o
h--->h1[NULL]
p[12<br>平衡因子: 0<br>h = 1]
j--->p
j--->j1[NULL]
q[23<br>平衡因子: 1<br>h = 2]
k--->q
k--->k1[28<br>平衡因子: 0<br>h = 1]

s[21<br>平衡因子: 0<br>h = 1]
q--->s
q--->q1[NULL]
classDef Red fill: #ff9999, color: #000, stroke: #ff0000, strike-width: 2px
class b Red
classDef Orange fill: #ffcc99, color: #000, stroke: #ff0000, strike-width: 2px
class e Orange

经过这一的平衡旋转后，整棵树已经恢复了平衡，因此结束删除；

结语

今天的内容到这里就结束了，通过今天的学习，我们系统性地掌握了AVL树删除操作的核心机制。

下面我们一起回顾以下本文的重要知识点：

核心操作步骤：

  1. 按照BST规则进行节点删除
  2. 向上查找第一个最小不平衡子树
  3. 根据"孙子节点"位置判断旋转类型（LL/LR/RR/RL）
  4. 执行对应的单旋或双旋操作
  5. 检查不平衡是否向上传导，必要时重复调整

关键技巧：

  • 通过"最高孩子→最高孙子"的路径判断旋转类型
  • 双旋操作需要先对子节点旋转，再对根节点旋转
  • 删除操作可能引发连锁不平衡，需要持续向上调整

实际应用：

  • 通过6个典型用例，我们完整覆盖了各种删除场景，特别是用例6展示的不平衡向上传导情况，帮助大家深入理解AVL树的自平衡特性。

掌握了AVL树的插入和删除操作后，相信大家对平衡二叉搜索树有了更深刻的理解。这些基础知识对于学习更高级的数据结构（如红黑树、B树等）至关重要。

如果本文对你有帮助，欢迎点赞⭐、收藏📁、关注✅，你的支持是我持续创作的最大动力！

有任何问题或想法，欢迎在评论区留言💬，我们一起交流讨论！

也可以转发分享🔗给更多需要的小伙伴，共同进步~

接下来我们将继续深入数据结构与算法的精彩世界，敬请期待！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-11-19，如有侵权请联系 cloudcommunity@tencent.com 删除
class
graph
null
width
数据结构

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

class
graph
null
width
数据结构
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 导读
  • 一、AVL树的删除步骤
  • 二、AVL树的删除用例
    • 2.1 用例1：删除结点不影响平衡
    • 2.2 用例2：最小不平衡子树中，孙子位于 LL
    • 2.3 用例3：最小不平衡子树中，孙子位于 LR
    • 2.4 用例4：最小不平衡子树中，孙子位于 RR
    • 2.5 用例5：最小不平衡子树中，孙子位于 RL
    • 2.6 用例6：最小不平衡子树向上传导
  • 结语
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论