文章目錄
-
-
- 1 前言
- 2 AVL 樹簡介
- 3 AVL 樹如何保證平衡（代碼實作）
- 3.1 添加元素失衡後如何恢複平衡
-
- 3.1.1 如何實作 isBalanced 方法
- 3.1.2 如何實作 updateHeight 方法
- 3.1.3 如何實作 rebalance 方法
- 3.2 删除元素失衡後如何恢複平衡
-
- 3.2.1 從哪兒開始尋找失衡節點
- 3.2.2 如何 rebalance
- 4 總結
-
1 前言
當我們查詢特定元素時，二叉搜尋樹在大多情況下的性能會比線性表強的多。但并不總是這樣，極端情況下，二叉搜尋樹也會退化成線性表，比如我們插入從小到大的序列（從大到小的序列），這樣會導緻二叉搜尋樹中的每個節點的左孩子（右孩子）都為空。可不可以避免上述這種情況呢？可以。我們隻需要在添加元素後調整樹的結構，讓每一個節點的左右孩子盡量都不為空即可，平衡二叉樹中的平衡就是這個意思。下面我們介紹一種平衡二叉樹：AVL 樹。
2 AVL 樹簡介
AVL 樹得名于它的發明者 Adelson-Velsky 和 Landis， 它是平衡二叉樹的一種（後續将要介紹的紅黑樹也是平衡二叉樹）。那什麼是平衡二叉樹？平衡又是什麼意思？
平衡二叉樹沒有絕對的定義，在一棵二叉樹中，所有節點左子樹和右子樹的高度越接近，它就越平衡。也就是說，平衡與左右子樹的高度差有關系。為了計算高度差，平衡二叉樹的節點比二叉搜尋樹的節點會多一個高度屬性。
// 内部類
private class AVLNode<E> extends Node<E>{
......
public int height = 1; // 預設為 1 的原因是：新添加的節點一定是葉子節點，是以高度為 1。
......
}
在AVL 樹中，平衡是這樣定義的：任一節點的左右子樹的高度差的絕對值不能超過 1。也就是說，如果在添加元素或者删除元素的過程中，某一個節點違反了這個條件，那便需要經過調整恢複到平衡狀态。
3 AVL 樹如何保證平衡（代碼實作）
AVL 樹也是一棵二叉搜尋樹，是以，我們可以直接繼承它，複用它的代碼。與之前的代碼有一點不同，AVL 樹會在添加删除元素後做進一步處理，添加 afterAdd() 方法 和 afterRemove() 方法。在這兩個兩個方法中，我們需要知道是哪一個節點導緻二叉搜尋樹失衡，怎麼找到這個節點，以及如何恢複平衡。對于這三個問題，添加元素和删除元素有着各自不同的邏輯，下面我們一一介紹。
3.1 添加元素失衡後如何恢複平衡
在二叉搜尋樹中每次添加完元素以後，我們需要對節點做一次掃描，目的是找出不平衡的節點并讓其恢複平衡。
由于我們添加的節點最終會成為葉子節點，是以，高度可能變化的節點隻能是該節點的父節點和祖先節點（從父節點的父節點開始，一直往上的節點都是祖先節點），但高度變化不一定就會失衡。其中，父節點就一定不會失衡，這點可以仔細思考一下（但父節點的高度可能會變）。隻有祖先節點可能會失衡。最差的情況是由于一個祖先節點失衡，可能導緻所有往上的祖先節點都失衡！
怎麼找到失衡的祖先節點呢？非常簡單，沿着父節點一直往上走，哪個祖先節點的左右子樹的高度差的絕對值超過 1 ，誰就失衡。此時，我們需要調整以該失衡節點為根的二叉樹，讓這棵子樹回到平衡狀态（調整以該失衡節點為根的二叉搜尋樹，使其高度減 1）。同時，我們也需要更新這條路徑上各個節點的高度值。
前面我們提到最差的情況會因為一棵子樹高度變化而導緻所有祖先節點失衡，那是不是應該對所有失衡的祖先節點進行調整呢？答案是否定的。我們添加一個節點，失衡的祖先節點的高度最多加 1。我們隻需要對離添加節點距離最近、且失衡的那一個祖先節點為根的二叉搜尋樹進行調整，讓其恢複平衡狀态即可。這樣，再上面的祖先節點的高度屬性也會恢複到未添加該節點之前的狀态。
怎麼調整失衡節點的狀态呢？這裡一共包含四種情況（以下資料參考自小碼哥的視訊教程）。
下面四張 PPT 中，一共包含了 LL, RR, LR, RL 的四種情況，圖中從左到右也畫出了對應情況的處理方法。其中字母 L 代表左，R 代表右。比如，LL 代表在節點 g (grandparent) 的左孩子的左子樹上添加一個節點導緻了失衡，并且節點 g 是第一個失衡的祖先節點。 RR, LR, RL 也是類似。（圖中的字母 p 為 parent 的簡寫，n 為 node 的簡寫。T0、T1、T2、T3 是二叉樹，其中 T0 和 T1 的高度相等，T2 和 T3 的高度相等。紅色的節點為添加的節點，黑紅黑三根虛線為各棵子樹高度的參考線）
（1）LL：右旋轉
（2）RR：左旋轉
（3）LR：RR - 左旋轉，LL - 右旋轉
（4）RL：LL - 右旋轉，RR - 左旋轉
我們需要熟知右旋轉和左旋轉，這沒有什麼技巧可言，花時間看懂熟悉即可。 旋轉過後，我們需要更新一些節點的 parent 屬性和高度。
下面我将進行代碼實作。
我們首先需要建立一個 afterAdd 方法，這個方法将新添加的葉子節點傳進去。我們會根據這個葉子節點一直往上（父節點）尋找，判斷節點是否失衡。如果沒有失衡，我們需要更新節點的高度值；如果失衡了，我們會判斷此時的失衡狀态是上述四種（LL, RR, LR, RL）的哪一種狀态，然後對應進行調整。下面，我們給出整個方法的大體架構。
protected void afterAdd(Node<E> node){
Node<E> parentNode = node.parent; // 這裡我們可以進行優化，如果 parentNode 的高度值并未改變，那麼就不用繼續往上找了。
while(parentNode != null){ // 一直往上，直到根節點為止
if(isBalanced(parentNode)){
updateHeight(parentNode); // 節點沒有失衡，我們需要檢查節點的高度值;
}else{
rebalance(parentNode);
break;
}
parentNode = parentNode.parent;
}
}
上述代碼中的三個方法，isBalanced 、updateHeight 和 rebalance 對應我們要解決的 3 個問題：（1）如何判斷一棵二叉樹是否失衡；（2）如何更新節點的高度；（3）如何讓一棵二叉樹恢複至平衡狀态。我們一一來實作這些方法。
3.1.1 如何實作 isBalanced 方法
根據 AVL 樹的定義，如果一個節點的左右子樹高度差的絕對值超過 1，則被認為是失衡的。是以，我們隻需要知道左右子樹的高度，便可以完成這個方法。
private boolean isBalanced(Node<E> root){
int leftHeight = root.left == null ? 0: root.left.height;
int rightHeight = root.right == null ? 0: root.right.height;
return Math.abs(leftHeight - rightHeight) <= 1;
}
3.1.2 如何實作 updateHeight 方法
實作這個方法的邏輯和 isBalanced 方法的邏輯類似，都需要擷取左右子樹的高度。
private void updateHeight(Node<E> root){
int leftHeight = root.left == null ? 0: root.left.height;
int rightHeight = root.right == null ? 0: root.right.height;
root.height = Math.max(leftHeight, rightHeight) + 1;
}
到這裡有同學會發現上述的兩個方法有重複代碼，是以，我們可以将代碼重構一下。
我們直接在 AVLNode 類中封裝 leftHeight 和 rightHeight 方法，用于擷取目前節點左右子樹的高度值。進而我們可以在裡面封裝**計算平衡因子（左右子樹的高度差）**的方法用于 isBalanced 方法中。同時，擷取了左右子樹的高度也可以進一步更新目前節點高度。
class AVLNode<E> extends Node<E>{
......
// 擷取左子樹的高度
public int leftHeight(){
int leftHeight = this.left == null ? 0: this.left.height;
return leftHeight;
}
// 擷取右子樹的高度
public int rightHeight(){
int rightHeight = this.right == null ? 0: this.right.height;
return rightHeight;
}
// 計算節點的平衡因子
public int balanceFactor(){
return leftHeight() - rightHeight();
}
// 更新節點的高度值
public void updateHeight(){
this.height = Math.max(leftHeight, rightHeight) + 1;
}
......
}
是以，上述的 isBalanced 方法和 updateHeight 方法可以簡化成：
private boolean isBalanced(Node<E> node){
return Math.abs(((AVLNode)node).balanceFactor()) <= 1;
}
private void updateHeight(Node<E> node){
((AVLNode)node).updateHeight();
}
3.1.3 如何實作 rebalance 方法
這部分的實作最需要我們進行深思，具體的實作過程需要參照上面四張 PPT。
首先我們需要解決的問題是：目前的失衡狀态屬于四張 PPT 中的哪一種？對于這個問題，我們需要明确 g、p、n 三個節點的關系，如果 p 是 g 的左孩子，n 又是 p 的左孩子，這種情況屬于 LL 情況，其他情況也是同理。
但是，怎麼确定 p 和 n 是父節點的左孩子還是右孩子呢？理清這個問題，我們需要明白失衡的原因：由于添加了一個新的葉子節點，是以導緻以 g 為根的二叉樹失衡了。要恢複平衡，我們需要調整 g 的高度較高的子樹（左子樹或者右子樹），降低它的高度，這樣，以 g 為根節點的二叉樹的高度也就降下來了。
是以，p 和 n 是左孩子還是右孩子，完全取決于它在哪一棵高度更高的子樹上。是以，我們需要一個方法擷取一個節點更高的那棵子樹。
class AVLNode<E> extends Node<E>{
......
// 擷取高度更高的子樹
private Node<E> tallerChild(){
int leftH = leftHeight();
int rightH = rightHeight();
if(leftH > rightH){
return left;
}else if(leftH < rightH){
return right;
}else{
return isLeftChild() ? left : right; // 如果目前節點左右子樹的高度相等，我們則根據目前節點是左孩子還是右孩子來判斷。如果是左孩子，則傳回左孩子，反之，傳回右孩子。這樣做的原因是為了轉換成 LL 或者 RR 情況，恢複平衡時隻需要旋轉一次。
}
}
......
}
自此，我們可以大緻确認 rebalance 方法的邏輯了。
public void rebalance(Node<E> grand){
Node<E> parent = ((AVLNode)grand).tallerChild();
Node<E> node = ((AVLNode)parent).tallerChild();
// 分情況
if(parent.isLeftChild()){ // L-
if(node.isLeftChild()){ // LL
rotateRight(grand); // 對 grand 進行右旋轉
}else{ // LR
rotateLeft(parent); // 先對 parent 進行左旋轉變成 LL 情況
rotateRight(grand); // 再對 grand 進行右旋轉
}
}else{ // R-
if(node.isLeftChild()){ // RL
rotateRight(parent); // 先對 parent 進行右旋轉變成 RR 情況
rotateLeft(grand); // 再對 grand 進行左旋轉
}else{ // RR
rotateLeft(grand); // 對 grand 進行左旋轉
}
}
}
重點來了，如何實作 rotateLeft 方法和 rotateRight 方法。實際上兩者的實作邏輯是一樣的，我們以 ratateLeft 方法為例。
參照下圖（這張圖上面也有，為了讓大家更友善看到放這兒是一個更好的選擇），我們首先要（1）更改節點 g 和 p 的指針；（2）然後更新 T1、p 和 g 的 parent 屬性；（3）最後我們再更新 g 和 p 的高度。這個順序能調換嗎？（3）必須在（1）的後面，（2）更新 parent 屬性可以随意。
private void rotateLeft(Node<E> grand){
// 根據節點 grand 擷取節點 parent
Node<E> parent = grand.right;
// 調整指針指向
grand.right = parent.left;
parent.left = grand;
// 更改節點的 parent 屬性
// 1、維護 parent 的父節點
grand.parent = parent.parent;
if(grand.isLeftChild()){
grand.parent.left = parent;
}else if(grand.isRightChild()){
grand.parent.right = parent;
}else{
root = parent;
}
// 2、維護 grand 右孩子的父節點
Node<E> child = grand.right;
if(child != null){
child.parent = grand;
}
// 3、維護 grand 的父節點，這個要放在 1 的後面，維護 parent 的父節點需要依賴 grand 原始的父節點
grand.parent = parent;
// 更新節點的高度，兩者的順序不能反
updateHeight(grand);
updateHeight(parent);
}
同理，我們也可以建立 rotateRight 的邏輯：
private void rotateRight(Node<E> grand){
// 根據節點 grand 擷取節點 parent
Node<E> parent = grand.left;
// 調整指針指向
grand.left = parent.right;
parent.right = grand;
// 更改節點的 parent 屬性
// 1、維護 parent 的父節點
g.parent = p.parent;
if(grand.isLeftChild()){
grand.parent.left = parent;
}else if(grand.isRightChild()){
grand.parent.right = parent;
}else{
root = parent;
}
// 2、維護 parent 右孩子的父節點
Node<E> child = grand.left;
if(child != null){
child.parent = grand;
}
// 3、維護 grand 的父節點，這個要放在 1 的後面，維護 parent 的父節點需要依賴 grand 原始的父節點
grand.parent = parent;
// 更新節點的高度，兩者的順序不能反
updateHeight(grand);
updateHeight(parent);
}
仔細觀察我們可以發現，兩個方法中從更新節點的 parent 屬性開始，代碼有大量重複的地方，除了 child 變量的指向不同，其餘都相同，是以，我們可以把這塊代碼抽出來形成一個私有的方法 afterRotate：
private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child){
// 更改節點的 parent 屬性
// 1、維護 parent 的父節點
grand.parent = parent.parent;
if(grand.isLeftChild()){
grand.parent.left = parent;
}else if(grand.isRightChild()){
grand.parent.right = parent;
}else{
root = parent;
}
// 2、維護 parent 右孩子的父節點
if(child != null){
child.parent = grand;
}
// 3、維護 grand 的父節點，這個要放在 1 的後面，維護 parent 的父節點需要依賴 grand 原始的父節點
grand.parent = parent;
// 更新節點的高度，兩者的順序不能反
updateHeight(grand);
updateHeight(parent);
}
這樣 rotateLeft 方法和 rotateRight 方法可以簡化成如下形式：
private void rotateLeft(Node<E> grand){
// 根據節點 grand 擷取節點 parent，進而擷取 child
Node<E> parent = grand.right;
Node<E> child = parent.left;
// 調整指針指向
grand.right = parent.left;
parent.left = grand;
afterRotate(grand, parent, child);
}
private void rotateRight(Node<E> grand){
// 根據節點 grand 擷取節點 parent，進而擷取 child
Node<E> parent = grand.left;
Node<E> child = parent.right;
// 調整指針指向
grand.left = parent.right;
parent.right = grand;
afterRotate(grand, parent, child);
}
添加元素失衡後的恢複平衡過程已經完成，總體上看其實并不複雜，隻是過程長一些。下面我們看看删除元素失衡後如何恢複平衡。
3.2 删除元素失衡後如何恢複平衡
删除節點和添加節點類似，也需要在删除動作完成後添加 afterRemove 方法。我們需要檢測哪些節點失衡了，将其恢複至平衡狀态即可。問題來了，我們應該從哪兒開始尋找失衡節點呢？找到失衡的節點以後，是不是也像 afterAdd 方法那般僅僅需要調整一個節點的平衡狀态就可以了呢？
3.2.1 從哪兒開始尋找失衡節點
我們先回答第一個問題：從哪兒開始尋找失衡節點？對于删除操作，**無論删除的是葉子節點還是非葉子節點，最終删除的位置一定是某一個葉子節點。**這點可以回顧删除元素的 3 種情況，如果删除的是非葉子節點，最終也是用某一個葉子節點替代，與該葉子節點相關的子樹高度也可能會減少。是以，我們需要從被删除的葉子節點開始，一直往上尋找失衡節點。
3.2.2 如何 rebalance
第二個問題：删除導緻的失衡和添加一樣，僅僅隻需要 rebalance 一次嗎？（下圖中的 break 語句表明添加導緻的失衡隻需要 rebalance 一次）對于這個問題，我們需要明白為什麼添加導緻的失衡隻需要 rebalance 一次。
添加的元素如果導緻失衡，該元素所在子樹的高度會加 1，我們往上遇到第一個不平衡的節點時，将其所在子樹恢複至平衡以後高度又會減 1，至此，整棵樹再往上的節點的高度狀态和未添加該節點之前是一樣的。
現在我們分析删除元素的情況。當我們删除一個元素，如果導緻了某棵子樹失衡（失衡說明左右子樹高度差的絕對值小于 1，該子樹的高度可能不變，也可能減 1），對其恢複平衡以後，整棵子樹的高度必定會減 1。這種變化可能會導緻往上的父節點繼續失衡。是以，删除節點導緻的失衡需要一直往上 rebalance，直到根節點。
下面，我們可以得出方法 afterRemove 的邏輯了：
protected void afterRemove(Node<E> node){
// 一直調整，直至根節點
while(node != null){
if(isBalanced(node)){
// 如果平衡，則更新祖先節點的高度即可
updateHeight(node);
}else{
// 恢複平衡，則根據情況旋轉
rebalance(node); // node 為不平衡的父節點
}
node = node.parent;
}
}
我們需要注意的是在之前删除元素的過程中，我們并未改變被删除節點的 parent 屬性，這才可以直接将被删除節點直接傳入上述的 afterRemove 方法中。
4 總結
AVL 樹通過在添加元素後做進一步處理，使得它的查詢性能比二叉搜尋樹要好。而查詢的性能也會直接影響添加元素和删除元素的性能，是以，整體上AVL 樹比二叉搜尋樹要更好。可當我們在 AVL 樹中删除一個節點時，我們需要進行 O(logn) 次的旋轉調整，這在一定程度上影響了删除元素的效率。而接下來我們介紹的紅黑樹，它在這一點上進行了改進。相較于 AVL 樹，紅黑樹是一種統計性能更優的二叉樹，詳情請見資料結構系列：紅黑樹。