AVL樹

AVL樹
類型	樹
發明時間	1962年
發明者	格奧爾吉·阿傑爾松-韋利斯基 葉夫根尼·蘭迪斯
用大O符號表示的時間複雜度
算法 平均 最差 空間 $O(n)$ $O(n)$ 搜尋 $O(\log n)$ $O(\log n)$ 插入 $O(\log n)$ $O(\log n)$ 刪除 $O(\log n)$ $O(\log n)$

非AVL樹的例子

AVL樹（英語：AVL tree）是計算機科學中最早被發明的自平衡二叉查找樹。在AVL樹中，任一節點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間複雜度都是 $O(\log {n})$。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉，以實現樹的重新平衡。AVL樹得名於它的發明者格奧爾吉·阿傑爾松-韋利斯基和葉夫根尼·蘭迪斯，他們在1962年的論文《An algorithm for the organization of information》中公開了這一數據結構。

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

同一個樹在高度平衡之後的樣子

操作

此動畫演示了不斷將節點插入AVL樹時的情況，並且演示了左旋（Left Rotation）、右旋（Right Rotation）、右左旋轉（Right-Left Rotation）、左右旋轉（Left-Right Rotation）以及帶子樹的右旋（Right Rotation with children）。

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的實現）

balance(null) -> null;
balance({null, _, null}=Tree) -> Tree;
balance({Left, Value, Right}=Tree) ->
	Diff = count(Left)-count(Right),
	if (Diff < 2) and (Diff > -2)	->	{balance(Left), Value, balance(Right)};
	   (Diff > 1)				->	balance(rotate_right(Tree));
	   (Diff< -1)				->	balance(rotate_left(Tree));
	   true					->	exit('This is impossible!')
	end.

rotate_right({Left, Value, Right}) ->
	merge_max(Left, {null, Value, Right}).

rotate_left({Left, Value, Right}) ->
	merge_min(Right, {Left, Value, null}).

merge_min({null, Value, Right}, Tree2) ->
	{Tree2, Value, Right};
merge_min({Left, _, _}, Tree2) ->
	merge_min(Left, Tree2).

merge_max({Left , Value, null}, Tree2) ->
	{Left, Value, Tree2};
merge_max({_, _, Right}, Tree2) ->
	merge_max(Right, Tree2).

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
• Data Structures and Algorithm Analysis in C (2nd edition) （頁面存檔備份，存於網際網路檔案館）