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

[easonc (eason)]

※ 引述《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
推 pups003: 可以split吧，2-3 tree是link數為2 or 3
推 pups003:  http://i.imgur.com/iqqHHQJ.jpg
→ easonc: 多謝~你中間split的過程是怎樣呢?
→ easonc: 是把4insert到56的node再split，然後5跑進79的node再split
→ easonc: 一次嗎?
推 pups003: 4,7,9 split,然後4到5,6 發現也要 split
→ pups003: 我是這樣想的喇
→ easonc: 可以一步一步畫圖嗎?3Q~感覺好像會有別的case怪怪的
推 janus7799: 2-3 top down應該不用split路徑上的3-node，因為3-node
→ janus7799: 不保證可以分成三個結點。借用樓上的圖，如果delete 6
→ janus7799: 再insert 4，沿途split所有3-node會造成高度不平衡
→ easonc: 我也是想到這個情況可是不沿途split 3-node該怎麼insert呢
推 dddm49: 不是找到正確位置插入後  再看有無overflow 決定是否split
→ dddm49: 嗎