# Data Struct - Tree : ALV Tree
###### tags: `Data Struct - Tree`

## 一 . ALV Tree
### (一) . 定義
1. 定義一 ： 樹高的要求。
- 若 ： 每一個節點的左子樹高為$h_L$，右子樹高為$h_R$，
- 則 ： $|h_L-h_R|≦1$。
2. 定義二 ： 遞迴要求
- 若 ： 每一個節點滿足定義一。
- 則 ： 其左右子節點也滿足定義一。

### (二) . 性質
1. 性質一 ： 滿足二元搜尋樹(BST)。
2. 性質二 : 滿足平衡因子。
- 定義 ： $BF(x)$為x節點的平衡因子為何。
- 平衡因子 ： $h_L-h_R$，可以知道平衡因子必須是$-1、0、1$。

## 二 . 動態操作 - 搜尋
### (一) . 概念
### (二) . 實作

## 三 . 動態操作 - 加入
### 前言
### (一) . LL型
#### 1. 定義 ：
- 若 ： 某一節點m的加入，造成n節點平衡因子的不合法。
- 則 ： 且m在n的左子的左子方。

#### 2. 抽象方法 ： 目標即保持BST特性，平衡因子特性。
- 設 ： n為不平衡節點，x為其左子，y為左的左。
- step 1 : 將x取代n的位置。
- step 2 : x的右節點給n的左節點。
- step 3 : 將x的右節點改為指向n。
- 註 ： 最後要重新計算整個樹的$BF$值。

### (二) . RR型
#### 1. 定義 ：
- 若 ： 某一節點m的加入，造成n節點平衡因子的不合法。
- 則 ： 且m在n的右子的右子方。

#### 2. 抽象方法 ： 目標即保持BST特性，平衡因子特性。
- 設 ： n為不平衡節點，x為其右子，y為右的右。
- step 1 : 將x取代n的位置。
- step 2 : x的左節點給n的右節點。
- step 3 : 將x的左節點改為指向n。
- 註 ： 最後要重新計算整個樹的$BF$值。

### (三) . LR型
#### 1. 定義 ：
- 若 ： 某一節點m的加入，造成n節點平衡因子的不合法。
- 則 ： 且m在n的左子的右子方。

#### 2. 抽象方法 ： 目標即保持BST特性，平衡因子特性。
- 設 ： n為不平衡節點，x為其左子，y為左的右。
- step 1 : 將y取代n的位置。
- step 2 : y的左節點給x的右節點 ; 將y的右節點給n的左節點。
- step 3 : y的左節點指向x，y的右節點指向n。
- 註 ： 最後要重新計算整個樹的$BF$值。

### (四) . RL型
#### 1. 定義 ：
- 若 ： 某一節點m的加入，造成n節點平衡因子的不合法。
- 則 ： 且m在n的右子的左子方。

#### 2. 抽象方法 ： 目標即保持BST特性，平衡因子特性。
- 設 ： n為不平衡節點，x為其右子，y為右的左。
- step 1 : 將y取代n的位置。
- step 2 : y的左節點給n的右節點 ; 將y的右節點給x的左節點。
- step 3 : y的左節點指向n，y的右節點指向x。
- 註 ： 最後要重新計算整個樹的$BF$值。

## 四 . 證明性質 - 加入

### (一) . 問題
##### 知道ALV樹後會有兩個問題
- 若加入一個節點，會造成多個祖先節點的平衡因子不合法，要怎麼改。
- 承上，若有多個節點不合法，只改一個可以使整個樹合法？，
### (二) . 證明
- 前提 ： 以LL為例，加入$new$後，不平衡。
- $n$為不平衡節點，$x$為其左子，$y$為左的左。
- $i$為加入方的高度，$j$為另一方的高度。
- $轉換前$ : 造成不合法的加入節點m所在的子樹，**必定是不合法節點n子樹中本來就較高的**。。
- 加入前 $|i - j|≦1$ ： $i$高$j$一單位，或等高，或$j$高$i$一單位。
- 加入後 $|i+1 - j|=2$ ： $i$高$j$一單位。

- $轉換後$ :
- 原本$j$的區域 ： 變$j+1=i$。
- 原本$i$的區域 ： 變$i+1-1=i$。
- 對取代$n$的$x$節點 ： $BF(x)=0$。

- 對祖先節點 ：
- 轉換前 ： 原本$|i-k|≦1$，現在為$|i+1-k|≦2$。
- 轉換後 ： 原本$|i+1-k|≦2$，現在為$|i-k|≦1$。


### (三) . 結論
- $Point\ 1$ : m所在的n子樹，原本必大於另一個子樹1單位的高度。
- $Point\ 2$ : 所有的轉換行為都是為了使n變成$BF(n)=0$。
- $Point\ 3$ : 加入後n的祖先節點可能$BF$值不合法，但n一轉換後，變回原來的$BF$值。