---
# System prepended metadata

title: 'Data Struct - Tree : ALV Tree'
tags: [Data Struct - Tree]

---

# 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為左的左。
   ![](https://i.imgur.com/ny2nGul.png =250x) 
   - step 1 : 將x取代n的位置。
   ![](https://i.imgur.com/OeHPRxp.png =300x)
   - step 2 : x的右節點給n的左節點。
    ![](https://i.imgur.com/yW8ly79.png =300x)
   - step 3 : 將x的右節點改為指向n。
    ![](https://i.imgur.com/BsBp0iG.png =250x)
   - 註 ： 最後要重新計算整個樹的$BF$值。

### (二) . RR型
#### 1. 定義 ： 
   - 若 ： 某一節點m的加入，造成n節點平衡因子的不合法。
   - 則 ： 且m在n的右子的右子方。
  
#### 2. 抽象方法 ： 目標即保持BST特性，平衡因子特性。
   - 設 ： n為不平衡節點，x為其右子，y為右的右。
 ![](https://i.imgur.com/FBR1wlX.png =250x)
   - step 1 : 將x取代n的位置。
   ![](https://i.imgur.com/aZ6auWA.png =300x)
   - step 2 : x的左節點給n的右節點。
    ![](https://i.imgur.com/1YQBJ6M.png =300x)
   - step 3 : 將x的左節點改為指向n。
    ![](https://i.imgur.com/tRPNFPr.png =250x)
   - 註 ： 最後要重新計算整個樹的$BF$值。

### (三) . LR型
#### 1. 定義 ： 
   - 若 ： 某一節點m的加入，造成n節點平衡因子的不合法。
   - 則 ： 且m在n的左子的右子方。
  
#### 2. 抽象方法 ： 目標即保持BST特性，平衡因子特性。
   - 設 ： n為不平衡節點，x為其左子，y為左的右。
    ![](https://i.imgur.com/LnlRbn3.png =250x)
   - step 1 : 將y取代n的位置。
    ![](https://i.imgur.com/8bm3NTA.png =300x)
   - step 2 : y的左節點給x的右節點 ; 將y的右節點給n的左節點。
      ![](https://i.imgur.com/8SEYH5e.png =300x)
   - step 3 : y的左節點指向x，y的右節點指向n。
    ![](https://i.imgur.com/6AisGbW.png =300x)
   - 註 ： 最後要重新計算整個樹的$BF$值。

### (四) . RL型
#### 1. 定義 ： 
   - 若 ： 某一節點m的加入，造成n節點平衡因子的不合法。
   - 則 ： 且m在n的右子的左子方。
  
#### 2. 抽象方法 ： 目標即保持BST特性，平衡因子特性。
   - 設 ： n為不平衡節點，x為其右子，y為右的左。
    ![](https://i.imgur.com/lO7hACT.png =250x)
   - step 1 : 將y取代n的位置。
       ![](https://i.imgur.com/NxuaQGy.png =300x)
   - step 2 : y的左節點給n的右節點 ; 將y的右節點給x的左節點。
       ![](https://i.imgur.com/csvCzug.png =300x)
   - step 3 : y的左節點指向n，y的右節點指向x。
       ![](https://i.imgur.com/YAB38Nf.png =300x)
   - 註 ： 最後要重新計算整個樹的$BF$值。
   

##  四 .  證明性質 - 加入    

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

- $轉換後$ :  
   - 原本$j$的區域 ： 變$j+1=i$。
   - 原本$i$的區域 ： 變$i+1-1=i$。
   - 對取代$n$的$x$節點 ： $BF(x)=0$。
![](https://i.imgur.com/YPsdsS5.png)

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

![](https://i.imgur.com/zfctKBo.png =500x)
![](https://i.imgur.com/ECABwHs.png =500x)

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

