[理工] [資結] B tree of order 3之刪除

看板Grad-ProbAsk作者 (56最帥)時間14年前 (2012/02/09 19:39), 編輯推噓3(3推 0噓 13→)
留言16則, 4人參與, 最新討論串1/1
有點不好畫=.= 想問一下我刪除的步驟哪裡錯了 題目樹如下: 刪除1,2,3 [5 9] / | \ 2 7 12 / \ / \ / \ 1 3,4 6 8 10 15 我的作法 step1: [5 9] / | \ 3 7 12 / \ / \ / \ 2 4 6 8 10 15 step2: [6 9] / | \ 5 7,8 12 / / \ 3,4 10 15 step3: [6 9] / | \ 5 7,8 12 / / \ 4 10 15 但是答案是: 9 / \ 5,7 12 / | \ / \ 4 6 8 10 15 我的感覺是不是我step1->2的rotation和合併錯了??? 有請強者解說一下謝謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 120.126.194.190
推
02/09 19:45, , 1F
step2 5並到7
02/09 19:45, 1F
→
02/09 19:46, , 2F
題外 不會有只有一個child的情形
02/09 19:46, 2F
推
02/09 20:28, , 3F
B tree 的所有leaf會在相同高度喔
02/09 20:28, 3F
推
02/10 01:16, , 4F
要delete 2的時候，應該先考慮到能不能rotation
02/10 01:16, 4F
→
02/10 01:17, , 5F
但是由於3轉下來、4轉上來之後會發生key<1
02/10 01:17, 5F
→
02/10 01:18, , 6F
所以此處不能做rotation，而是要做合併 於是3,4就合在
02/10 01:18, 6F
→
02/10 01:19, , 7F
同一個node 合併後發現原本3的位置也出現鍵植數<1
02/10 01:19, 7F
→
02/10 01:19, , 8F
於是再看看能不能做rotation，跟上面一樣的情況
02/10 01:19, 8F
→
02/10 01:20, , 9F
所以也只能把5拉下來跟以7為root的子樹做合併
02/10 01:20, 9F
→
02/10 01:20, , 10F
所以我覺得比較正確的step 2的結果應該會是
02/10 01:20, 10F
→
02/10 01:22, , 11F
9
02/10 01:22, 11F
→
02/10 01:22, , 12F
/ \
02/10 01:22, 12F
→
02/10 01:22, , 13F
5,7 12
02/10 01:22, 13F
→
02/10 01:23, , 14F
/ | \ / \
02/10 01:23, 14F
→
02/10 01:24, , 15F
3,4 6 8 10 15
02/10 01:24, 15F
→
09/11 14:54, , 16F
所以此處不能做rota https://daxiv.com
09/11 14:54, 16F
‣ 更多 ma19and5566 的文章
文章代碼(AID): #1FCx1kze (Grad-ProbAsk)