[理工]資結 2-3 tree

[maque (Que)]

題目如下
http://ppt.cc/heMZ
http://ppt.cc/ygwP
有問題在於第二小題，刪除部分
第一次刪除30在root部分應該可以選擇35作為root吧?
第二次刪除7照原解沒有疑問，
第三次刪除18，自己是這樣想的，
因無法做旋轉只能合併，父節點16拉下來作合併，
父節點overflow，則拉祖父節點19下來，變成root為overflow，
等同刪除root，從右子樹找最小值22拉上來。

麻煩解答了!感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.68.195.162
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1416316291.A.CB8.html
推 kather: 第三次刪除18 父節點拉下來後underflow=>可以rotation
推 kather: 可以rotation就rotation 0.0 不能才嘗試combination
推 kather: 而第一題中 Horowitz書內的deletion是
→ kather: 先看有沒有右邊sibling 有的話看他能不能rotation
→ kather:   能則rotation 不能則把該node 右邊sibling combine
→ kather: 也就是說是先考慮與右邊合併
→ kather: 只不過你要寫成先考慮跟左邊合併也是可以啦....
→ kather: 他那個答案跟右邊的合併應該是根據這個來的
→ maque: 明白了!謝謝!