PTT職涯區 / Examination (國家考試)

[課業] 資料結構-B tree問題

看板Examination (國家考試)作者 (mingrong)時間13年前 (2013/03/21 17:14), 編輯推噓6(6推 0噓 4→)
留言10則, 3人參與, 最新討論串1/1
下面有兩個疑問: 問題一 : 在最壞的形況下，一個高度為2，但儲存空間之使用率為100%的 B tree會比一個等高度的B+ tree多存一倍的紀錄(records) 答案:不正確,處存資料數量大致相同 為什麼儲存資料會大致相同阿??B+ tree不是只有樹葉才會存資料嗎? 問題二: 假設B tree 的階級(order)為m,則每個內部節點至少有┌m/2┐個子節點 答案:false 這題為什麼是false?? 麻煩知道的大大說明一下，感謝><... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 124.199.76.249
推
03/21 17:22, , 1F
問題二應該是答案錯了
03/21 17:22, 1F
推
03/21 17:44, , 2F
問題2: root 除外 但是 root 需要至少有2個children
03/21 17:44, 2F
推
03/21 18:53, , 3F
嗯 忘記root這東西了XD
03/21 18:53, 3F
第2題懂了~那第1題知道為什麼嗎? ※ 編輯: mingrong2 來自: 114.34.31.118 (03/21 23:14)
推
03/21 23:29, , 4F
高度為2...
03/21 23:29, 4F
推
03/22 00:00, , 5F
我覺得這題是給定一個空間S B tree和B+ tree都用滿
03/22 00:00, 5F
→
03/22 00:01, , 6F
這個空間S的情況下 去比較兩者所存的key 和 records
03/22 00:01, 6F
推
03/22 00:03, , 7F
假設B tree每層的key有n個 records為n-1個
03/22 00:03, 7F
→
03/22 00:05, , 8F
B+ tree的第一層key值為m 第2層records亦為m
03/22 00:05, 8F
→
03/22 00:06, , 9F
因為只有兩層 對B tree而言每一層的key:records~=1:1
03/22 00:06, 9F
→
03/22 00:07, , 10F
B+ tree亦是1:1
03/22 00:07, 10F
還是聽不太懂><.... ※ 編輯: mingrong2 來自: 124.199.76.249 (03/22 16:52)
‣ 更多 mingrong2 的文章
文章代碼(AID): #1HIizezQ (Examination)
Examination 近期熱門文章
更多 近期熱門文章 >>
PTT職涯區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 mingrong2 的文章
文章代碼(AID): #1HIizezQ (Examination)