【數據結構】數據結構核心考點：AVL樹刪除操作詳解（附平衡旋轉實例）詳情 - 考研,408,數據結構,C,C++,後端開發,yyds乾貨盤點蒙奇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$ 進行刪除：

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 的刪除規則，我們可以直接對其進行刪除：

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$：

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 的刪除規則，由於該刪除結點只有一個孩子，因此完成刪除後直接用其孩子替代該結點：

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$ ，因此我們需要找到該結點最高的孩子與孫子：

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），因此我們需要對其進行一次 右單旋轉：

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$：

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

和前一個例子一樣，被刪除的結點只有一個孩子，因此刪除該結點後，直接用其孩子來頂替該結點的位置：

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$ 。接下來我們需要找到該結點的最高的孩子和最高的孫子：

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），因此我們需要對其 左孩子 先進行一次 左單旋轉，再對其進行一次 右單旋轉：

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$：

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樹 中，被刪除的結點只有一個孩子，因此刪除該結點後，直接用其孩子來頂替該結點的位置：

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$，因此我們需要找到該棵樹的最高的孩子和最高的孫子：

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），因此我們需要對該樹進行一次 左單旋轉 ：

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$：

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 刪除規則，在刪除完該結點後，我們需要直接用其孩子來替代該結點的位置：

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$，接下來我們需要找到其最高的孩子和最高的孫子：

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），因此我們需要先對其 右孩子 進行一次 右單旋轉 ，再對其做一次 左單旋轉：

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$：

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$ 來替代該結點的位置，由於進行替換的結點只有一個孩子，因此該結點的位置由其孩子進行替代：

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$ ，因此我們需要找到其最高的孩子和最高的孫子：

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），因此我們需要對 最小不平衡子樹 的 右孩子進行一次 右單旋轉：

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

再對該 最小不平衡子樹 進行一次 左單旋轉：

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$ ，因此我們需要找到其最高的孩子和最高的孫子：

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），因此我們需要先對其 左孩子 進行一次左單旋轉：

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

再對該 最小不平衡子樹 進行一次 右單旋轉：

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樹刪除操作的核心機制。

下面我們一起回顧以下本文的重要知識點：

核心操作步驟：

按照BST規則進行節點刪除
向上查找第一個最小不平衡子樹
根據"孫子節點"位置判斷旋轉類型（LL/LR/RR/RL）
執行對應的單旋或雙旋操作
檢查不平衡是否向上傳導，必要時重複調整

關鍵技巧：

通過"最高孩子→最高孫子"的路徑判斷旋轉類型
雙旋操作需要先對子節點旋轉，再對根節點旋轉
刪除操作可能引發連鎖不平衡，需要持續向上調整

實際應用：

通過6個典型用例，我們完整覆蓋了各種刪除場景，特別是用例6展示的不平衡向上傳導情況，幫助大家深入理解AVL樹的自平衡特性。

掌握了AVL樹的插入和刪除操作後，相信大家對平衡二叉搜索樹有了更深刻的理解。這些基礎知識對於學習更高級的數據結構（如紅黑樹、B樹等）至關重要。

如果本文對你有幫助，歡迎點贊⭐、收藏📁、關注✅，你的支持是我持續創作的最大動力！

有任何問題或想法，歡迎在評論區留言💬，我們一起交流討論！

也可以轉發分享🔗給更多需要的小夥伴，共同進步~

接下來我們將繼續深入數據結構與算法的精彩世界，敬請期待！

蒙奇D索隆博客

蒙奇D索隆博客

博客 / 詳情