# Data Struct - Tree : 2-3-4樹
###### tags: `Data Struct - Tree`
## 一 . 2-3-4樹
### (一) . 定義
1. 節點 ： 可以存放2-4個data。
2. 樹葉點必須在同一個level。

### (二) . 性質
1. 性質一 ： 樹是向上長的(比較像是概念)。
2. 性質二 ： 節點的data和node關係。
- 若節點有1個data : 可能有0或2個子。
- 若節點有2個data : 可能有0或3個子。
- 若節點有3個data : 可能有0或4個子。
- 若有0子，則必是樹葉點。

### (三) . 樹高與節點
1. 分析節點 ： 若高為$h$，則節點數為 $2^h-1$ 到 $4^h-1$。
2. 分析高 ： 若樹的節點為 $n$ 個，則高為 $log_4 \ n$ 到 $log_2\ n$。

## 二 . 動態操作 - 加入
### (一) . 方法
- $Step \ 1$ : 開始尋找需要加入的node，且一路上若有遇到3data的node，就分裂。
- 只管尋找的路徑，附近有3data的也不管。
- $Step \ 2$ : 依照大小找到可以的leaf。
- $Step \ 3$ : 若leaf也是3data，加入後split。

### (二) . 解釋
#### 1. 優化 ： $step\ 1$的優點
- 性質一 ： 可以使除了root外每一個node在split的時候，其父節點必只有1或2個data。
- 性質二 ： 由上可以知道，除了root之外的分裂，都不會造成高度變化。
- 優點 ： 可以造成2-3-4樹的加入，只需要1pass。
#### 2. 比較 : 和2-3樹比較

### (三) . 情況一 ： 父節點為1個data。
- $Case \ 1$ : 本身為3data時。
1. 方法 ： 將中間的data丟上去，再分裂成兩個。
2. 必不會影響樹高 ： 因為此的父為1data，只有2child，多一data和child不影響。

- $Case \ 2$: 本身為4data時。
1. 方法 ： 將中間的data丟上去(4/2=2，第二個)，再分裂成兩個。
2. 必不會影響樹高 ： 因為此的父為1data，只有2child，多一data和child不影響。
3. **加入的node為樹葉點，不用管子節點分配**。

### (四) . 情況二 ： 父節點為2個data。
- $Case \ 1$ : 本身為3data時。
1. 方法 ： 將中間的data丟上去，再分裂成兩個。
2. 必不會影響樹高 ： 因為此的父為2data，只有3child，多一data和child不影響。

- $Case \ 2$: 本身為4data時。
1. 方法 ： 將中間的data丟上去(4/2=2，第二個)，再分裂成兩個。
2. 必不會影響樹高 ： 因為此的父為2data，只有3child，多一data和child不影響。
3. **加入的node為樹葉點，不用管子節點分配**。

### (五) . 情況三 ： 父節點為root時

## 三 . 動態操作
### (一) . 遞迴方法
- $Step \ 1$ : 開始尋找需要加入的node，且一路上若有遇到2data的node，就旋轉或塌縮。
- 只有樹根可以是2data。
- 只管尋找的路徑，附近有3data的也不管。
- $Step \ 2$ : 依照大小找到可以的leaf。
- $Step \ 3$ : 若leaf也是2data，先旋轉或塌縮，在刪除。

### (二) . 解釋
#### 1. 優化 ： 由$step \ 1$和$step\ 3$可以知道
- 性質一 ： 可以使除了root外每一個node在旋轉或塌縮的時候，其父節點必超過1個data。
- 性質二 ： 由上可以知道，除了root中data的刪除，都不會造成高度變化。
- 性質三(step3) ： 刪除時節點data必大於2個，不會造成刪除變0個。
- 優點 ： 可以造成2-3-4樹的刪除，只需要1pass。

### (三) . 情況一 ： 父節點為2data時
- $case \ 1$ : 旋轉
1. 方法 ： 若兄弟節點有大於1個data，借出一個。
2. 必不會影響樹高 ： 因為此的父為2data，旋轉後，不影響樹高。

- $case \ 2$ : 塌縮
1. 方法 ： 若兄弟節點有大於1個data，向父借出一個，並和兄弟合併。
2. 必不會影響樹高 ： 因為此的父為2data，塌縮後至少還有一個，不影響樹高。

### (四) . 情況二 ： 父節點為3data時
- $case \ 1$ : 旋轉
1. 方法 ： 若兄弟節點有大於1個data，借出一個。
2. 必不會影響樹高 ： 因為此的父為2data，旋轉後，不影響樹高。

- $case \ 2$ : 塌縮
1. 方法 ： 若兄弟節點有大於1個data，向父借出一個，並和兄弟合併。
2. 必不會影響樹高 ： 因為此的父為2data，塌縮後至少還有一個，不影響樹高。