首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
A 3-order B-tree has 2047 key
[单选题]
A 3-order B-tree has 2047 key words,what is the maximum height of the tree?
11
12
13
14
添加笔记
求解答(0)
邀请回答
收藏(8)
分享
纠错
1个回答
添加回答
0
牛客-007
答案:A
M阶B树只能在叶子结点存储数据,其他结点的孩子个数必须在[ceiling(M/2), M]之间,根节点要么是叶子结点,要么至少有两个孩子。
根据该定义,如果3阶B树有2048个元素,那高度最大时每个结点都取孩子个数下限(2),高度为12(即log(2048)+1)。
然后去掉一个叶子结点,则从叶子向根一路发生结点合并,一个2孩子结点和一个1孩子结点合并成为一个3孩子结点。
根节点的两个孩子也发生了结点合并,变成了一个结点,根不再满足B树的要求,被删除,其唯一的孩子成为了新的根。 于是,树的高度变为了11。
发表于 2015-01-27 15:04:55
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
微软
树
上传者:
sometimes
难度:
1条回答
8收藏
8353浏览
热门推荐
相关试题
编写实现链表排序的一种算法。说明为...
微软
链表
排序
评论
(2)
体育课测验(二)
广度优先搜索(BFS)
拓扑排序
dfs
评论
(2)
防火墙是怎么实现的?
计算机网络基础
评论
(1)
PMOS和NMOS的区别
元器件
评论
(1)
“乔布斯不做调查,张小龙不看数据。...
用户研究
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题