作者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)