首页 > 试题广场 >

在一棵5阶B_树中，高度是5（叶子层不算），则这棵B树至少有

[填空题]
在一棵5阶B_树中，高度是5（叶子层不算），则这棵B树至少有    1　  个结点
添加回答
菲尼-艾德头像 菲尼-艾德
根节点最少一个关键字，最少2个子节点， 其他节点，最少m/2(向上取整)-1个关键字，这里m=5，所以是最少3-1=2个关键字，最少m/2（向上取整）个子节点，也就是3个子节点。
第一层： 1
第二层：  2*2=4
第三层:      （2*3）*2=12
第四层：    （6*3）*2=36
所以最少 36+12+4+1=53；
答案53

编辑于 2017-10-26 23:28:20 回复(0)
更多回答
L-where🍉头像 L-where🍉
一楼有2个赞我是没想到的。
不如画个表啊：
                      个数      孩子
 第一层。         1.          2
 第二层：         2.         2*3
 第三层：        2*3    （2*3）*3
 第四层：        2*3*3   （2*3*3）*3
 第五层：      2*3*3*3.   （2*3*3*3)*3 


可以看到：第一层比较特殊，无论几阶，孩子最少都是2，关键字最少都是1.
而下面的层数就变得有规律起来了：
求最小个数，就是首项为2，公比为3的等比数列。
如果再考虑最少关键字个数，因为每个结点的最少关键字是2，也就是每一层的个数乘2，其实公比还是3，只不过首项变为2*2=4了

故对于高度为5的5阶B树，就是一个1+ 首项为2，公比为3，个数为（5-1）=4的等比数列求和
对于本题，就是1+2*（1-3^4)/(1-3)=1+3^4-1=3^4=81

比较难的是求关键字，第h层的关键字个数，如果用数列ah来表示的话，就是一个：
1⃣️ 首项为1（根结点只有1个关键字，其余均至少满足[m/2]-1个关键字）
2⃣️ 其余项是等比数列的形式，令k=[m/2],其数值为ah=2*K^(H-2) *(K-1)
编辑于 2020-11-20 23:54:06 回复(0)
提交观点

问题信息

树
上传者：星辰大海的碎片
难度：
2条回答 5617浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号