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