# Data Struct - Tree : 2-3樹
###### tags: `Data Struct - Tree`

## 一 . 2-3 樹
### (一) . 定義
1. 節點 ： 可以存放2或3個data。
3. 樹葉點必須在同一個level。

### (二) . 性質
1. 性質一 ： 樹是向上長的(比較像是概念)。
2. 性質二 ： 節點的data和node關係。
- 若節點有1個data : 可能有0或2個子。
- 若節點有2個data : 可能有0或3個子。
- 若有0子，則必是樹葉點。
### (三) . 樹高與節點
1. 分析節點 ： 若高為$h$，則節點數為 $2^h-1$ 到 $3^h-1$。
2. 分析高 ： 若樹的節點為 $n$ 個，則高為 $log_3 \ n$ 到 $log_2\ n$。

## 二 . 動態操作 - 加入
### (一) . 遞迴方法
- $Step\ 1$ : 依大小找到leaf，並加入。
- $Step\ 2$ : 若leaf(node)已滿，則分裂成2個，將中間值向父送。
- $Step\ 3$ : 若父已滿，則重複$step2$直到合法。

### (二) . 解釋 ： **分析**leaf分裂的情況
#### 1. sibling=0 : 都不可能。
- $case \ 1$ : sibling=0，parent的data為1 :
- 要變成左圖那樣 ： $x>y$。
- 但不論先加入x或y，都只可能在單節點，不可能雙節點。

- $case \ 2$ : sibling=0，parent的data為2 :
- 要變成左圖那樣 ： $z>x>y$。
- 但不論先加入x或y或z，都只可能形成右圖單節點，不可能雙節點。

#### 2. sibling=1 : parent的data必為1。
- $case\ 1$ : sibling=1，parent的data為1 :
- 任意三個不同的數 ： $z>x>y$加入，都可以形成下圖。

- $case \ 2$: sibling=1，parent的data為2 :
- 必由上面(sibling=1，parent的data為1)變成。
- 但是，由上面推倒可知，不可能。

#### 3. sibling=2 : parent的data必為2。
- $case \ 1$ : sibling=2，parent的data為1 :
- 不可能，因為父節點需要有2個data才可以辨別三個子節點的方位。
- $case \ 2$ : sibling=2，parent的data為2 :
- 由sibling=1，parent的data為1演化而成。

#### 4. 結論 ： 對加入新data時的狀況，可以簡化。
- 對要加入的leaf node和其父的情況，我們可以縮小到兩種狀況。
1. $case\ 1$ : sibling=1 ， parent的data為1。
2. $case\ 2$ : sibling=2 ， parent的data必為2。

### (三) . 情況一 ： sibling=1 ， parent的data為1。
- 重點 ： 只有使得節點這一層與父節點有所變化。
- 情況 ： 分裂的連續行為止於父節點。
- 將data向父節點送。
- 因為父節點只有一個data，所以必會止於此。

### (四) . 情況二 ： sibling=2 ， parent的data必為2。
- 重點 ： 使得節點與所有的祖先層可能有大變化。
- 情形 ： 必會使得父節點也分裂。
- 父節點也分裂下，祖父節點可能也要分類。
- 一層一層的影響下，可能直到只有1data的祖先節點，或直到根節點。
### (五) . 情況三 ： 非樹葉點的split
- 重點 ： 非樹葉點需要再加入時發生split，**表示其子節點必有split，才會給出data，使非樹葉點需要分裂**。
- 情況 ： 非樹葉點的子節點分配，可以依照上圖。
- 視AB節點為非樹葉點。
- 而其分裂時必會滿足4個子節點。

## 三 . 動態操作 - 刪除
### (一) . 遞迴方法
1. $Step\ 1$ : 搜尋要刪除的node。
2. $Step\ 2$ : 若是樹葉點，則辨別是否該事業點只存在一個data。
- 否 ： 直接刪除(刪除仍滿足2-3樹)。
- 是 ： 進行塌縮或旋轉。
3. $Step \ 3$ : 若不是樹葉點，找左子樹最大，或右子樹最小，進行替代。
- 也可以視為刪除樹葉點了。
### (二) . 情況一 ： 樹葉點的data有2個
- 若要刪除的樹葉點有2data下 ： 刪除15這個節點。
- 直接刪除，不影響2-3樹的特性 : 

### (三) . 情況二 ： 旋轉 - 左右兄弟可以提供
- 若要刪除的樹葉點有1data下 ： 刪除33這個節點。
- 向左或右的節點和父節點進行旋轉 ： 向左或右節點借出一個。
- 向左節點借出最大的。
- 向右節點借出最小的。

### (四) . 情況三 ： 塌縮 - 左右兄弟無法提供
- 若要刪除樹葉點只有一個data且無法旋轉下 ： 刪除13下。
- 將父節點的一個資料和左或右的資料一起合併。
- $step \ 1$ : 將父節點的資料和左或右的資料一起移動到節點中。
- $step \ 2$ : 將兄弟節點刪除。
- $step \ 3$ : 若父節點變成空的(父節點可能有2筆dara)，則父節點由step1開始動作。
- 注意 ： step 1的左右兄弟節點的子節點也要一起一到原本節點下方。
- non-leaf node要進行塌縮 ： 其子必定只有一個(其子個數必不合法)。