Re: [理工] [資結]2-3 Tree的 delete

看板Grad-ProbAsk作者ybite (小犬)時間13年前 (2011/01/20 00:10)推噓4(4推 0噓 4→)

留言8則, 2人參與討論串4/4 (看更多)

花了一整個早上去想，順便一口氣搞懂2-3 Tree、2-3-4 Tree和B-Tree Orz 我自己的想法跟我修的演算法是一致的，這三種都有類似的作法： Insert：加在葉子上，葉子滿了，把中間提上去，節點一分為二 Remove：不在葉子(Non-leaf)下，就拿左子樹最大和右子樹最小去補在葉子下就直接對葉子做處理當要刪除的節點「裡頭元素不夠了」會形成空洞 ex: 從2-3 Tree or 2-3-4 Tree中2-node 或只剩k-1個keys的B-Tree節點中移除一值這時我們需要透過以下的方式，從下而上把洞給補起來： * 如果左鄰右舍還有剩（借了不會多新洞），就「向左鄰右舍」借這就是Rotation * 如果左鄰右舍沒得借了，那就把鄰居「併」起來，聯合起來「向樓上」借這就是Combination 如果樓上借完之後不夠了，會形成一個洞，再重複這個流程，一路補起來所以回到原題目，我的想法會比較接近 boy5548 重新回顧，要在以下2-3 Tree刪掉14： 14 / \ 12 16,18 /\ / | \ 11 13 15 17 19 Non-leaf，所以拿左邊最大的13補，把原來13所在的位置刪掉，留下空洞： 13 / \ 12 16,18 /\ / | \ 11 空 15 17 19 這時開始補洞。左邊鄰居也是一個2-node，因此沒有辦法進行Rotation 所以只能作Combination，把空跟它的左邊(11)併，向上面借走12： 13 / \ 空 16,18 / / | \ 11,12 15 17 19 借走12之後換上面一層變空，這時因為他的右邊鄰居(16,18)有辦法借一個所以就進行Rotation： 16 / \ 13 18 / \ / \ 11,12 15 17 19 得到答案。 --- tomcallme所謂的「Combination時斷鍵再接回去」這種講法我覺得是有問題的某些情況下會有正確的解答，某些狀況下不會有正確的結果... Orz 但也有可能只是同一種想法的兩種講法。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 122.127.177.42 ※ 編輯: ybite 來自: 122.127.177.42 (01/20 00:19)

推

tomcallme

01/20 14:52, , 1^F

01/20 14:52, 1^F

推

tomcallme

01/20 15:01, , 2^F

01/20 15:01, 2^F

→

tomcallme

01/20 15:02, , 3^F

01/20 15:02, 3^F