學習JavaScript數據結構與算法（第2版）：8.6 自平衡樹_Loiane Grone

現在你知道如何使用二叉搜索樹了，如果願意的話，可以繼續去學習更多關於樹的知識。

BST存在一個問題：取決於你添加的節點數，樹的一條邊可能會非常深；也就是說，樹的一條分支會有很多層，而其他的分支卻只有幾層，如下圖所示：

這會在需要在某條邊上添加、移除和搜索某個節點時引起一些性能問題。為了解決這個問題，有一種樹叫作Adelson-Velskii-Landi樹（AVL樹）。AVL樹是一種自平衡二叉搜索樹，意思是任何一個節點左右兩側子樹的高度之差最多為1。也就是說這種樹會在添加或移除節點時盡量試著成為一棵完全樹。

8.6.1　Adelson-Velskii-Landi樹（AVL樹）

AVL樹是一種自平衡樹。添加或移除節點時，AVL樹會嘗試自平衡。任意一個節點（不論深度）的左子樹和右子樹高度最多相差1。添加或移除節點時，AVL樹會盡可能嘗試轉換為完全樹。

在AVL樹中插入節點

在AVL樹中插入或移除節點和BST完全相同。然而，AVL樹的不同之處在於我們需要檢驗它的平衡因子，如果有需要，則將其邏輯應用於樹的自平衡。

下面的代碼是向AVL樹插入新節點的例子：

var insertNode = function(node, element) {
  if (node === null) {
    node = new Node(element);
  } else if (element < node.key) {
    node.left = insertNode(node.left, element);
　
    if (node.left !== null) {
      // 確認是否需要平衡 {1}
    }
  } else if (element > node.key) {
    node.right = insertNode(node.right, element);
　
    if (node.right !== null) {
      // 確認是否需要平衡 {2}
    }
  }
  return node;
};

然而，插入新節點時，還要檢查是否需要平衡樹（行{1}和行{2}）。

計算平衡因子

在AVL樹中，需要對每個節點計算右子樹高度（hr）和左子樹高度（hl）的差值，該值（hr－hl）應為0、1或-1。如果結果不是這三個值之一，則需要平衡該AVL樹。這就是平衡因子的概念。

下圖舉例說明了一些樹的平衡因子（所有的樹都是平衡的）：

計算節點高度的代碼如下：
```
var heightNode = function(node) {
  if (node === null) {
    return -1;
  } else {
    return Math.max(heightNode(node.left),
    heightNode(node.right)) + 1;
  }
};

  
```
因此，向左子樹插入新節點時，需要計算其高度；如果高度大於1（即不為-1、0和1之一），就需要平衡左子樹。代碼如下：
```
// 替換insertNode方法的行{1}
if ((heightNode(node.left) - heightNode(node.right)) > 1) {
  // 旋轉 {3}
}

  
```
向右子樹插入新節點時，應用同樣的邏輯，代碼如下：
```
// 替換insertNode方法的行{2}
if ((heightNode(node.right) - heightNode(node.left)) > 1) {
  // 旋轉 {4}
}
  
```
AVL旋轉

向AVL樹插入節點時，可以執行單旋轉或雙旋轉兩種平衡操作，分別對應四種場景。
- 右-右（RR）：向左的單旋轉
- 左-左（LL）：向右的單旋轉
- 左-右（LR）：向右的雙旋轉
- 右-左（RL）：向左的雙旋轉

我們依次看看它們是如何工作的。

**右-右（RR）：向左的單旋轉**

如下圖所示：

![{%}](http://www.ituring.com.cn/figures/2017/JavaScriptStruAlgo/11.d08z.015.png)

假設向AVL樹插入節點90，這會造成樹失衡（節點50 -Y高度為-2），因此需要恢復樹的平衡。下面是我們執行的操作：

* 與平衡操作相關的節點有三個（X、Y、Z），將節點X置於節點Y（平衡因子為-2）所在的位置（行`{1}`）；

* 節點X的右子樹保持不變；

* 將節點Y的右子節點置為節點X的左子節點Z（行`{2}`）；

* 將節點X的左子節點置為節點Y（行`{3}`）。

下面的代碼舉例說明了整個過程：

    var rotationRR = function(node) {
      var tmp = node.right;  // {1}
      node.right = tmp.left; // {2}
      tmp.left = node;       // {3}
      return tmp;
    };

**左-左（LL）：向右的單旋轉**

如下圖所示：

![{%}](http://www.ituring.com.cn/figures/2017/JavaScriptStruAlgo/11.d08z.016.png)

假設向AVL樹插入節點5，這會造成樹失衡（節點50 -Y高度為+2），需要恢復樹的平衡。下面是我們執行的操作：

* 與平衡操作相關的節點有三個（X、Y、Z），將節點X置於節點Y（平衡因子為+2）所在的位置（行`{1}`）；

* 節點X的左子樹保持不變；

* 將節點Y的左子節點置為節點X的右子節點Z（行`{2}`）；

* 將節點X的右子節點置為節點Y（行`{3}`）。

下面的代碼舉例說明了整個過程：

    var rotationLL = function(node) {
      var tmp = node.left;   // {1}
      node.left = tmp.right; // {2}
      tmp.right = node;      // {3}
      return tmp;
    };

**左-右（LR）：向右的雙旋轉**

如下圖所示：

![{%}](http://www.ituring.com.cn/figures/2017/JavaScriptStruAlgo/11.d08z.017.png)

假設向AVL樹插入節點35，這會造成樹失衡（節點50 -Y高度為+2），需要恢復樹的平衡。下面是我們執行的操作：

* 將節點X置於節點Y（平衡因子為+2）所在的位置；

* 將節點Y的左子節點置為節點X的右子節點；

* 將節點Z的右子節點置為節點X的左子節點；

* 將節點X的右子節點置為節點Y；

* 將節點X的左子節點置為節點Z。

基本上，就是先做一次RR旋轉，再做一次LL旋轉。

下面的代碼舉例說明了整個過程：

    var rotationLR = function(node) {
      node.left = rotationRR(node.left);
      return rotationLL(node);
    };

**右-左（RL）：向左的雙旋轉**

如下圖所示：

![{%}](http://www.ituring.com.cn/figures/2017/JavaScriptStruAlgo/11.d08z.018.png)

假設向AVL樹插入節點75，這會造成樹失衡（節點70 -Y高度為-2），需要恢復樹的平衡。下面是我們執行的操作：

* 將節點X置於節點Y（平衡因子為-2）所在的位置；

* 將節點Z的左子節點置為節點X的右子節點；

* 將節點Y的右子節點置為節點X的左子節點；

* 將節點X的左子節點置為節點Y；

* 將節點X的右子節點置為節點Z。

基本上，就是先做一次LL旋轉，再做一次RR旋轉。

下面的代碼舉例說明了整個過程：

    var rotationRL = function(node) {
      node.right = rotationLL(node.right);
      return rotationRR(node);
    };

完成insertNode方法

確認樹需要平衡後，就需要對每種情況分別應用正確的旋轉。

向左子樹插入新節點，且節點的值小於其左子節點時，應進行LL旋轉。否則，進行LR旋轉。該過程的代碼如下：

// 替換insertNode方法的行{1}
if ((heightNode(node.left) - heightNode(node.right)) > 1){
  // 旋轉 {3}
  if (element < node.left.key){
    node = rotationLL(node);
  } else {
    node = rotationLR(node);
  }
}

向右子樹插入新節點，且節點的值大於其右子節點時，應進行RR旋轉。否則，進行RL旋轉。該過程的代碼如下：

// 替換insertNode方法的行{2}
if ((heightNode(node.right) - heightNode(node.left)) > 1){
  // 旋轉 {4}
  if (element > node.right.key){
    node = rotationRR(node);
  } else {
    node = rotationRL(node);
  }
}

8.6.2　更多關於二叉樹的知識

儘管AVL樹是自平衡的，其插入或移除節點的性能並不總是最好的。更好的選擇是紅黑樹。

紅黑樹可以高效有序地遍歷其節點（http://goo.gl/OxED8K）。本書不打算講解紅黑樹，但也提供了它的源代碼。

如果感興趣的話，你還可以瞭解堆積樹（http://goo.gl/SFlhW6）。

8.6.1 Adelson-Velskii-Landi樹（AVL樹）

8.6.2 更多關於二叉樹的知識

8.6.1　Adelson-Velskii-Landi樹（AVL樹）

8.6.2　更多關於二叉樹的知識