作者jojoboy0115 (その血の運命~Jo~Jo~)
看板Grad-ProbAsk
標題[理工] 2-3 Tree以及2-3-4 Tree的Insertion
時間Sun Jan 27 14:20:03 2019
先提出疑問
1.請問2-3或者2-3-4 Overflow 是怎麼判斷?
(A)在插入後，檢查是否Overflow，才Split
(B)在插入前，就把所經過的 Node 都先Split(後面有例子)
有點像是紅黑樹若經過有兩個紅子點，要先 Color change
2.要往父點拉的值是怎麼選擇?
(C)在插入對應的順序後，才開始找
假設2-3-4 Tree現在有{13,14,15}，Insert(12)後，{12,13,14,15}overflow，
選擇{13}上去父點，{12}、{14,15}當子點
(D)在插入前，先Split，選{14}上去當父點，{12,13}、{15} 當子點
3.2-3 Tree 跟 2-3-4 Tree 的Insertion 本來就不一樣嗎?
直接來看題目，這題2-3 Tree是用(A)+(C)
看前三個數字 10 9 8就好
當8插入後，發現Overflow，選擇第二個值 9 往上拉
https://i.imgur.com/RJYDiuW.jpg
https://i.imgur.com/Pw0JUJH.jpg
再來是這題2-3-4 Tree
106台大電機丙的資料結構
要採用(B)+(D)才有答案...
https://i.imgur.com/CHseQQu.jpg
http://i.imgur.com/70KGZUq.jpg
轉自yorunohoshi大大的圖片
在插入12之前，就先Split了，就是我上面的例子
可以看這篇文章下面的討論
https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1486893104.A.3B6.html
還是...這些問題都不存在? 我哪邊又想錯惹@@
請各位大大開導一下...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.233.83.128
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548570005.A.531.html
1F：推 aeiou335: 3. 看維基百科 兩個做法不一樣吧 01/27 16:52
2F：推 Voicer: 1.2-3 A/2-3-4 B 01/27 17:38
3F：推 Voicer: 2.D 01/27 17:40
4F：→ Voicer: 234屬於最後再做插入，23屬於先插入 01/27 17:41
5F：→ alen0303: 採(A)+(C)法可以選出BD為答案 01/27 19:11
6F：→ alen0303: 答案有確定是AB還是BD嗎? 01/27 19:11
7F：推 alen0303: 啊 題目要求用top-down insert 那應該是AB沒錯了 01/27 19:22
答案是AB沒錯
8F：推 ming173899: 2-3-4tree 01/27 20:28
9F：→ ming173899: Bottom-up是先插入後在split 01/27 20:28
10F：→ ming173899: Top-down好像是搜索路徑上等於四就會先split 01/27 20:28
11F：→ ming173899: 不過我也不知道2-3 tree Bottom-up和Top-down的差別 01/27 20:30
幾乎都是Top-down
總結來說就是2-3 跟 2-3-4 做法不一樣...
這樣我知道了~感謝各位~
※ 編輯: jojoboy0115 (36.233.83.128), 01/27/2019 22:37:29
12F：推 ekids1234: 真的有先插在split作法嗎QQ 這樣會不懂四個誰該上去.. 01/27 22:47
13F：→ jojoboy0115: 因為2-3 是用先插入再Split，所以我一開始做2-3-4也 01/27 23:06
14F：→ jojoboy0115: 是用同樣的方法，卻沒有答案，爬文後才知道有其他做 01/27 23:06
15F：→ jojoboy0115: 法@@ 01/27 23:06
16F：推 eatagary: 台大 2-3樹 那題 題目有問題，用top-down會畫不出來， 01/28 00:17
17F：→ eatagary: 市面解答都是用 bottom up解法，解這題。 01/28 00:17
18F：推 ko330: 2 3 tree是不是沒有top-down阿都找不到資料.. 01/28 17:38