# [資料結構] CH10. Multi-way Search Trees

## M-way search trees
* 在Binary search Tree中，每個node都只會有一個data和兩個pointer。
* 而在M-way search tree的**中，每個node則是有`M-1`個data和`M`個pointer。
* `M`被稱作是這棵M-way search tree的*degree*
* 如果M=2，這顆M-way search tree就等於Binary Search Tree。

digraph Multiway
{	
    label="3-way search tree"
	node[shape=record]
	node1 [label="<f0>●|<f1>18|<f2>●|<f3>45|<f4>●"];
    node2 [label="<f0>●|<f1>9|<f2>●|<f3>11|<f4>●"];
    node3 [label="<f0>●|<f1>27|<f2>●|<f3>36|<f4>●"];
    node4 [label="<f0>●|<f1>54|<f2>●|<f3>63|<f4>●"];
    node5 [label="<f0>●|<f1>29|<f2>●|<f3>30|<f4>●"];
    node6 [label="<f0>●|<f1>72|<f2>●|<f3>81|<f4>●"];
    node1:f0->node2
    node1:f2->node3
    node1:f4->node4
    node3:f2->node5
    node4:f4->node6
    }

* 在每個node中的data，必須按照大小排序。
* 同Binary search Tree，對於每個data `D`，`D`的leftpointer所指向的node中所有data必須小於`D`；rightpointer則反之。
* M-way search tree並不嚴格規定每個node都必須擁有`M-1`筆data。
* 任何一個node的data數可以是`1`~`M-1`。

## B Trees
* B Tree是M-way search tree的一種，但它對於node中的data限制更多。
* 和M-way search tree一樣，一棵degree=`M`的B Tree，每個node最多可擁有`M-1`筆data和`M`個pointer。
* 有些地方定義為 order 而非 degree，請注意自身學習時教學書的用詞。
* 感謝 **skysoul1024** 告知。
* 然而，除了root和leaf之外的所有node，必須至少擁有$\left \lceil \frac{M}{2} \right \rceil$個小孩(pointer)。
* Degree=4,至少有兩個小孩，一筆data。
* Degree=5,至少有三個小孩，兩筆data。
* root至少有兩個小孩。
* 所有葉子必須要在同一個level(同一高度)。

digraph BTree
{	
    label="B Tree, Degree=4"
	node[shape=record]
	node1 [label="<f0>●|<f1>45|<f2>●"];
    node2 [label="<f0>●|<f1>29|<f2>●|<f3>32|<f4>●"];
    node3 [label="<f0>●|<f1>49|<f2>●|<f3>63|<f4>●"];
    node4 [label="<f0>●|<f1>18|<f2>●|<f3>27|<f4>●"];
    node5 [label="<f0>●|<f1>30|<f2>●|<f3>31|<f4>●"];
    node6 [label="<f0>●|<f1>36|<f2>●|<f3>39|<f4>●"];
    node7 [label="<f0>●|<f1>46|<f2>●|<f3>47|<f4>●"];
    node8 [label="<f0>●|<f1>54|<f2>●|<f3>59|<f4>●|<f5>61|<f6>●"];
    node9 [label="<f0>●|<f1>67|<f2>●|<f3>72|<f4>●"];
    node1:f0->node2
    node1:f2->node3
    node2:f0->node4
    node2:f2->node5
    node2:f4->node6
    node3:f0->node7
    node3:f2->node8
    node3:f4->node9
    }

### 搜尋

在B Tree中搜尋n
1.從root開始，檢查數字n是否在該node中。
2.如果在該node找不到，找出n介於哪兩個數a,b之間，改為拜訪a,b之間的pointer指向的node。
3.若拜訪到的node為NULL，表示找不到該數字。

* 在剛剛的範例中搜尋`59`：

digraph BTree
{	
    label="B Tree, Degree=4"
	node[shape=record]
	node1 [label="<f0>●|<f1>45|<f2>●"];
    node2 [label="<f0>●|<f1>29|<f2>●|<f3>32|<f4>●"];
    node3 [label="<f0>●|<f1>49|<f2>●|<f3>63|<f4>●"];
    node4 [label="<f0>●|<f1>18|<f2>●|<f3>27|<f4>●"];
    node5 [label="<f0>●|<f1>30|<f2>●|<f3>31|<f4>●"];
    node6 [label="<f0>●|<f1>36|<f2>●|<f3>39|<f4>●"];
    node7 [label="<f0>●|<f1>46|<f2>●|<f3>47|<f4>●"];
    node8 [label="<f0>●|<f1>54|<f2>●|<f3>59|<f4>●|<f5>61|<f6>●"];
    node9 [label="<f0>●|<f1>67|<f2>●|<f3>72|<f4>●"];
    node1:f0->node2
    node1:f2->node3
    node2:f0->node4
    node2:f2->node5
    node2:f4->node6
    node3:f0->node7
    node3:f2->node8
    node3:f4->node9
    }

1.`59`比`45`大，拜訪右子樹
2.`59`介於`49`和`63`之間，拜訪中間那個node。
3.找到`59`ㄌ。

## 插入
* 在B Tree加入新的data時，一定是先放在leaf的地方，如果容量爆了再做處理。
* 一般的Binary Search Tree是向下長，而B Tree是向上長的。

1.尋找data應該被放在哪個葉子。
2.如果葉子還沒滿，放入後結束。
3.如果葉子滿了：
    a)先把它大力地硬插進去這個node。
    b)找到中間值，拆成左邊的node和右邊的node，並把中間值上提拿給老爸。
    c)上提後的中間值，左pointer值向剛剛左邊的node，右邊同理。
    d)因為老爸多了一個data，檢查老爸有沒有滿(遞迴步驟2or3)。

---

* 範例1：在下面這棵B Tree中加入`4`。
* degree=5

digraph BTree
{	
	node[shape=record]
	node1 [label="<f0>●|<f1>18|<f2>●|<f3>45|<f4>●|<f5>72|<f6>●"];
    node2 [label="<f0>●|<f1>7|<f2>●|<f3>8|<f4>●|<f5>9|<f6>●|<f7>11|<f8>●"];
    node3 [label="<f0>●|<f1>21|<f2>●|<f3>27|<f4>●|<f5>36|<f6>●|<f7>42|<f8>●"];
    node4 [label="<f0>●|<f1>54|<f2>●|<f3>63|<f4>●"];
    node5 [label="<f0>●|<f1>81|<f2>●|<f3>89|<f4>●|<f5>90|<f6>●"];
    node1:f0->node2
    node1:f2->node3
    node1:f4->node4
    node1:f6->node5
}

* 先硬把`4`加進去。

digraph BTree
{	
	node[shape=record]
	node1 [label="<f0>●|<f1>18|<f2>●|<f3>45|<f4>●|<f5>72|<f6>●"];
    node2 [label="<f-1>4|<f0>●|<f1>7|<f2>●|<f3>8|<f4>●|<f5>9|<f6>●|<f7>11|<f8>●"];
    node3 [label="<f0>●|<f1>21|<f2>●|<f3>27|<f4>●|<f5>36|<f6>●|<f7>42|<f8>●"];
    node4 [label="<f0>●|<f1>54|<f2>●|<f3>63|<f4>●"];
    node5 [label="<f0>●|<f1>81|<f2>●|<f3>89|<f4>●|<f5>90|<f6>●"];
    node1:f0->node2
    node1:f2->node3
    node1:f4->node4
    node1:f6->node5
}

* 容量爆了，將中間值`8`往上提，並拆成左右並將指標指向正確位置。

digraph BTree
{	
	node[shape=record]
	node1 [label="<n2>●|<n1>8|<f0>●|<f1>18|<f2>●|<f3>45|<f4>●|<f5>72|<f6>●"];
    node2a [label="<n2>●|<n1>4|<f0>●|<f1>7|<f2>●"];
    node2b [label="<f4>●|<f5>9|<f6>●|<f7>11|<f8>●"];
    node3 [label="<f0>●|<f1>21|<f2>●|<f3>27|<f4>●|<f5>36|<f6>●|<f7>42|<f8>●"];
    node4 [label="<f0>●|<f1>54|<f2>●|<f3>63|<f4>●"];
    node5 [label="<f0>●|<f1>81|<f2>●|<f3>89|<f4>●|<f5>90|<f6>●"];
    node1:n2->node2a
    node1:f0->node2b
    node1:f2->node3
    node1:f4->node4
    node1:f6->node5
}

* 完成。

---

* 範例2：再加入`20`。
* 一樣先硬塞入`20`。

digraph BTree
{	
	node[shape=record]
	node1 [label="<n2>●|<n1>8|<f0>●|<f1>18|<f2>●|<f3>45|<f4>●|<f5>72|<f6>●"];
    node2a [label="<n2>●|<n1>4|<f0>●|<f1>7|<f2>●"];
    node2b [label="<f4>●|<f5>9|<f6>●|<f7>11|<f8>●"];
    node3 [label="<n2>●|<n1>20|<f0>●|<f1>21|<f2>●|<f3>27|<f4>●|<f5>36|<f6>●|<f7>42|<f8>●"];
    node4 [label="<f0>●|<f1>54|<f2>●|<f3>63|<f4>●"];
    node5 [label="<f0>●|<f1>81|<f2>●|<f3>89|<f4>●|<f5>90|<f6>●"];
    node1:n2->node2a
    node1:f0->node2b
    node1:f2->node3
    node1:f4->node4
    node1:f6->node5
}

* 中間值`27`往上提，拆左右。

digraph BTree
{	
	node[shape=record]
	node1 [label="<n2>●|<n1>8|<f0>●|<f1>18|<f2>●|<f3>27|<f4>●|<f5>45|<f6>●|<f7>72|<f8>●"];
    node2a [label="<n2>●|<n1>4|<f0>●|<f1>7|<f2>●"];
    node2b [label="<f4>●|<f5>9|<f6>●|<f7>11|<f8>●"];
    node3a [label="<n2>●|<n1>20|<f0>●|<f1>21|<f2>●"];
    node3b [label="<f4>●|<f5>36|<f6>●|<f7>42|<f8>●"];
    node4 [label="<f0>●|<f1>54|<f2>●|<f3>63|<f4>●"];
    node5 [label="<f0>●|<f1>81|<f2>●|<f3>89|<f4>●|<f5>90|<f6>●"];
    node1:n2->node2a
    node1:f0->node2b
    node1:f2->node3a
    node1:f4->node3b
    node1:f6->node4
    node1:f8->node5
}

* 上提後變成爸爸爆炸，只好換爸爸上提拆左右。

digraph BTree
{	
	node[shape=record]
    node0[label="<f0>●|<f1>27|<f2>●"];
	node1a [label="<n2>●|<n1>8|<f0>●|<f1>18|<f2>●"];
    node1b [label="<f4>●|<f5>45|<f6>●|<f7>72|<f8>●"];
    node2a [label="<n2>●|<n1>4|<f0>●|<f1>7|<f2>●"];
    node2b [label="<f4>●|<f5>9|<f6>●|<f7>11|<f8>●"];
    node3a [label="<n2>●|<n1>20|<f0>●|<f1>21|<f2>●"];
    node3b [label="<f4>●|<f5>36|<f6>●|<f7>42|<f8>●"];
    node4 [label="<f0>●|<f1>54|<f2>●|<f3>63|<f4>●"];
    node5 [label="<f0>●|<f1>81|<f2>●|<f3>89|<f4>●|<f5>90|<f6>●"];
    node0:f0->node1a
    node0:f2->node1b
    node1a:n2->node2a
    node1a:f0->node2b
    node1a:f2->node3a
    node1b:f4->node3b
    node1b:f6->node4
    node1b:f8->node5
}

* 完成。

## 刪除
* 刪除在B Tree裡面就有點麻煩了。
* 我們分成兩種情形來討論：
* 刪除的值不是在葉子(internal node)。
* 刪除的值在葉子(leaf node)。

### Internal Node
* 當刪除的值不在葉子上時，我們先直接將值刪除，然後找**左子樹最大值**代替原來的位置。
* 因為左子樹最大值被拿走了，因此情況就變成了下方的**刪除葉節點**了。

### Leaf node
* 葉節點要考慮的情形就有點多了：

1.判斷data數是否低於下限，如果沒有，結束。
2.如果左右兄弟的data數量夠，向和左右的兄弟節點借值來補：
    a1)左邊的情形：先找到父親哪個pointer指向自己，將該pointer左邊的data放下來，並將左節點最大值向上推給父親取代。
    a2)右邊的情形：先找到父親哪個pointer指向自己，將該pointer右邊的data放下來，並將右節點最小值向上推給父親取代。
3.如果兄弟都沒辦法借，只好向父親求救，一樣方為左右兩左情形：
    a1)左邊的情形：先找到父親哪個pointer指向自己，將該pointer左邊的data放下來，然後將自己和左兄弟兩個node合併。
    a2)右邊的情形：先找到父親哪個pointer指向自己，將該pointer右邊的data放下來，然後將自己和右兄弟兩個node合併。
    b)因為老爸被拿走一個data，回到步驟1但改為確認老爸的節點情況並做處理。

* 簡單版：

1.刪完沒事就沒事。
2.有事向兄弟求救。
3.兄弟救不了找老爸救。
4.老爸刪完沒事就沒事。
5.老爸有事向老爸的兄弟求救。
6.老爸的兄弟救不了找老爸的老爸。
7.LOOP

* 因為該部分步驟過多，用圖片很亂也很累，請參閱下方**其他資源**的部分。

## 其他資源
* [B Tree模擬網頁](https://www.cs.usfca.edu/~galles/visualization/BTree.html)
* 如果不想要手刻一次B Tree，一定要玩玩這個網頁！對插入和刪除的理解都很有幫助。
* 內含動畫，如太快可調整下方**Animation Speed**更改速度。
* [台科大 陳冠宇老師 上課講義](http://faculty.csie.ntust.edu.tw/~kychen/courses/2018_Fall_DS/2018-10-24%20Multi-way%20Search%20Trees.pdf)
* 內含大量例子+圖片，可幫助思考。

###### tags: `DS` `note`