[理工]資結 2-3 tree
作者: maque (Roadside) 2014-11-18 21:11:29
題目如下
![]()
![]()
有問題在於第二小題，刪除部分
第一次刪除30在root部分應該可以選擇35作為root吧?
第二次刪除7照原解沒有疑問，
第三次刪除18，自己是這樣想的，
因無法做旋轉只能合併，父節點16拉下來作合併，
父節點overflow，則拉祖父節點19下來，變成root為overflow，
等同刪除root，從右子樹找最小值22拉上來。
麻煩解答了!感謝
有問題在於第二小題，刪除部分
第一次刪除30在root部分應該可以選擇35作為root吧?
第二次刪除7照原解沒有疑問，
第三次刪除18，自己是這樣想的，
因無法做旋轉只能合併，父節點16拉下來作合併，
父節點overflow，則拉祖父節點19下來，變成root為overflow，
等同刪除root，從右子樹找最小值22拉上來。
麻煩解答了!感謝
作者: kather (Kather) 2014-11-18 22:01:00
第三次刪除18 父節點拉下來後underflow=>可以rotation可以rotation就rotation 0.0 不能才嘗試combination而第一題中 Horowitz書內的deletion是先看有沒有右邊sibling 有的話看他能不能rotation能則rotation 不能則把該node 右邊sibling combine也就是說是先考慮與右邊合併只不過你要寫成先考慮跟左邊合併也是可以啦....他那個答案跟右邊的合併應該是根據這個來的
作者: maque (Roadside) 2014-11-19 19:19:00
明白了!謝謝!