[理工] 105 中央 資演 B tree問題

看板Grad-ProbAsk作者 (睡覺宰予)時間6年前 (2020/01/05 11:20), 6年前編輯推噓4(4推 0噓 7→)
留言11則, 3人參與, 6年前最新討論串1/1
這年的中央題目提到5,4,3,2,1放入一個空的B tree裡面(degree 3) 版上查到的答案是 [2,4] / | \ [1] [3] [5] 不過我去網路上看，看到的都是一個節點最多放兩倍degree-1的key 照這樣算起來光是root就可以把所有東西裝滿了啊？(變成[1,2,3,4,5]) 不知道各位朋友能否賜教，提醒我到底哪邊出問題了，如果直接告訴我步驟更感謝。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.74.226.57 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578194431.A.6A2.html
推
01/05 11:28, 6年前 , 1F
degree 3不是代表一個節點可以伸出去3個線ㄇ
01/05 11:28, 1F
→
01/05 11:28, 6年前 , 2F
也就是key最多2個 不太可能塞到5個吧
01/05 11:28, 2F
推
01/05 11:40, 6年前 , 3F
應該是你的定義看錯吧！ 不如把網址放上來給大家看看
01/05 11:40, 3F
https://i.imgur.com/l4cJX8Q.png
先上一張圖片，網址等等(好像有點長我看看是否縮一下) 剛剛才發現人家是minimum degree不是單純degree，是差在這邊嗎 (更)一開始是看這個(我餵狗第一條)： https://bit.ly/2ZPtkOa 後來是看這個： https://bit.ly/39DqkJi ※ 編輯: GlassesKJ (42.74.226.57 臺灣), 01/05/2020 12:45:23
推
01/05 14:47, 6年前 , 4F
你的第一張圖講的是minimum degree=3，不是max=3
01/05 14:47, 4F
推
01/05 14:51, 6年前 , 5F
題目的degree=3是指max degree=3
01/05 14:51, 5F
→
01/05 14:53, 6年前 , 6F
用你查到的算法是2t-1=3,t=2 至少要1個data
01/05 14:53, 6F
→
01/05 14:58, 6年前 , 7F
原來是這樣，所以結果才會變成一般2,3樹那樣啊
01/05 14:58, 7F
→
01/05 14:59, 6年前 , 8F
好吧我沒搞懂這個degree怎麼分的，中央105也沒有特別明
01/05 14:59, 8F
→
01/05 14:59, 6年前 , 9F
講:3
01/05 14:59, 9F
→
01/05 15:25, 6年前 , 10F
算是習慣用法,Btree of degree k代表最多k個子樹
01/05 15:25, 10F
→
01/05 16:35, 6年前 , 11F
瞭解，感謝指導
01/05 16:35, 11F
‣ 更多 GlassesKJ 的文章
文章代碼(AID): #1U4LN_QY (Grad-ProbAsk)