Java 資料結構 - AVL 樹

如果二叉搜尋樹的輸入以排序（升序或降序）的方式出現會怎樣？它將如下所示：

可以觀察到，BST 的最壞情況效能最接近線性搜尋演算法，即 O(n)。在即時資料中，我們無法預測資料模式及其頻率。因此，需要對現有的 BST 進行平衡。

以其發明者 **Adelson、Velski 和 Landis** 的名字命名，**AVL 樹**是高度平衡的二叉搜尋樹。AVL 樹檢查左右子樹的高度，並確保差異不超過 1。此差異稱為**平衡因子**。

在這裡我們看到第一棵樹是平衡的，而接下來的兩棵樹是不平衡的：

在第二棵樹中，C 的左子樹高度為 2，右子樹高度為 0，因此差值為 2。在第三棵樹中，A 的右子樹高度為 2，而左子樹缺失，因此為 0，差值再次為 2。AVL 樹只允許差值（平衡因子）為 1。

BalanceFactor = height(left-sutree) − height(right-sutree)

如果左右子樹高度的差異大於 1，則使用一些旋轉技術來平衡樹。

AVL 旋轉 Java

為了平衡自身，AVL 樹可以執行以下四種旋轉：

• 左旋轉
• 右旋轉
• 左-右旋轉
• 右-左旋轉

前兩種旋轉是單旋轉，後兩種旋轉是雙旋轉。要使樹不平衡，我們至少需要高度為 2 的樹。透過這棵簡單的樹，讓我們逐一瞭解它們。

左旋轉

如果在 A 節點的右子樹的右子樹中插入節點時樹變得不平衡，則我們執行單左旋轉：

在我們的示例中，由於在 A 的右子樹的右子樹中插入了一個節點，因此節點 **A** 已變得不平衡。我們透過使 **A** 成為 B 的左子樹來執行左旋轉。

右旋轉

如果在左子樹的左子樹中插入節點，則 AVL 樹可能變得不平衡。然後樹需要右旋轉。

如圖所示，透過執行右旋轉，不平衡節點成為其左子節點的右子節點。

左-右旋轉

雙旋轉是已經解釋過的旋轉版本的稍微複雜一些的版本。為了更好地理解它們，我們應該注意旋轉過程中執行的每個動作。讓我們首先檢查如何執行左-右旋轉。左-右旋轉是左旋轉後緊接著右旋轉的組合。

狀態	動作
	已將節點 **A** 插入到左子樹的右子樹中。這使得 **C** 成為不平衡節點。這些情況導致 AVL 樹執行左-右旋轉。
	我們首先對 **C** 的左子樹執行左旋轉。這使得 **A** 成為 **B** 的左子樹。
	節點 **C** 仍然不平衡，但是現在，這是由於左子樹的左子樹造成的。
	我們現在將對樹進行右旋轉，使 **B** 成為此子樹的新根節點。**C** 現在成為其自身左子樹的右子樹。
	樹現在已平衡。

右-左旋轉

第二種雙旋轉是右-左旋轉。它是右旋轉後緊接著左旋轉的組合。

狀態	動作
	已將節點插入到右子樹的左子樹中。這使得 **A** 成為一個平衡因子為 2 的不平衡節點。
	首先，我們在 C 節點執行右旋轉，使 C 成為其自身左子樹 **B** 的右子樹。現在，**B** 成為 **A** 的右子樹。
	由於其右子樹的右子樹，節點 **A** 仍然不平衡，需要左旋轉。
	透過使 **B** 成為子樹的新根節點來執行左旋轉。**A** 成為其右子樹 **B** 的左子樹。
	樹現在已平衡。