[理工] 2-3 Tree以及2-3-4 Tree的Insertion

[jojoboy0115 (その血の運命~Jo~Jo~)]

先提出疑問

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1486893104.A.3B6.html

還是...這些問題都不存在?  我哪邊又想錯惹@@
請各位大大開導一下...



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.233.83.128
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548570005.A.531.html
推 aeiou335: 3. 看維基百科 兩個做法不一樣吧
推 Voicer: 1.2-3 A/2-3-4 B
推 Voicer: 2.D
→ Voicer: 234屬於最後再做插入，23屬於先插入
→ alen0303: 採(A)+(C)法可以選出BD為答案
→ alen0303: 答案有確定是AB還是BD嗎?
推 alen0303: 啊 題目要求用top-down insert 那應該是AB沒錯了
答案是AB沒錯
推 ming173899: 2-3-4tree
→ ming173899: Bottom-up是先插入後在split
→ ming173899: Top-down好像是搜索路徑上等於四就會先split
→ ming173899: 不過我也不知道2-3 tree Bottom-up和Top-down的差別
幾乎都是Top-down
總結來說就是2-3 跟 2-3-4 做法不一樣...
這樣我知道了~感謝各位~
※ 編輯: jojoboy0115 (36.233.83.128), 01/27/2019 22:37:29
推 ekids1234: 真的有先插在split作法嗎QQ 這樣會不懂四個誰該上去..
→ jojoboy0115: 因為2-3 是用先插入再Split，所以我一開始做2-3-4也
→ jojoboy0115: 是用同樣的方法，卻沒有答案，爬文後才知道有其他做
→ jojoboy0115: 法@@
推 eatagary: 台大 2-3樹 那題 題目有問題，用top-down會畫不出來，
→ eatagary: 市面解答都是用 bottom up解法，解這題。
推 ko330: 2 3 tree是不是沒有top-down阿都找不到資料..