作者wolfswolfs (wolf)
看板Grad-ProbAsk
標題Re: [理工] [資結]2-3 Tree的老問題!!!
時間Fri Jan 28 22:09:53 2011
應該是說，delete 15的話，只有13.15.18這顆子樹會變動，不能動用到7.8.11這邊的資料
所以，
: 有一2-3 tree如下:
: 19.35
: / | \
: 11.15 25 42
: / | \ / \ / \
: 7.8 13 18 24 27.30 39 46
結果:
: 19.35
: / | \
: 11 25 42
: / \ / \ / \
: 7 13.18 24 27.30 39 46
這樣才是對的，也就是說，因為15空了的緣故，13跟18必須合併
至於結果對不對，你可以自己再insetr 15試試，看是不是跟原來一樣
Case 2
: 19.35
: / | \
: 8.13 27 42
: / | \ / \ / \
: 7 11 18 25 30 39 46
: 19
: / \
: 8.13 35.42
: / | \ / | \
: 7 11 18 27.30 39 46
是我的話我也會選擇用右邊去合併，因為左邊子樹鍵值太多，一看就很容易錯
而用右邊合併完結果跟你一樣，至於結果對不對，一樣，你也可以insert 25試試
但是硬要用左邊合併的話，我也不知道怎麼合併了，可以知道的是前一篇用左邊合併的答案是錯的
以上供參考。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.171.126.223
→ st84514:感謝回答,我現在才發現可以插回去驗算這招! 01/28 22:37
推 juan19283746:原PO帥哥 01/28 22:40
推 nypgand1:第一小題還是有兩個答案吧 這篇是拿右子樹的最小值18上去 01/28 23:40
→ nypgand1:上一篇是拿13上去 就可以跟7,8借 01/28 23:41
→ nypgand1: 借來rotation的意思 01/28 23:42
→ wolfswolfs:如果你認為那種情況可以這樣作 你可以insert 15回去試 01/29 00:33
→ wolfswolfs:不是甚麼情況都可以rotation的 01/29 00:35
推 tuner123:原PO帥哥 01/29 00:40
推 tetragramm:請問為什麼insert回去的結果一定會跟原本一樣呢? 01/29 01:14
推 cksh3300110:樓上也很帥 01/29 01:22