---
title: 'M-way Search Tree'
disqus: hackmd
---
[TOC]
## M-way Search Tree
* **Def：** Degree $>$ 2，每個 Node 有 m 個 Degree 、 m-1 個 Data
* 在實際應用上，二元搜尋樹因為每個 Node 只能儲存一筆 Data 所以只要資料量一多就會使高度過大
* 為解決高度問題我們要增加每個 Node 裡面的資料，相對的 Links 數量也會增加
* 在 BT 中大的放左、小的放右，而在 M-way ST 中同樣依照 Node 裡 Data 的值域來做區分，如圖所示 (4-Way)
---
### 性質
* 設高度 k 起始點為 1，根據 BT 該 Level 最大 Nodes = $2^{k-1}$
在 M-way Tree 裡 設 Degree = m ，該 Level 最大 Nodes 則為 $m^{k-1}$
* 整顆 Tree 最大 Nodes = $m^{0}$ + $m^{1}$ + ... + $m^{k-1}$
根據等比級數求合：$\dfrac{m^k-1}{m-1}$
* 所有的 Data 數量 = $\dfrac{m^k-1}{m-1}*(m-1)=m^{k}-1$
---
## B-tree of order m
* B Tree 是平衡後 M-way Search Tree 我們使用 order m 表示最大 Degree 數，滿足以下條件
1. **Root** 至少有兩個兒子 $(2$ ~ $m)$
3. 除了 Root 、 External Node 以外其餘 **Node Degree：** $\lceil\dfrac{m}{2}\rceil$ ~ $m$
4. 每個 Node 裡的 **Data 數量：**$\lceil\dfrac{m}{2}\rceil-1$ ~ $(m-1)$
6. 所有的 External Node 皆要在**相同 Level** (平衡重要條件)
設 m = 3
* Root Degree：2~3
* Internal Node Degree：2~3
* Data 數量：1~2
以下兩圖皆符合 B-tree of order 3 定義
```graphviz
graph graphname{
1 [label="10" shape=s]
2 [label="2" shape=s]
3 [label="55,100" shape=s]
4 [label="F" style=dashed shape=s]
5 [label="F" style=dashed shape=s]
6 [label="F" style=dashed shape=s]
7 [label="F" style=dashed shape=s]
8 [label="F" style=dashed shape=s]
1--2 [color=blue label="<10"]
1--3 [color=blue label=">10"]
2--4
2--5
3--6
3--7
3--8
}
```
```graphviz
graph graphname{
11 [label="10,50" shape=s]
12 [label="2" shape=s]
13 [label="33,45" shape=s]
14 [label="F" style=dashed shape=s]
15 [label="F" style=dashed shape=s]
16 [label="F" style=dashed shape=s]
17 [label="F" style=dashed shape=s]
18 [label="F" style=dashed shape=s]
19 [label="123" shape=s]
20 [label="F" style=dashed shape=s]
21 [label="F" style=dashed shape=s]
11--12 [color=blue label=" <10"]
11--13 [color=blue label=" 10~50"]
11--19 [color=blue label=" >50"]
12--14
12--15
13--16
13--17
13--18
19--20
19--21
}
```
---
## Property of B-tree
* 由於一顆 B-tree 的 **Nodes 、 Links 、 Datas** 是允許在範圍內任意更動的，接著就讓我們來探討關於一顆 B-tree 這三個屬性的最大最小值
1. Nodes
* **最大 Nodes** 與 M-way Search Tree 一樣： $\dfrac{m^k-1}{m-1}$
* **最小 Nodes**：由定義中 Root 最少有 2 Child，Internal Node 最少 Degree 為 $\lceil\dfrac{m}{2}\rceil$ 依序乘下去，根據等比級數求合得：$1+2* \left ( \dfrac{\lceil\dfrac{m}{2}\rceil^{k-1}-1}{\lceil\dfrac{m}{2}\rceil-1}\right)$
2. Links，根據 Links = Nodes - 1
* **最大 Links** ： $\dfrac{m^k-1}{m-1}-1$
* **最小 Links** ： $2* \left ( \dfrac{\lceil\dfrac{m}{2}\rceil^{k-1}-1}{\lceil\dfrac{m}{2}\rceil-1}\right)$
5. Data 總數，根據
* **最大 Datas**：$m^{k-1}$
* **最小 Datas**：將最小 Nodes 乘上每個 node 的最小 Datas：$\lceil\dfrac{m}{2}\rceil-1$
得 $[1+2* \left ( \dfrac{\lceil\dfrac{m}{2}\rceil^{k-1}-1}{\lceil\dfrac{m}{2}\rceil-1}\right)]*(\lceil\dfrac{m}{2}\rceil-1)$
---
### Insertion - 插入
* 在插入時依照 Root 的值域，依序找到適合的 Node 插入
* 檢查此 Node 是否 Overflow
* $Datas \leq m-1：無\ overflow$
* $Datas > m-1：\ overflow$，這時我們將進行 **Split (分裂)** 處理
---
#### Spilt - 分裂
1. 將 Node 裡第 $\lceil\dfrac{m}{2}\rceil$ 個 Data 加進該 Node 的 Parent 裡
2. 因為分裂後該 Level Nodes 會多 1，如下圖分裂後變為 4
3. 所以得先檢查分裂前該 Level Nodes + 1 是否比最大 Nodes 還多，
即判斷 2+1 是否 $\leq$ 3
4. 滿足則放置正確位置，不需要 Spilt
```graphviz
graph graphname{
11 [label="最大 Degree 3" shape=s]
12 [label="" shape=s]
13 [label="我要分裂了 (丟一個給 Parent)" shape=s]
11--12 [label=" "]
11--13 [label=" "]
111 [label="最大 Degree 3" shape=s]
121 [label="" shape=s]
131 [label="左" shape=s]
191 [label="右" shape=s]
111--121 [label=" "]
111--131 [label=" "]
111--191 [label=""]
}
```
5. 若超出該 Level Max Nodes 則 Parent 必將分裂，則將分裂後的 Child 先保留之後再按照大小放至分裂後的 Parent
```graphviz
graph graphname{
11 [label="最大 Degree = 3" shape=s]
12 [label="" shape=s]
13 [label="我要分裂了" shape=s]
19 [label="" shape=s]
11--12 [label=" "]
11--13 [label=" "]
11--19 [label=""]
111 [label="Parent 將分裂" shape=s]
121 [label="" shape=s]
131 [label="左" shape=s]
191 [label="右" shape=s]
192 [label="" shape=s]
111--121 [label=" "]
111--192
}
```
> 為何分裂後超出該 Level Max Nodes 則 Parent 也必分裂：
> 假設最大 Degree = 3 ， 某 Level Nodes 有 3 個，代表他的 Parent 已經有了 2 個 Data ( 才能有三種 Data 區隔，<x , x~y , >y )
> 而每個 Node 最大 Data 數 = m-1 = 2，所以加進去後 2+1 > 2 也必定分裂
>
> [time=Wed, May 15, 2019 2:13 PM]
4. Spilt 完再次檢查 Parent Node 是否 Overflow ，否則結束
---
(繼續插入)
* 插入 40 到 B tree of order 3
```graphviz
graph graphname{
11 [label="10,50" shape=s]
12 [label="2" shape=s]
13 [label="33,45" shape=s]
19 [label="123" shape=s]
11--12 [label=" <10"]
11--13 [label=" 10~50"]
11--19 [label=" >50"]
40[color=red]
}
```
* 至適當 Node 插入，發現該 Node Datas > m-1 = 2
```graphviz
graph graphname{
11 [label="10,50" shape=s]
12 [label="2" shape=s]
13 [label="33,40,45" shape=s color=red]
19 [label="123" shape=s]
11--12 [label=" <10"]
11--13 [label=" 10~50"]
11--19 [label=" >50"]
}
```
* 將該 Node 第 $\lceil\dfrac{m}{2}\rceil=2$ 個 Data 放進他的 Parent
而因為分裂後該 Level Nodes = 4 > m = 3 將左右 Data 保存起來等待 Parent 分裂
```graphviz
graph graphname{
11 [label="10,40,50" shape=s color=blue]
12 [label="2" shape=s]
13 [label="33" shape=s color=red]
133 [label="45" shape=s color=red]
19 [label="123" shape=s]
11--12 [label=" <10"]
11--19 [label=" >50"]
}
```
* 將 Parent 進行分裂，因其 Parent 不須分裂直接放置正確位置
```graphviz
graph graphname{
11 [label="10" shape=s color=red]
21 [label="50" shape=s color=red]
12 [label="2" shape=s]
13 [label="33" shape=s]
133 [label="45" shape=s]
19 [label="123" shape=s]
1[label="40" shape=s color=blue]
1--11 [label=" <40"]
1--21 [label=" >40"]
11--12 [label=" <10"]
21--19 [label=" >50"]
}
```
* 將剛剛保存的 Node 放入正確位置
```graphviz
graph graphname{
11 [label="10" shape=s color=blue]
21 [label="50" shape=s color=blue]
12 [label="2" shape=s]
13 [label="33" shape=s color=red]
133 [label="45" shape=s color=red]
19 [label="123" shape=s]
1[label="40" shape=s]
1--11 [label=" <40"]
1--21 [label=" >40"]
11--13 [label=" >10"]
11--12 [label=" <10"]
21--19 [label=" >50"]
21--133 [label=" <50"]
}
```
---
### Deletion - 刪除
* 同插入，依照 Root 的值域，依序找到符合 Data 的 Node
* 而找到的 Node 將分為
1. Leaf Node
2. Non-Leaf Node
#### Leaf Node
1. 刪除位於 Leaf Node 裡的 Data
2. 檢查此 Leaf 是否 Underflow ( $Datas <\lceil\dfrac{m}{2}\rceil-1$ )
* 未 Underflow ，即完成
* 若 Underflow ， 也就是該 Node 的 Datas 低於限制
這時我們將進行 **挨家挨戶**
* 挨家挨戶
1. 判斷左右兄弟是否有足夠的 Datas 可以提出 ( Datas > $\lceil\dfrac{m}{2}\rceil-1$ )
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="3,10" shape=s]
2[label="1,2" shape=s]
3[label="已破產" shape=s]
4[label="11,12" shape=s]
1--2
1--3
1--4
}
```
2. 若選擇左兄弟：將 Parent 最小值移進 Node ，左兄弟最大值放入 Parent
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="2,10" shape=s color=blue]
2[label="1" shape=s color=blue]
3[label="3" shape=s color=red]
4[label="11,12" shape=s]
1--2
1--3
1--4
}
```
3. 若選擇右兄弟：將 Parent 最大值移進 Node ，右兄弟最小值放入 Parent
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="3,11" shape=s color=blue]
2[label="1,2" shape=s]
3[label="10" shape=s color=red]
4[label="12" shape=s color=blue]
1--2
1--3
1--4
}
```
* 尋求 **Parent**：若左右兄弟皆不給力 $Datas < \lceil\dfrac{m}{2}\rceil-1$
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="3,10" shape=s]
2[label="1" shape=s]
3[label="已破產" shape=s]
4[label="11" shape=s]
1--2
1--3
1--4
}
```
由圖可知，若從 Parent 取一個 Data 下來則 Nodes 將會為 3 ，但是此時 Parent 只有一個 Data 並沒辦法有效對其 Child 進行區分，所以我們應該判斷從 Parent 取出來的值是大的還是小的
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="10" shape=s]
2[label="1" shape=s]
3[label="3" shape=s]
4[label="11" shape=s]
1--2[label=" <10"]
1--3[label=" <10"]
1--4[label=" >10"]
}
```
1. 剛剛從 Parent 提出最小值：3 是小的，所以我們應該要將 3 放在 < 10 的 Node
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="10" shape=s color=blue]
2[label="1,3" shape=s color=red]
4[label="11" shape=s]
1--2[label=" <10"]
1--4[label=" >10"]
}
```
2. 相反的從 Parent 提出最大值：10，所以我們應該要將 10 放在 > 3 的 Node
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="3" shape=s color=blue]
2[label="1" shape=s]
4[label="10,11" shape=s color=red]
1--2[label=" <3"]
1--4[label=" >3"]
}
```
* Parent 即將破產
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="3" shape=s]
2[label="1" shape=s]
3[label="已破產" shape=s]
4[label="11" shape=s]
1--2
1--3
1--4
}
```
1. 若 3 為 Root 我們直接合併成一個 Node
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="1,3,11" shape=s]
}
```
2. 若不是 Root 而且他的 Parent 也即將破產，我們將重複上述的尋找其 Sibling、Parent
```graphviz
graph graphname{
label="
B Tree of order 3"
1[label="" shape=s color=blue]
2[label="1" shape=s]
3[label="已破產" shape=s]
4[label="11" shape=s]
5[label="" shape=s color=blue]
6[label="3" shape=s]
7[label="" shape=s color=blue]
5--1
5--6
5--7
6--2
6--3
6--4
}
```
* Parent's Parent 即將破產
1. 承上述，若不幸他的 Parent 也即將破產，
```graphviz
graph graphname{
label="
B Tree of order 3"
2[label="1" shape=s]
3[label="已破產" shape=s]
4[label="11" shape=s]
5[label="20" shape=s color=red]
6[label="3" shape=s]
7[label="100" shape=s]
5--6
5--7
6--2
6--3
6--4
}
```
2. 我們同樣將 3 個 Data 合併在一個 Node 裡，但是我們要將此 Node 放在 Child 的位置，而破產的 Parent 繼續依照上述的方法直到 Root 為止
```graphviz
graph graphname{
label="
B Tree of order 3"
2[label="1" shape=s]
2[label="1,3,11" shape=s color=red]
5[label="20" shape=s]
6[label="已破產" shape=s color=blue]
7[label="100" shape=s]
5--6
5--7
6--2
}
```
---
#### Non-Leaf Node
* 如果我們刪除的不是 Leaf ，則我們將從該 Node 的 **Left / Right Subtree** 取最大、最小值出來補進被刪除的 Node
1. 刪除 50
```graphviz
graph graphname{
11 [label="10" shape=s]
21 [label="50" shape=s color=red]
12 [label="2" shape=s]
13 [label="33" shape=s]
133 [label="45,46" shape=s]
19 [label="123" shape=s]
1[label="40" shape=s]
1--11
1--21
11--13
11--12
21--19
21--133
}
```
2. 50 的左子樹最大值為 46
```graphviz
graph graphname{
11 [label="10" shape=s]
21 [label="" shape=s]
12 [label="2" shape=s]
13 [label="33" shape=s]
133 [label="45,46" shape=s color=red]
19 [label="123" shape=s]
1[label="40" shape=s]
1--11
1--21
11--13
11--12
21--19
21--133
}
```
3. 放上來
```graphviz
graph graphname{
11 [label="10" shape=s]
21 [label="46" shape=s color=red]
12 [label="2" shape=s]
13 [label="33" shape=s]
133 [label="45" shape=s]
19 [label="123" shape=s]
1[label="40" shape=s]
1--11
1--21
11--13
11--12
21--19
21--133
}
```
4. 該 Node 的 Datas 符合定義，不須更動
接著我們刪除 46
```graphviz
graph graphname{
11 [label="10" shape=s]
21 [label="46" shape=s color=red]
12 [label="2" shape=s]
13 [label="33" shape=s]
133 [label="45" shape=s]
19 [label="123" shape=s]
1[label="40" shape=s]
1--11
1--21
11--13
11--12
21--19
21--133
}
```
5. 我們可以將破產的情況視為刪除 Leaf
```graphviz
graph graphname{
11 [label="10" shape=s]
21 [label="45" shape=s]
12 [label="2" shape=s]
13 [label="33" shape=s]
133 [label="破產中" shape=s color=red]
19 [label="123" shape=s]
1[label="40" shape=s]
1--11
1--21
11--13
11--12
21--19
21--133
}
```
6. 最後的 Tree 將會為
```graphviz
graph graphname{
11 [label="10,40" shape=s]
12 [label="2" shape=s]
13 [label="33" shape=s]
19 [label="45,123" shape=s]
11--12 [label="<10"]
11--13 [label=" 10~40"]
11--19 [label=" >40"]
}
```
---
###### tags: `Data Structure`
Sign in with Wallet
Connect another wallet