在一棵高度为2 的 5 阶 B 树中，所含关键字的个数最少_

爱吃青菜皮卷面的byr

n为树根结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。

树叶节点中关键字的个数满足ceil（m/2）~m

两个结点，2+3 = 5

发表于 2017-02-20 00:02:42 回复(1)

ICANTHEARYOU

一个m阶B树是一棵空树，或者是满足以下条件的树:

（1）结点最多有m-1个节点m个分支。

（2）根结点最少有两个分支，非根非叶结点至少有ceil(m/2)个分支。

（3）结点内关键字递增排序。

（4）一个结点有n-1个关键字，则该结点有n个分支，将关键字一一隔开。

（5）结点中任何一个关键字，其左边分支上的结点值都小于这个关键字，右边分支的结点值都大于这个关键字。

（6）叶子结点处于同一层。

编辑于 2019-06-03 22:12:41 回复(0)

川久保玲球

B树的插入操作一定是发生在叶子结点上。5阶B树的结点最多含4个关键字，假设初始B树为空，插入前4个关键字时都在同一个叶节点，此时叶节点即根节点。由题意5阶B树高度为2，则至少含5个关键字。

比如关键字为1，2，3，4，5，高度为2的5阶B树可为：

3

/ \

1,2 4,5

发表于 2020-08-02 14:07:31 回复(0)

裁

问下，书上说B树的阶是指树中孩子结点数的最大值。那么按照5个结点的说法，即第二层分别放两个含有5阶B树最少关键字为2的结点。那么这B树不就成为孩子结点为最大为3的B树了吗？也即是一棵3阶B树了啊？建议画个图看一下。

发表于 2018-12-11 21:11:15 回复(1)

龟龟饲养员

含N个关键字的m阶B-树的最大深度为 h=log[m/2]（（N+1）/2）+1 即[m/2]^（h-1）=（n+1）/2 []代表向上去整代入数据可得 [5/2]=（n+1）/2 解得n=5 详见严书240到241页

发表于 2017-12-04 21:42:32 回复(0)

洛比达

根节点关键字最少 1 个，根节点有两个孩子，每个孩子关键字最少 ceil(5/2) - 1 = 2 个，所以关键字个数最少是 1 + 2 *2 = 5 个。

发表于 2017-09-06 09:37:14 回复(0)

黏黏糖

根节点的分支数为[2,m]，孩子结点的分支数为[m/2,m]

发表于 2017-05-31 09:16:06 回复(0)

microlulu

1.根节点至少有两个孩子节点，那么根节点的关键字至少为1

2.第二层节点（至少2个），每个节点至少有ceil(m/2)=3个孩子节点，那么其关键字至少为2

3.综上：高度为2的5阶B树，关键字个数至少为1+2+2=5

编辑于 2018-09-20 15:38:36 回复(6)

牛客985409号

树非空，根节点至少包含一个关键字，根节点至少两个孩子，孩子节点关键字的个数n满足[ceil(m / 2)-1]<= n <= m-1（m为B树的阶），即n至少为2，两个孩子就是4个关键字，算上根节点共至少5个关键字，不知道对不对？

发表于 2016-11-23 19:37:57 回复(10)

CpInsist

B 树是一种查找树；是一种多路查找树，主要用来进行对磁盘上的文件进行检索的结构；由磁盘的查找特征可知；若果我们所涉及的数据量特别大时，当我们进行数据查询时，我们希望我们能进行的 IO 操作越少越好；换言之就是希望我们的查找树的高度越低越好；而 B 树就是这样一种数据结构。它是一种 m 路的查找树；

B 树只能用于随机查找

在 B 树中：

A: 除了根节点和叶子节点之外，所有的节点最少有 m/2 个孩子节点，最多有 m 孩子个；

B: 根节点至少两颗一个子树

C: 所有的叶节点均在同一层； B 树中的叶节点可以看做时一种外部节点，不包含任何数据；

D ：含有 J 个孩子的非叶孩子节点刚好含有 J-1 个关键码；关键码按照递增的序列排列；

发表于 2016-12-15 10:02:08 回复(5)

AaronSwartz1

上面好多答案都忽略了5阶B树

5阶B树至少有一个节点有5个指针（4个关键字）吧

m阶B树除根结点以外所有非叶子结点关键字最少为（m/2）【向上取整】 - 1

编辑于 2019-04-12 16:25:30 回复(2)

韶关靓仔

根节点 1个关键字，左右孩子分别2个关键字。总5个

发表于 2016-11-24 14:46:56 回复(0)

救赎i_

要一棵m阶B树所含的关键字最少，也就等价于有n个关键字，树的最大高度要最大，求n。所以这种情况下，每个结点的关键字要最小：⌈m/2⌉ - 1，分叉要最小⌈m/2⌉：

这里有两种方法计算：

法一（叶子结点的下限，叶子结点代表失败结点，n个关键字有n+1失败结点，相当于n个关键字将实数域分成了n+1个区间）：

第1层结点数最少为：1

第2层结点数最少为：2 //第一层发出两个分叉

第3层结点数最少为：2⌈m/2⌉ //第二层发出⌈m/2⌉个分叉

第4层结点数最少为：2⌈m/2⌉^2 //第三层发出⌈m/2⌉个分叉

……

第h层结点数最少为：2⌈m/2⌉^(h-2)

第h+1层（失败结点层）结点数最少为：2⌈m/2⌉^(h-1)

所以n + 1 ≥ 2⌈m/2⌉^(h-1)

在这题中m=5，h=2，n + 1 >= 2*3，n >=5，所以关键字最少为5个

法二（关键字的下限）

第1层结点数最少为：1 关键字最少为：1

第2层结点数最少为：2 关键字最少为：2(⌈m/2⌉ - 1) //每个结点关键字为最少：⌈m/2⌉ - 1

第3层结点数最少为：2⌈m/2⌉ 关键字最少为：2⌈m/2⌉(⌈m/2⌉ - 1)

第4层结点数最少为：2⌈m/2⌉^2 关键字最少为：2⌈m/2⌉^2(⌈m/2⌉ - 1)

……

第h层结点数最少为：2⌈m/2⌉^(h-2) 关键字最少为：2⌈m/2⌉^(h-2)(⌈m/2⌉ - 1)

将每层的关键字数目相加1 + 2(⌈m/2⌉ - 1) + 2⌈m/2⌉(⌈m/2⌉ - 1) + 2⌈m/2⌉^2(⌈m/2⌉ - 1) + ... + 2⌈m/2⌉^(h-2)(⌈m/2⌉ - 1) =

1 + 2(⌈m/2⌉ - 1)（1 + ⌈m/2⌉ + ⌈m/2⌉^2 + ... + ⌈m/2⌉^(h-2)）= 1 + 2(⌈m/2⌉^(h-1) - 1) = 2⌈m/2⌉^(h-1) - 1

由此 n >= 2⌈m/2⌉^(h-1) - 1，不难看出这个不等式和方法一得到的是一模一样的。

故我们可以用以上两种方法求解。

这个是有公式的，我只是按照根据那个思路自己推了一遍，看起来有点麻烦，实际推很快的。

发表于 2022-07-20 20:17:02 回复(1)

MnM~

高度为2，阶数为5的B树，则除了根节点以外的结点的子树最少为5/2向上取整为3.

根节点的最少为2棵子树。

关键字=子树数-1.

所以，

高度为1：根节点1个关键字

高度为2: 2个结点，结点的子树取最少为3，所以各有2个关键字。

总共：1+2*2=5

发表于 2022-04-05 15:53:36 回复(0)

__sgf__

根节点关键字最少 1 个，根节点有两个孩子，每个孩子关键字最少 ceil(5/2) - 1 = 2 个，所以关键字个数最少是 1 + 2 *2 = 5 个。

发表于 2022-03-14 02:07:11 回复(0)

Fitz1990

往一个5阶树里边1个1个的放数据，什么时候开始分叉，什么时候不就是最小索引个数吗？

5阶的树，先往根节点上塞1,2,3,4进去，再加一个5，就开始分叉了。所以最小是5啊

发表于 2021-07-09 23:21:09 回复(1)

Starling9

这里的阶数=5是用来确定每个结点关键字个数范围的，不代表存在关键字个数=4的结点！阶数是所有结点孩子个数的最大值，不一定达得到最大值

发表于 2020-10-31 18:19:56 回复(0)

浅悠凉

根节点一个关键字，只有一个孩子，有4个关键字，1+4=5

编辑于 2018-11-28 11:20:59 回复(0)

云云云一飞冲天

笔记如下：

发表于 2022-08-23 13:54:27 回复(0)

努力coding_

有两层，那么必然不是空树。求最小，那根节点算一个关键字。有两个分支。

接下来的计算“除根节点以外的非叶节点至少有ceil(m/2)-1个关键字”，ceil是向上取整，m是B树的阶=5

计算得到每个非叶节点（除了根节点）至少有2个关键字。

所以1+2+2=5，本题选5。

（B树中的叶节点代表查找失败的位置）

补充：B树中除根节点以外的非叶节点中关键字的个数ceil(m/2)-1~m-1

发表于 2024-05-08 10:44:42 回复(0)

在一棵高度为2 的 5 阶 B 树中，所含关键字的个数最少

一个m阶B树是一棵空树，或者是满足以下条件的树:

问题信息

热门推荐

相关试题

在一棵高度为2 的 5 阶 B 树中， 所含关键字的个数最少

一个m阶B树是一棵空树，或者是满足以下条件的树:

问题信息

热门推荐

相关试题

在一棵高度为2 的 5 阶 B 树中，所含关键字的个数最少