推 janus7799: 做的時候是9往上拉，左子8右子10，不過這個說法也小有 02/14 23:02
→ janus7799: 瑕疵 02/14 23:02
※ 編輯: easonc (118.166.104.200), 02/15/2016 09:20:42
→ easonc: 謝謝~ 02/15 09:38
有個小問題想請教各位
2-3 tree 的 top-down insertion 要怎麼做呢?
我在做台大電機丙資結的第10題看到的
我知道做top down 的insertion是由root開始往下走，
遇到full的node就split，然後繼續往下走，重複這個過程。
當order是偶數(node滿的時候會有奇數把key，如:2-3-4tree)，
split可以把正中間的key往上放，
比中間的key大的key分在右邊的node，
比較小的key分在左邊的node;
可是當order是奇數(node滿的時候有偶數把key)，就不能這樣做了
以這一題來說，他要我們用top down的方式依序insert{10,9,8,7,...}
等key到一個2-3 tree。
首先，依序insert 10,9，tree變成:1個node，稱這個node為N，
N裡面有9和10。
接著insert 8，發現N已經full了，所以應該split N，
這時候N應該怎麼split呢?覺得卡卡的，想問問大家，謝謝各位~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.104.200
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455460266.A.1AE.html