[理工] [DS] 104台大電機丙 top down insertion
有個小問題想請教各位
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
推
02/14 23:02, , 1F
02/14 23:02, 1F
→
02/14 23:02, , 2F
02/14 23:02, 2F
※ 編輯: easonc (118.166.104.200), 02/15/2016 09:20:42
→
02/15 09:38, , 3F
02/15 09:38, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：