首页 > 试题广场 >

在一个空的5阶B-树中依次插入关键字序列{6,8,15,16

[单选题]
在一个空的5阶B-树中依次插入关键字序列{6,8,15,16,22,10,18,32,20}，插入完成后，关键字6所在结点包含的关键字个数为（      ） 
  • 2
  • 3
  • 4
  • 5
查看答案及解析
添加回答
newcomer头像 newcomer
一颗m阶B树，非叶节点至多可以有m-1个关键字，至少可以有ceil(n/2)-1个，根节点可以至少有一个关键字。根据这个原则，可以画出5阶B树的构建过程，如下图所示：

编辑于 2019-07-03 10:22:34 回复(6)
漫步云端.头像 漫步云端.
这篇博客写的挺好
发表于 2019-08-28 21:36:48 回复(1)
默默学习的啦啦啦头像 默默学习的啦啦啦
n阶B-树，每个结点中关键字个数范围为ceil(n/2) - 1 ~ n-1个，因此为2-4个，插入时首先插入6,8,15,16；
再插入22时结点个数大于4，因此取15为中间结点拆分，变成15 - (6,8),(16,22)，继续插入10,18,32变成15 - (6,8,10),(16,18,22,32)，再插入20时结点个数大于4，取20为中间结点拆分，合并到根节点上变为(15,20) - (6,8,10),(16,18),(22,32)
编辑于 2019-05-31 09:42:32 回复(1)
云云云一飞冲天头像 云云云一飞冲天
忘记是从哪里看到的了，大致内容如下：
编辑于 2022-08-22 15:31:27 回复(0)
牛客425244096号头像 牛客425244096号
发表于 2021-07-31 19:32:05 回复(0)
忽然间要很好头像 忽然间要很好
参考理解： 
n阶B-树，除根节点/叶子节点外的节点，最多有n个子树，最少ceil（n/2）（n/2的上界）个子树。
所以，最少3个关键字，根节点至少两个子树，还剩下5个
发表于 2019-05-30 14:56:39 回复(1)
生命不息奋斗不止oooo头像 生命不息奋斗不止oooo
B树老师没教，考研的时候再学
发表于 2021-01-01 20:17:45 回复(0)
🐤201904121546909头像 🐤201904121546909
根据B树的特性：

1) 根节点至少有两个子女；

2) 每个中间节点都包含k个孩子，其中m/2<=k<=m；

3) 每一个中间结点和叶子节点都包含k-1个元素，其中m/2<=k<=m;

4) 所有的叶子节点都位于同一层；

5) 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分。


发表于 2019-11-16 16:01:21 回复(0)
offer快到碗里来啊！头像 offer快到碗里来啊！
https://www.cs.usfca.edu/~galles/visualization/BTree.html
发表于 2019-09-08 10:45:38 回复(1)
提交观点

问题信息

爱奇艺 树 2019
上传者：小小
难度：
9条回答 7846浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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