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

看板Grad-ProbAsk作者jojoboy0115 (その血の運命~Jo~Jo~)時間6年前 (2019/01/27 14:20)推噓8(8推 0噓 10→)

留言18則, 8人參與討論串1/1

先提出疑問 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

01/27 16:52, 6年前 , 1^F

01/27 16:52, 1^F

推

Voicer

01/27 17:38, 6年前 , 2^F

01/27 17:38, 2^F

推

Voicer

01/27 17:40, 6年前 , 3^F

01/27 17:40, 3^F