---
# System prepended metadata

title: 'Data Struct - Tree :     2-3樹'
tags: [Data Struct - Tree]

---

# 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，都只可能在單節點，不可能雙節點。  
![](https://i.imgur.com/d4F1bXk.png =200x)![](https://i.imgur.com/LxuBrif.png =200x)

- $case \ 2$ : sibling=0，parent的data為2 : 
   - 要變成左圖那樣 ： $z>x>y$。
   - 但不論先加入x或y或z，都只可能形成右圖單節點，不可能雙節點。  
![](https://i.imgur.com/SUrbODD.png =200x)![](https://i.imgur.com/PvE6f06.png =200x)

#### 2. sibling=1 : parent的data必為1。
- $case\ 1$ : sibling=1，parent的data為1 : 
  - 任意三個不同的數 ： $z>x>y$加入，都可以形成下圖。 
![](https://i.imgur.com/W3kWQ70.png =300x)

- $case \ 2$: sibling=1，parent的data為2 : 
  - 必由上面(sibling=1，parent的data為1)變成。
  - 但是，由上面推倒可知，不可能。 
![](https://i.imgur.com/XFaB0JR.png =300x)

#### 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演化而成。
![](https://i.imgur.com/J7MbRrn.png =300x)
![](https://i.imgur.com/v0KG7h9.png =300x)

#### 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，所以必會止於此。 
![](https://i.imgur.com/J7MbRrn.png =300x)
![](https://i.imgur.com/v0KG7h9.png =300x)

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


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

### (三) . 情況二 ： 旋轉 - 左右兄弟可以提供
- 若要刪除的樹葉點有1data下 ： 刪除33這個節點。
![](https://i.imgur.com/iMpUzwW.png =450x)
- 向左或右的節點和父節點進行旋轉 ： 向左或右節點借出一個。
  - 向左節點借出最大的。
  - 向右節點借出最小的。 
![](https://i.imgur.com/SR8pn8r.png =450x)

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

