---
title: 'AVL 自平衡樹'
disqus: kyleAlien
---
AVL 自平衡樹
===
## OverView of Content
[TOC]
## AVL 概述
> AVL 是 1962 年由 Adelson-Velsky & Landis 發明，所以命名為 AVL
AVL 的特色：**在操作 ++`插入`++、++`移除`++ 時去檢查樹的平衡性，如果高度差超過 1 (任何節點的高度差可以是 1、-1、0) 則進行修正**
### TreeNode 紀錄高度
* AVL 樹中的每個節點都 **必須記錄自身在樹中的高度**；當某個節點被插入二元樹時，才可以即時之察覺不平衡的樹節點
```java=
private static final class AVLTreeNode {
public AVLTreeNode left, right;
public final int val;
// 記錄當前節點的高度
public int height;
private AVLTreeNode(int val) {
this.val = val;
height = 0;
}
// 左、右子樹的高度差
public int diffHeight() {
int leftH = left == null ? -1 : left.height;
int rightH = right == null ? -1 : right.height;
return leftH - rightH;
}
// 計算自身結點的高度差
public void computeHeight() {
int leftH = left == null ? -1 : left.height;
int rightH = right == null ? -1 : right.height;
// 1 (自身) + 左、右取最高
height = 1 + Math.max(leftH, rightH);
}
}
```
### Insert 插入 - 傾斜
* 在每次 Insert 插入節點時，都需要做 **重新計算自身高的的操作**；並做了一棵 AVL 預設樹，方便 Demo 用
> 
```java=
public class AVLTree {
private final AVLTreeNode header;
public AVLTree(AVLTreeNode header) {
this.header = header;
}
public AVLTreeNode insert(int val) {
_insert(header, val);
return header;
}
private AVLTreeNode _insert(AVLTreeNode root, int val) {
if(root == null) {
// 返回新節點
return new AVLTreeNode(val);
}
if(root.val <= val) {
root.right = _insert(root.right, val);
} else if(root.val > val) {
root.left = _insert(root.left, val);
}
// 重新自計算自身節點
root.computeHeight();
return root;
}
// Demo 用預設樹
public static AVLTreeNode getDefaultTree() {
AVLTreeNode root = new AVLTreeNode(19);
AVLTree avlTree = new AVLTree(root);
avlTree.insert(14);
avlTree.insert(3);
avlTree.insert(15);
avlTree.insert(53);
avlTree.insert(26);
avlTree.insert(58);
avlTree.insert(29);
return root;
}
}
```
* 接下來使用 AVL 樹進行插入，插入 `27`，並且每個遞迴都重新計算路徑節點個高 (使用 `computeHeight` 函數)
> 
1. **更新自身高度**：當 `27` 插入後，每個路徑 (插入後會經過 4 個節點) 上的 Node 都會更新自身高度
| Node | 未更新前 | 更新高度後 |
| - | - | - |
| 27 | - | 0 (不用更新，原始就是 0) |
| 29 | 0 | 1 |
| 26 | 1 | 2 |
| 53 | 2 | 3 |
| 19 | 3 | 4 |
> 
2. **高度差**：這邊計算高度差的方式是 `left` - `right`，所以插入 `27` 後每個節點的高度差如下表
| Node | 高度差 | 計算 (`left` - `right`) |
| - | - | - |
| 29 | 1 | `0 - (-1)` |
| 26 | -2 | 右傾斜，`-1 - 1` |
| 53 | 2 | 左傾斜，`2 - 0` |
| 19 | -2 | 右傾斜，`1 - 3` |
> 當前計算方式：Math.abs(高度差) > 1，正數為左傾，負數為右傾
### Remove 移除 - 傾斜
使用以下預設寫好的二元樹，並準備移除 `58` 這個 Node 節點
> 
* **二元樹移除函數**：以下是一個基礎的二元樹移除函數 (請記得二元樹移除有 3 種可能狀態)
```java=
public AVLTreeNode _remove(AVLTreeNode root, int val) {
if(root == null) {
return null;
}
if(root.val <= val) {
root.right = _remove(root.right, val);
} else if(root.val > val) {
root.left = _remove(root.left, val);
} else {
// 1. 已是末端節點
if(root.left == null && root.right == null) {
return null;
}
// 2. 只有單邊 (左 or 右)
if(root.right == null) {
return root.left;
}
if(root.left == null) {
return root.right;
}
// 3. 左右子樹都有
AVLTreeNode tmp = root;
// 找出右子樹中的最小
root = root.right;
while (root != null) {
root = root.left;
}
// 移除最小值
AVLTreeNode fix = _removeMin(tmp.right);
// 重新為最小值串上
root.left = tmp.left;
root.right = fix;
}
return root;
}
private AVLTreeNode _removeMin(AVLTreeNode node) {
if(node.left == null) {
return node.right;
}
// 遞迴移除最小值
node.left = _removeMin(node.left);
return node;
}
```
* 測試後會發現 `58` 這個 Node 節點會 **造成 `53` 左傾斜**
| Node | 高度差 | 計算 (`left` - `right`) |
| - | - | - |
| 29 | 0 | - |
| 26 | -2 | 右傾斜，`-1 - 1` |
| 53 | 2 | 左傾斜，`2 - 0` |
```java=
public static void main(String[] args) {
AVLTreeNode root = AVLTreeNode.getDefaultTree();
AVLTree avlTree = new AVLTree(root);
avlTree.remove(58);
}
```
> 
## Node rotation 旋轉節點 - 調整傾斜
下圖為一個左傾斜的二元樹，高度為 h；`50` 左子樹高度為 `h-3`，右子樹高度為 `h-1`，其 **高度差就為 +2**，是需要調整的傾斜樹
> e.g `50` 高度為 4，左子樹高度為 1，右子樹高度為 3
>
> 
* 上圖左傾斜，可以使用 **右旋** 調整，**以 ++30 為根結點，像右旋轉++**
> 
### 二元樹 4 種不平衡 - 輔助函數
* 在只有三個節點的二原樹中，其不平衡有四種可能，透過旋轉最終可以得到相同的平衡二元樹，我們把它分為 2 組來講
1. **僅需一次旋轉**
* **左左 `rotate left`**：單右璇，即可變成平衡二元樹
> 
```java=
private AVLTreeNode rotateRight(AVLTreeNode node) {
// 找到 new Root
AVLTreeNode newRoot = node.left;
AVLTreeNode nRootR = newRoot.right;
// 將 newRoot 原本的右邊，設定給 node 的左邊
node.left = nRootR;
newRoot.right = node;
// 重新計算高度
node.computeHeight();
return newRoot;
}
```
> 照著圖做出程式
>
> 
* **右右 `rotate right`**：單左璇，即可變成平衡二元樹
> 
```java=
private AVLTreeNode rotateLeft(AVLTreeNode node) {
// 找到 new Root
AVLTreeNode newRoot = node.right;
AVLTreeNode nRootL = newRoot.left;
// 將 newRoot 原本的左邊，設定給 node 的右邊
node.right = nRootL;
newRoot.left = node;
// 重新計算高度
node.computeHeight();
return newRoot;
}
```
> 照著圖做出程式
>
> 
2. **需要兩次旋轉**
* **右左 `rotate right-left`**：先右傾再左傾；必須先右璇，再左旋
> 
```java=
private AVLTreeNode rotateRightLeft(AVLTreeNode node) {
// 先定義出重點節點
AVLTreeNode child = node.right;
AVLTreeNode newRoot = child.left; // 新節點在末端
// 新節點的左右都需要調整
AVLTreeNode nRootR = newRoot.right;
AVLTreeNode nRootL = newRoot.left;
// 串接原本新節點的子樹
child.right = nRootR;
node.left = nRootL;
// 串上新節點的左、右
newRoot.left = child;
newRoot.right = node;
// 兩棵子樹 重新計算高度
child.computeHeight();
node.computeHeight();
return newRoot; // newRoot 會在外部進行運算
}
```
> 照著圖做出程式
>
> 
* **左右 `rotate left-right`**：先左傾再右傾；必須先左旋，再右璇
> 
```java=
private AVLTreeNode rotateLeftRight(AVLTreeNode node) {
// 先定義出重點節點
AVLTreeNode child = node.left;
AVLTreeNode newRoot = child.right; // 新節點在末端
// 新節點的左右都需要調整
AVLTreeNode nRootR = newRoot.right;
AVLTreeNode nRootL = newRoot.left;
// 串接原本新節點的子樹
child.right = nRootR;
node.left = nRootL;
// 串上新節點的左、右
newRoot.left = child;
newRoot.right = node;
// 兩棵子樹 重新計算高度
child.computeHeight();
node.computeHeight();
return newRoot; // newRoot 會在外部進行運算
}
```
> 照著圖做出程式
>
> 
* **輔助函數**：可以依據上面發現的 **基礎四個狀況** 撰寫出相對應的輔助函數
| `node.diffHeight()` 結果 | 含意 |
| - | - |
| 2 | 左傾斜 |
| -2 | 右傾斜 |
```java=
private AVLTreeNode resolveLeftLeaning(AVLTreeNode node) {
// 判斷傾斜程度
if(node.diffHeight() == 2) {
if(node.left.diffHeight() >= 0) { // 往 "左左" 傾斜
node = rotateRight(node);
} else { // 往 "左右" 傾斜
node = rotateLeftRight(node);
}
}
return node;
}
private AVLTreeNode resolveRightLeaning(AVLTreeNode node) {
// 判斷傾斜程度
if(node.diffHeight() == -2) {
if(node.right.diffHeight() >= 0) { // 往 "右右" 傾斜
node = rotateLeft(node);
} else { // 往 "右左" 傾斜
node = rotateRightLeft(node);
}
}
return node;
}
```
### Insert 使用輔助函數
* 使用 輔助函數 的時機是 **插入 (insert) 後**，在每次插入後都做檢查，並進行調整
```java=
private AVLTreeNode _insert(AVLTreeNode root, int val) {
if(root == null) {
return new AVLTreeNode(val);
}
if(root.val <= val) {
root.right = _insert(root.right, val);
// 可能右傾，嘗試向右調整
root = resolveRightLeaning(root);
} else if(root.val > val) {
root.left = _insert(root.left, val);
// 可能左傾，嘗試向左調整
root = resolveLeftLeaning(root);
}
root.computeHeight();
return root;
}
```
調整後結果
> 
### Remove 使用輔助函數
* 使用 輔助函數 的時機是 **移除 (Remove) 後**，在每次移除後都做檢查 (移除點都需要重新計算是否需要調整，**有 4 個地方需要調整**)，並進行調整
```java=
public AVLTreeNode _remove(AVLTreeNode root, int val) {
if(root == null) {
return null;
}
if(root.val <= val) {
root.right = _remove(root.right, val);
// 插入右邊，可能右偏
root = resolveRightLeaning(root);
} else if(root.val > val) {
root.left = _remove(root.left, val);
// 插入左邊，可能左偏
root = resolveLeftLeaning(root);
} else {
if(root.left == null && root.right == null) {
return null;
}
if(root.right == null) {
return root.left;
}
if(root.left == null) {
return root.right;
}
AVLTreeNode tmp = root;
root = root.right;
while (root != null) {
root = root.left;
}
AVLTreeNode fix = _removeMin(tmp.right); // 移除右子樹中最小
root.left = tmp.left;
root.right = fix;
// 由於移除右邊的某一個節點後，可能導致左傾斜
// 所以計算右邊
root = resolveRightLeaning(root);
}
root.computeHeight();
return root;
}
private AVLTreeNode _removeMin(AVLTreeNode node) {
if(node.left == null) {
return node.right;
}
node.left = _removeMin(node.left);
// 移除右子樹中，左邊的 Node
// 可能導致，右傾斜
node = resolveRightLeaning(node);
return node;
}
```
1. 移除後的結果 (尚未調整)
> 
2. 調整後的結果
> 
## AVL 效能分析
* 每次 AVL 樹插入，**需要旋轉的 Node ++永遠不會超過 1 個++**
* 每次 AVL 樹移除，**需要旋轉的 Node 有多個，++永遠不會超過 log(N) 次旋轉++**
:::success
透過上面兩點可以知道其二元樹仍是 **保持 O(N logN) 的效能**
:::
## Appendix & FAQ
:::info
:::
###### tags: `資料結構`
Sign in with Wallet
Connect another wallet