摘要訊息 : 高度平衡的二元搜尋樹.

0. 前言

二元搜尋樹 (《【資料結構】樹——二元搜尋樹》) 有不錯的搜尋性能, 其搜尋的時間複雜度為 \Theta(h). 其中, h 是二元搜尋樹的高度. 如果將 \left \{ 1, 2, 3, 4, 5, 6, 7, 8 \right \} 或者 \left \{ 8, 7, 6, 5, 4, 3, 2, 1 \right \} 組織成二元搜尋樹, 如果不對元素進行打亂, 二元搜尋樹就會退化為連結串列 (《【資料結構】連結串列》). 這個時候, 在二元搜尋樹中搜尋的時間複雜度同時也會退化為 \Theta(n). 如果能夠讓 h 滿足 \displaystyle {h = \Theta(\log {n})}, 那麼在二元搜尋樹中搜尋的時間複雜度就能夠非常可觀.

Tip : 本文要求閣下了解二元樹的旋轉操作, 可以參考《【資料結構】樹——二元樹》第 5 節.

1. 定義

定義 1. 若一棵二元搜尋樹 \mathcal {T} 滿足任意節點的兩個子樹的高度相差不超過 1, 則稱 \mathcal {T} 為 AVL 樹 (AVL tree, Adelson-Velsky and Landis tree).

根據《【資料結構】樹》定義 13, 任意 AVL 樹都是一棵平衡樹, 其平衡條件為 \displaystyle {B = \left \{ \text {任意節點的子樹的高度相差不超過 } 1 \right \}}. 另外根據定義 1, 一棵 AVL 樹中, 任意子樹同時也是一棵 AVL 樹.

定義 2. 設 x 是 AVL 樹 \mathcal {T} 中的任意節點, x_{\mathrm {L}} 是 x 的左子節點, x_{\mathrm {R}} 是 x 的右子節點. 我們稱 \displaystyle {b(x) = h_{x_{\mathrm {L}}} - h_{x_{\mathrm {R}}}} 為節點 x 的平衡因素 (balance factor). 其中, h_{x} 表示以 x 為根節點的子樹的高度.

結合定義 1, 我們容易得到 AVL 樹中任意節點的平衡因素值域為 \displaystyle {R_{b} = \left \{ -1, 0, 1 \right \}}.

2. 性質

性質 1. 設一棵高度為 h 的 AVL 樹, 令 n(h) 表示其可容納的最少節點數量, 則有 \displaystyle {n(h) = \begin {cases} 0 & {h = 0} \\ 1 & {h = 1} \\ n(h - 1) + n(h - 2) + 1 & {h > 1}. \end {cases}}

證明 :

當 h = 0 時, AVL 樹中沒有節點, 因此 n(0) = 0. 當 h = 1 時, AVL 樹中有且唯有一個節點, 因此 n(1) = 1. 當 h > 1 時, 根節點有兩棵子樹. 根據定義 1, 這兩棵子樹的高度必須相差 1. 如果這兩棵子樹高度相等, 那麼其中一棵子樹的高度減一之後仍然滿足定義 1, 這就導致這兩棵子樹中有一棵子樹的節點不滿足最少的條件; 如果這兩棵子樹的高度相差 2 甚至以上, 那麼這棵樹不滿足定義 1. 此時, 樹中的節點數量可以表示為左子樹中的節點數量和右子樹中的節點數量之和, 再加上根節點, 即 \displaystyle {n(h) = n(h - 1) + n(h - 2) + 1}.

綜上所述, 有 \displaystyle {n(h) = \begin {cases} 0 & {h = 0} \\ 1 & {h = 1} \\ n(h - 1) + n(h - 2) + 1 & {h > 1}. \end {cases}}

\blacksquare

性質 2. 若一棵 AVL 樹有 n 個節點, 那麼樹的高度為 \Theta(\log {n}).

證明 :

根據性質 1, 由於 n(h - 1) > n(h - 2), 因此我們有 \displaystyle {\begin {aligned} n(h) &= n(h - 1) + n(h - 2) + 1 \\ &> n(h - 2) + n(h - 2) + 1 \\ &\geq 2n(h - 2) \\ &\geq 2^{2}n(h - 3) \\ &\geq ... \\ &\geq 2^{h - 2}n(1) = 2^{h - 2}. \end {aligned}} 不等式兩側取對數, 最終有 \displaystyle {h \leq \log_{2}{n(h)} + 2. \ \ \ \ \ \ \ \ \ \ (\mathrm {I})} 從另一個角度, 我們又有 \displaystyle {\begin {aligned} n(h) &= n(h - 1) + n(h - 2) + 1 \\ &< n(h - 1) + n(h - 1) + 1 \\ &< 2n(h - 1) + 1 \\ &\leq 2n(h - 1) \\ &\leq 2^{2}n(h - 2) \\ &\leq ... \\ &\leq 2^{h - 1}n(1) = 2^{h - 1}. \end {aligned}} 不等式兩側取對數, 又有 \displaystyle {h \geq \log_{2}{n(h)} + 1. \ \ \ \ \ \ \ \ \ \ (\mathrm {II})} 結合 (\mathrm {I}) 式和 (\mathrm {II}) 式, 有 \displaystyle {\log_{2}{n(h)} + 1 \leq h \leq \log_{2}{n(h)} + 2}. 根據《漸近分析基礎》定義 3, 最終有 \displaystyle {h = \Theta(\log {n})}.

由於 AVL 樹有 n 節點, 因此 n(h) = n. 綜上所述, 樹的高度為 \Theta(\log {n}).

\blacksquare

性質 3. 對於費氏數列 x_{n} = \begin {cases} 0 & {n = 0} \\ 1 & {n = 1} \\ x_{n - 1} + x_{n - 2} & {n > 1} \end {cases}, n(h) 滿足 \displaystyle {n(h) = x_{h + 2} - 1}.

證明 :

我們使用歸納法進行證明.

當 h = 0 時, n(0) = x_{2} - 1 = x_{0} + x_{1} - 1 = 0; 當 h = 1 時, n(1) = x_{3} - 1 = x_{1} + x_{2} - 1 = 1.

不妨假設當 h < k 時, 都有 n(h) = x_{h + 2} - 1 成立.

當 h = k 時, 有 \displaystyle {\begin {aligned} n(h) &= n(h - 1) + n(h - 2) + 1 \\ &= x_{h + 1} - 1 + x_{h} - 1 + 1 \\ &= x_{h + 1} + x_{h} - 1 \\ &= x_{h + 2} - 1. \end {aligned}}

綜上所述, n(h) = x_{h + 2} - 1 成立.

\blacksquare

3. 插入

AVL 樹的插入操作和二元搜尋樹是一樣的, 只是 AVL 樹要檢查插入操作完成之後樹是否仍然維持定義 1. 如果樹的平衡被破壞了, 那麼就需要進行一些調整. 我們可以從平衡因素的角度入手. 如果在插入操作之後, 樹中存在一些節點的平衡因素不再是 -1, 0 或者 1, 那麼這棵樹的平衡就被破壞了. 插入操作對平衡因素的影響如下 :

1. 一個節點 x 的平衡因素值域 R_{b} 發生了變化, 為 \displaystyle {R_{b} = \left \{ -2, -1, 0, 1, 2 \right \}};
2. 若一個節點的平衡因素為 2, 那麼之前這個節點的平衡因素為 1; 若一個節點的平衡因素為 -2, 那麼之前這個節點的平衡因素為 -1;
3. 從根節點到插入節點的這條路徑上, 所有節點的平衡因素都會因為插入操作而發生改變;

能夠導致第二點的情形有四種, 設插入節點為 x, 我們可以畫出這四種情況 :

可以看到, 節點 A 在插入之前的平衡因素為 -1 或 1. 由於 x 插入到了 A 的子樹中, 導致了以 A 為根節點的子樹不再平衡. 此時, b(A) \in \left \{ -2, 2 \right \}. 另一個角度, 既然 x 成為了以 A 為根節點的子樹中的一個節點, 那麼在插入的過程中, 就一定會遇到 A. 總的來說, 插入之前 b(A) = \pm 1, 插入之後 b(A) = \pm 2. 那麼在根節點到 A 的這條路徑上, 是否存在另外一個 A', 其也滿足插入之前 b(A') = \pm 1, 插入之後 b(A') = \pm 2 呢? 當然可能存在. 所以為了區分, 我們規定 A 是離 x 最近的那個祖先節點.

這裡要特別注意, A 並不一定是 x 父節點的父節點. 從根節點到 x 的這條路徑上, 任何離 x 最近且滿足插入之前平衡因素為 \pm 1, 插入之後平衡因素為 \pm 2 的節點都可能是 A. 就像 Figure 3 中那樣, 在元素 4 插入之前, b(20) = 0; 在元素 4 插入之後, b(20) = -1. 所以元素為 20 的那個節點顯然不可能成為 A.

如果在插入之後, 從根節點到插入的節點, 根本找不到一個 A 滿足插入之前 b(A) = \pm 1, 插入之後 b(A) = \pm 2, 那麼就說明這棵 AVL 樹仍然是平衡的, 不需要調整.

接下來我們主要討論如何調整 AVL 樹因插入導致的不平衡. 在 Figure 2 的前兩種情況中, x 的插入導致 b(A) = -2. 也就是說, 能夠導致 b(A) = -2 的插入只能在 A 的左子樹中進行. 我們稱這種情況引起了 L 型不平衡. 具體地, 如果插入發生在 A 的左子樹的左子樹中, 我們細化為 LL 型不平衡; 如果插入發生在 A 的左子樹的右子樹中, 我們細化為 LR 型不平衡. 在 Figure 2 的後兩種情況中, x 的插入導致了 b(A) = 2. 換句話說, 能夠導致 b(A) = 2 的插入只能發生在 A 的右子樹中. 我們稱這種情況引起了 R 型不平衡. 類似的, 如果插入發生在 A 的右子樹的左子樹中, 我們細化為 RL 型不平衡; 如果插入發生在 A 的右子樹的右子樹中, 我們細化為 RR 型不平衡.

不平衡的調整既要維持 AVL 樹的定義, 同時原樹必須還是一棵二元搜尋樹. 看似這樣的調整無從下手, 但是我們容易從《【資料結構】樹——二元搜尋樹》性質 1 中得到啟發 : 在調整的時候, 我們只要維持中序尋訪的結果不變, 那麼就可以既維持樹的平衡, 又保證樹還是一棵二元搜尋樹. 同時, 我們又可以從《【資料結構】樹——二元樹》定理 1 中得到啟發 : 旋轉操作不會改變二元樹的中序尋訪結果. 兩者結合, 我們自然想到, 不平衡的調整可以借助旋轉來進行.

能引起 LL 型不平衡只有一種情況 :

其中, A_{\mathrm {R}} 是 A 的右子樹, 其高度為 h; B_{\mathrm {L}} 是 B 的左子樹, 其高度為 h; B_{\mathrm {R}} 是 B 的右子樹, 其高度也為 h. 因為如果 B_{\mathrm {L}} 的高度為 h - 1, 那麼 b(B) = 1, 向左子樹插入至多引起 b(B) = 0, 不會導致不平衡. 如果 B_{\mathrm {R}} 的高度為 h - 1, 本身就是一種 LL 型不平衡, 需要調整. 如果 A_{\mathrm {R}} 的高度為 h - 1, 那麼 A 的兩棵子樹高度相差為 2. 如果 A_{\mathrm {R}} 的高度為 h + 1, 那麼 b(A) = 0, 向 B_{\mathrm {L}} 插入節點至多導致 b(A) = 1. 因此, LL 型不平衡有且唯有 Figure 4-1 這一種可能. 引起 LL 型不平衡的原因是一個新的節點被插入到 B_{\mathrm {L}} 中, 導致了 B_{\mathrm {L}} 的高度從 h 增加到了 h + 1.

解決的方法就是以 B 節點為中心, 進行右旋轉.

這樣, B 的兩棵子樹的高度都為 h + 1, 以 B 為新根節點的子樹保持了平衡.

和 LL 型不平衡對應的是 RR 型不平衡. LL 型不平衡的糾正是採用右旋轉, 那麼 RR 型不平衡的糾正就採用左旋轉.

LL 型不平衡和 RR 型不平衡都只需要一次旋轉就可以讓 AVL 樹的局部維持平衡. 因此, 我們說 LL 型不平衡和 RR 型不平衡由單旋轉來調整. 但是 LR 型不平衡和 RL 型不平衡需要使用雙旋轉來調整, 也就是要旋轉兩次. 先來看 LR 型不平衡. 能引起 LR 型不平衡的同樣只有一種情況 :

現在, 我們將 B_{\mathrm {R}} 繼續分解, 分解為節點 C 及其它的左右子樹 C_{\mathrm {L}} 和 C_{\mathrm {R}}. 這裡, 我們不需要去關心 C_{\mathrm {L}} 和 C_{\mathrm {R}} 的高度到底是多少. 我們只需要知道由於 B_{\mathrm {R}} 的高度為 h + 1, 因此 C_{\mathrm {L}} 和 C_{\mathrm {R}} 中至少有一個高度為 h 才能使得以 C 為根節點的子樹, 即 B_{\mathrm {R}} 的高度為 h + 1.

接著以 C 為中心, 進行左旋轉.

現在, A 的兩棵子樹高度差仍然為 2, 所以繼續以 C 為中心, 進行右旋轉.

這樣, C 的兩棵子樹的高度都為 h + 1, 樹保持平衡. 總的來說, LR 型不平衡的糾正需要使用一次左旋轉和一次右旋轉. RL 型不平衡的糾正恰好和 LR 型不平衡相反, 需要使用一次右旋轉和左旋轉 :

我們來總結一下各種不平衡情況的修正方法 :

• LL 型不平衡 : 進行一次右旋轉;
• RR 型不平衡 : 進行一次左旋轉;
• LR 型不平衡 : 進行一次左旋轉之後再進行一次右旋轉;
• RL 型不平衡 : 進行一次右旋轉之後再進行一次左旋轉.

最後, 我們討論一下 AVL 樹中插入操作的複雜度. 根據二元搜尋樹插入操作的時間複雜度, 在 AVL 樹中插入一個元素至少需要 \Omega(\log {n}) 的時間. 在插入完成之後, 我們至多需要進行兩次旋轉, 而旋轉操作都是 \Theta(1) 的. 因此, AVL 樹插入操作的時間複雜度仍然為 \Theta(\log {n}). 由於在二元搜尋樹中插入和旋轉操作都不需要額外的輔助空間, 因此在 AVL 樹中插入元素的空間複雜度為 \Theta(1).

4. 移除

和插入類似, 我們同樣適用二元搜尋樹的移除演算法在 AVL 樹中進行移除操作, 如果移除操作導致了樹的不平衡, 那麼就進行調整. 現在我們來列舉各種可能的情況. 假設要移除的節點為 x, 其父節點為 p. 如果 x 是葉子節點, 那麼移除 x 會導致 b(p) 值發生變化. 若 x 是 p 的左子節點, 那麼 b(p) 減少 1; 若 x 是 p 的右子節點, 那麼 b(p) 增加 1. 若 x 只有一棵子樹, 那麼移除 x 導致的 b(p) 值變化和上面是一樣的. 假設 x 有兩棵子樹, 那麼情況就有些不同了. 這個時候, 我們是沒有辦法計算 b(p) 的值是否變化的, 因為我們根本不知道 x 的兩棵子樹到底是什麼情況. 在二元搜尋樹中, 我們一般會選取 x 左子樹中最大的元素來替換 x 或者 x 右子樹中最小元素來替換 x. 那麼 x 被移除了嗎? 實際上 x 對應的節點還在, 只是裡面的元素發生了變化. 真正被移除的是左子樹中那個最大元素對應的節點或者右子樹中那個最小元素對應的節點. 因此, 當 x 有兩棵子樹的時候, 我們真正要考慮的是左子樹中最大元素對應的節點或者右子樹中最小元素對應的節點 x' 的父節點 p' 對應的 b(p') 值的變化. 而 x' 必定是葉子節點, 這又回到了開始的那種情形.

我們綜合一下上面討論的三種情況, 記 x 是真正從樹中被移除的節點, p 是 x 的父節點. x 的移除必然導致 b(p) 值的變化 :

• 如果 b(p) 的值從 \pm 1 變為了 0, 就說明以 p 為根節點的子樹高度減少了 1;
• 如果 b(p) 的值從 0 變成了 \pm 1, 就說明以 p 為根節點的子樹高度維持不變;
• 如果 b(p) 的值從 \pm 1 變為了 \pm 2, 那麼以 p 為根節點的子樹不再是平衡的.

對於第二種情況, 若 p 的兩棵子樹的高度都為 h, 由於 b(p) 值發生了改變, 所以一棵樹的高度減少到了 h - 1. 但是因為另外一棵子樹的高度仍然為 h, 所以以 p 為根節點的樹的高度仍然為 h + 1, 沒有發生變化. 於是對於第二種情況, AVL 樹的平衡並不需要調整.

對於第一種情況, 雖然以 p 為根節點的子樹仍然保持了平衡, 但是由於它的高度減少了 1, 我們從 p 的父節點開始一直上溯到根節點, 途中檢查以各節點為根的子樹的平衡性. 一旦發現某個節點的平衡性被破壞, 就要進行調整. 對於第三種情況, 平衡調整將立即開始.

從 p 開始上溯, 找到第一個節點 A, 其滿足 b(A) = \pm 2. 如果移除的節點在 A 的左子樹中, 我們稱移除引起了 L 型不平衡; 如果移除的節點在 A 的右子樹中, 我們稱移除引起了 R 型不平衡. 對於 b(A) = 2, 移除在 A 的右子樹進行, 在移除之前必定有 b(A) = 1. 因此可以判斷 A 必定存在一棵左子樹, 不妨設這棵左子樹以 B 為根節點. 對於 b(A) = -2, 移除在 A 的左子樹進行, 在移除之前必定有 b(A) = -1. 因此可以判斷 A 必定存在一棵右子樹, 不妨設這棵左子樹以 B 為根節點. 於是, 我們可以根據 b(B) 的值將 L 型不平衡分為 L₀ 型不平衡, L₁ 型不平衡和 L_-1 型不平衡, 將 R 型不平衡分為 R₀ 型不平衡, R₁ 型不平衡和 R_-1 型不平衡.

對於 L₀ 型不平衡, 由於 b(B) = 0, 因此 B 的左右子樹是一樣高的, 不妨設為 h, 於是以 B 為根節點的子樹的高度為 h + 1. 由於 b(A) 在節點移除之前的值為 1, 因此 A 右子樹的高度會比 A 左子樹低 1, 即 A 右子樹 A_{\mathrm {R}} 的高度為 h. 從右子樹中移除一個節點導致 b(A) = 2 實際上說明了 A_{\mathrm {R}} 的高度降低為 h - 1.

此時, 我們以節點 B 為中心, 進行右旋轉.

在調整之後, 以 B 為根節點的子樹保持了平衡. 接下來, 我們需要考慮是否需要繼續向上調整. 繼續向上調整的基礎是以 B 為根節點的子樹的高度是否發生變化. 在調整之前, 以 A 為根節點的子樹的高度為 h + 2; 在調整之後, 雖然根節點發生了改變, 但是高度仍然是 h + 2. 因此, L₀ 型不平衡只需要進行單旋轉, 即一次右旋轉即可保持平衡. 對應地, R₀ 型不平衡也只需要進行一次左旋轉即可保持平衡 :

對於 L₁ 型不平衡和 R₁ 型不平衡, 一開始的處理和 L₀ 型不平衡與 R₀ 型不平衡的處理方式是一樣的. 現在我們來看不同的地方. 以 L₁ 型不平衡為例, 在旋轉之前, 由於 b(B) = 1, 設 B 的左子樹 B_{\mathrm {L}} 的高度為 h, 那麼 B 的右子樹 B_{\mathrm {R}} 的高度為 h - 1. 於是, 以 B 為根節點的子樹的高度是 h + 1. 又因為旋轉之前 b(A) = 1, 從 A_{\mathrm {R}} 中移除節點之後導致 b(A) = 2, 所以 A 的右子樹 A_{\mathrm {R}} 的本來高度應該是 h, 某一節點被移除導致了 A_{\mathrm {R}} 的高度減少為 h - 1. 在旋轉之後, 以 A 為根節點的子樹高度為 h, 和 B 的左子樹 B_{\mathrm {L}} 的高度一樣高, 所以 b(B) = 0. 這同時也說明了以 B 為根節點的新子樹的高度和原來相比, 減少了 1. 於是, 我們就要繼續上溯, 檢查父節點是否也是不平衡的. 如果父節點保持平衡, 那麼平衡的調整就此停止; 否則, 我們需要一直檢查到根節點.

L_-1 型不平衡需要使用雙旋轉來調整. 由於 b(B) = -1, 設 B 的右子樹 B_{\mathrm {R}} 的高度為 h, 則 B 的左子樹 B_{\mathrm {L}} 的高度為 h - 1. 對於 A 的右子樹 A_{\mathrm {R}} 的高度, 由於從 A_{\mathrm {R}} 中移除節點之前 b(A) = 1, 移除之後 b(A) = 2, 因此 A_{\mathrm {R}} 的高度為 h. 在從 A_{\mathrm {R}} 中移除了一個節點之後, A_{\mathrm {R}} 的高度降低為 h - 1.

接著分解 B_{\mathrm {R}} 為以 C 為根節點的子樹及其左子樹 C_{\mathrm {L}} 和右子樹 C_{\mathrm {R}}.

然後以 C 為中心, 進行左旋轉.

最後以 C 為中心, 再進行右旋轉.

現在我們來分析 L_-1 型不平衡調整完成之後, 是否和 L₀ 型不平衡與 R₀ 型不平衡那樣需要繼續上溯進行調整. 從 Figure 11-1 中, 我們可以知道原子樹的高度為 h + 2. 從 Figure 11-4 中, 我們可以得到新子樹的高度為 h + 1. 因此, 這棵子樹的高度減少了 1. 於是, 我們還是要像 L₀ 型不平衡與 R₀ 型不平衡那樣, 上溯進行檢查和調整.

R_-1 型不平衡的調整順序恰好和 L_-1 型不平衡相反, 首先進行右旋轉, 然後進行左旋轉.

和 L_-1 型不平衡不同的是, 原子樹的高度為 h + 2, 新子樹的高度也是 h + 2. 因此 R_-1 型不平衡並不需要上溯進行檢查和調整.

我們來總結一下 AVL 樹的移除操作 :

• L₀ 型不平衡與 R₀ 型不平衡 : 只需要進行單旋轉, 時間複雜度為 \Theta(1);
• L₁ 型不平衡和 R₁ 型不平衡 : 只需要進行單旋轉, 最好的情況下只旋轉一次, 最壞的情況下需要旋轉 \Theta(\log {n}) 次. 故平均時間複雜度為 \Theta(\log {n});
• L_-1 型不平衡 : 需要進行雙旋轉, 最好的情況下只旋轉一次, 最壞的情況下需要旋轉 \Theta(\log {n}) 次. 故平均時間複雜度為 \Theta(\log {n});
• R_-1 型不平衡 : 需要進行雙旋轉, 而且只需要進行一次雙旋轉, 時間複雜度為 \Theta(1).

由於所有調整平衡性的操作需要的額外輔助空間和節點數量無關, 所以 AVL 樹移除操作的空間複雜度為 \Theta(1).

5. 實作

我自己用 C++ 實作了 AVL 樹 : https://github.com/Jonny0201/data_structure/blob/master/data_structure/AVL_tree.hpp, 大家可以參考後自行實作.