Re: [理工] [DS] 104台大電機丙 top down insertion

看板Grad-ProbAsk作者 (eason)時間8年前 (2016/02/15 10:11), 編輯推噓5(5推 0噓 9→)
留言14則, 4人參與, 最新討論串2/2 (看更多)
※ 引述《easonc (eason)》之銘言： : 我知道做top down 的insertion是由root開始往下走， : 遇到full的node就split，然後繼續往下走，重複這個過程。 : 當order是偶數(node滿的時候會有奇數把key，如:2-3-4tree)， : split可以把正中間的key往上放， : 比中間的key大的key分在右邊的node， : 比較小的key分在左邊的node; : 可是當order是奇數(node滿的時候有偶數把key)，就不能這樣做了 : 如果有一棵2-3 tree: 7,9 / | \ 5,6 8 10 需要insert 4 如果做的是bottom up的insertion， 應該是把 4 insert到5,6的那個node，再split，再往上檢查看有沒有人需要再split; 但是， 如果是top-down 的 insertion， 應該是 從根開始往下看，發現7,9的node已經滿了，就split 7,9的node 可是只有2個key的node怎麼split，好像都很奇怪 我是不是誤會了甚麼qq -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.104.200 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455502292.A.37E.html
推
02/15 10:27, , 1F
可以split吧，2-3 tree是link數為2 or 3
02/15 10:27, 1F
推
02/15 10:34, , 2F
02/15 10:34, 2F
→
02/15 10:53, , 3F
多謝~你中間split的過程是怎樣呢?
02/15 10:53, 3F
→
02/15 10:54, , 4F
是把4insert到56的node再split，然後5跑進79的node再split
02/15 10:54, 4F
→
02/15 10:55, , 5F
一次嗎?
02/15 10:55, 5F
推
02/15 11:33, , 6F
4,7,9 split,然後4到5,6 發現也要 split
02/15 11:33, 6F
→
02/15 11:34, , 7F
我是這樣想的喇
02/15 11:34, 7F
→
02/15 11:55, , 8F
可以一步一步畫圖嗎?3Q~感覺好像會有別的case怪怪的
02/15 11:55, 8F
推
02/15 11:56, , 9F
2-3 top down應該不用split路徑上的3-node，因為3-node
02/15 11:56, 9F
→
02/15 11:56, , 10F
不保證可以分成三個結點。借用樓上的圖，如果delete 6
02/15 11:56, 10F
→
02/15 11:56, , 11F
再insert 4，沿途split所有3-node會造成高度不平衡
02/15 11:56, 11F
→
02/15 12:33, , 12F
我也是想到這個情況可是不沿途split 3-node該怎麼insert呢
02/15 12:33, 12F
推
02/15 16:28, , 13F
不是找到正確位置插入後 再看有無overflow 決定是否split
02/15 16:28, 13F
→
02/15 16:28, , 14F
嗎
02/15 16:28, 14F
‣ 更多 easonc 的文章
文章代碼(AID): #1MmJFKD- (Grad-ProbAsk)
‣ 更多 easonc 的文章
文章代碼(AID): #1MmJFKD- (Grad-ProbAsk)