首页
题库
面试
求职
学习
竞赛
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收藏
8509浏览
热门推荐
相关试题
编写实现链表排序的一种算法。说明为...
微软
链表
排序
评论
(2)
当信号频率等于放大电路的fL或fH...
模拟电路
评论
(1)
假设当前Java程序中 int =...
Java
评论
(1)
假设一存储设备中磁头当前位于磁道的...
操作系统
评论
(1)
分析以下 asyncio 代码片段...
Python
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题