高度平衡二元樹

**AVL 樹**（Adelson-Velsky and Landis Tree）是電腦科學中最早被發明的自平衡二元搜尋樹。在 AVL 樹中，任一節點對應的兩棵子樹的最大高度差為 1，因此它也被稱為**高度平衡樹**。尋找、插入和刪除在平均和最壞情況下的時間複雜度都是 $O(\log {n})$ 。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉，以實現樹的重新平衡。AVL 樹得名於它的發明者 G. M. Adelson-Velsky 和 Evgenii Landis，他們在 1962 年的論文《An algorithm for the organization of information》中公開了這一資料結構。

節點的**平衡因子**是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子 1、0 或 -1 的節點被認為是平衡的。帶有平衡因子 -2 或 2 的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接儲存在每個節點中，或從可能儲存在節點中的子樹高度計算出來。

## 操作

AVL 樹的基本操作一般涉及運作同在不平衡的二元搜尋樹所運作的同樣的演算法。但是要進行預先或隨後做一次或多次所謂的 "AVL 旋轉"。

以下圖表以四列表示四種情況，每行表示在該種情況下要進行的操作。在左左和右右的情況下，只需要進行一次旋轉操作；在左右和右左的情況下，需要進行兩次旋轉操作。

### 刪除

從 AVL 樹中刪除，可以通過把要刪除的節點向下旋轉成一個葉子節點，接著直接移除這個葉子節點來完成。因為在旋轉成葉子節點期間最多有 log _n_ 個節點被旋轉，而每次 AVL 旋轉耗費固定的時間，所以刪除處理在整體上耗費 O (log _n_) 時間。

### 搜尋

可以像普通二元搜尋樹一樣的進行，所以耗費 O (log _n_) 時間，因為 AVL 樹總是保持平衡的。不需要特殊的準備，樹的結構不會由於尋找而改變。（這是與伸展樹搜尋相對立的，它會因為搜尋而變更樹結構。）

## 實現描述

假設平衡因子是左子樹的高度減去右子樹的高度所得到的值，又假設由於在二元排序樹上插入節點而失去平衡的最小子樹根節點的指標為 a（即 a 是離插入點最近，且平衡因子絕對值超過 1 的祖先節點），則失去平衡後進行的規律可歸納為下列四種情況：

1. 單向右旋平衡處理 LL：由於在 \*a 的左子樹根節點的左子樹上插入節點，\*a 的平衡因子由 1 增至 2，致使以 \*a 為根的子樹失去平衡，則需進行一次右旋轉操作；
2. 單向左旋平衡處理 RR：由於在 \*a 的右子樹根節點的右子樹上插入節點，\*a 的平衡因子由 - 1 變為 - 2，致使以 \*a 為根的子樹失去平衡，則需進行一次左旋轉操作；
3. 雙向旋轉（先左後右）平衡處理 LR：由於在 \*a 的左子樹根節點的右子樹上插入節點，\*a 的平衡因子由 1 增至 2，致使以 \*a 為根的子樹失去平衡，則需進行兩次旋轉（先左旋後右旋）操作。
4. 雙向旋轉（先右後左）平衡處理 RL：由於在 \*a 的右子樹根節點的左子樹上插入節點，\*a 的平衡因子由 - 1 變為 - 2，致使以 \*a 為根的子樹失去平衡，則需進行兩次旋轉（先右旋後左旋）操作。

在平衡的二元排序樹 BBST (Balancing Binary Search Tree) 上插入一個新的資料元素 e 的遞迴演算法可描述如下：

1. 若 BBST 為空樹，則插入一個資料元素為 e 的新節點作為 BBST 的根節點，樹的深度增 1；
2. 若 e 的關鍵字和 BBST 的根節點的關鍵字相等，則不進行；
3. 若 e 的關鍵字小於 BBST 的根節點的關鍵字，而且在 BBST 的左子樹中不存在和 e 有相同關鍵字的節點，則將 e 插入在 BBST 的左子樹上，並且當插入之後的左子樹深度增加（+1）時，分別就下列不同情況處理之：
  1. BBST 的根節點的平衡因子為 - 1（右子樹的深度大於左子樹的深度，則將根節點的平衡因子更改為 0，BBST 的深度不變；
  2. BBST 的根節點的平衡因子為 0（左、右子樹的深度相等）：則將根節點的平衡因子更改為 1，BBST 的深度增 1；
  3. BBST 的根節點的平衡因子為 1（左子樹的深度大於右子樹的深度）：則若 BBST 的左子樹根節點的平衡因子為 1：則需進行單向右旋平衡處理，並且在右旋處理之後，將根節點和其右子樹根節點的平衡因子更改為 0，樹的深度不變；
4. 若 e 的關鍵字大於 BBST 的根節點的關鍵字，而且在 BBST 的右子樹中不存在和 e 有相同關鍵字的節點，則將 e 插入在 BBST 的右子樹上，並且當插入之後的右子樹深度增加（+1）時，分別就不同情況處理之。

AVL 樹的調平（Erlang 的實現）

## AVL 節點數計算

高度為 h 的 AVL 樹，總節點數 N 最多 $2^{h+1}-1$ ； 
最少節點數 $N_{h}$ 如以斐波那契數列可以用數學歸納法證明： 
 $N_{h}$ = $F_{h+2}$ - 1 ( $F_{h+2}$ 是斐波那契數列的第 h+2 項，根據斐波那契多項式得來)。 
即: 
 $N_{0}$ = 0 (表示 AVL Tree 高度為 0 的節點總數) 
 $N_{1}$ = 1 (表示 AVL Tree 高度為 1 的節點總數) 
 $N_{2}$ = 2 (表示 AVL Tree 高度為 2 的節點總數) 
 $N_{h}$ = $N_{h-1}$ + $N_{h-2}$ + 1 (表示 AVL Tree 高度為 h 的節點總數) 
換句話說，當節點數為 N 時，高度 h 最多為 $log_{\Phi }({\sqrt {5}}*(N+1))-2$ 。

## 參見

* 樹旋轉
* 伸展樹
* 紅黑樹
* B 樹

## 參照

* G. Adelson-Velskii and E.M. Landis, "An algorithm for the organization of information." _Doklady Akademii Nauk SSSR_, 146:263–266, 1962（Russian）. English translation by Myron J. Ricci in _Soviet Math. Doklady_, 3:1259–1263, 1962.

## 外部連結

* Description from the Dictionary of Algorithms and Data Structures（頁面存檔備份，存於網際網路檔案館）
* AVL Tree Traversal（頁面存檔備份，存於網際網路檔案館）
* Linked AVL tree
* C++ AVL Tree Template and C AVL TREE "Generic Package" by Walt Karas
* A Visual Basic AVL Tree Container Class（頁面存檔備份，存於網際網路檔案館） by Jim Harris
* AVL Trees: Tutorial and C++ Implementation（頁面存檔備份，存於網際網路檔案館） by Brad Appleton
* Ulm's Oberon Library: AVLTrees（頁面存檔備份，存於網際網路檔案館）
* The AVL TREE Data Type
* CNAVLTree Class Reference
* GNU libavl（頁面存檔備份，存於網際網路檔案館）
* AVL-trees - balanced binary trees by Alex Konshin
* Simulation of AVL Trees
* AVL tree applet（頁面存檔備份，存於網際網路檔案館）
* Simulation of AVL Trees (DYNAMIC)
* AVL, Splay and Red/Black Applet