在一个10阶的B-树上，每个树根结点中所含的关键字数目最多允_网易有道笔试题

feitian

树根节点不是[1,M-1]个关键字吗？

发表于 2016-08-31 10:37:54 回复(6)

Yel

题目错了，非根节点才对

发表于 2016-09-04 21:26:05 回复(2)

牛客359211号

http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

发表于 2016-08-31 12:13:16 回复(3)

banbo

最多M-1 最少M/2-1 向上取整

发表于 2016-08-29 16:56:25 回复(8)

勤劳致富君

B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种树。而事实上是， B-tree就是指的B树 。

发表于 2016-09-09 13:05:15 回复(4)

dilemmaxk

关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1 （ceil为取上整）

发表于 2016-09-01 14:32:39 回复(1)

拿不到offer就只是个富二代了

之前看题目理解错了，我还以为是题目错了。很多人跟我一样理解的是根节点的儿子节点个数，其实是关键字个数。请看下面的B树特性第5条：

一颗m阶的B树的特性如下：

1）树中每个节点最多含有m个孩子（m>=2）

2）除根节点和叶子结点外，其他节点最少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；

3）若根节点不是叶子结点，最少有两个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；

4）所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；（读者反馈@冷岳：这里有错，叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。@研究者July：其实，关键是把什么当做叶子结点，因为如红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已）。

5）每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：

a) Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。

b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。

c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

发表于 2017-08-05 14:22:56 回复(0)

牛客3163694号

根结点的儿子数为 [2, M]；

除根结点以外的非叶子结点的儿子数为 [M/2, M]；

每个结点存放至少 M/2-1 （取上整）和至多 M-1 个关键字；（至少 2 个关键字）。

发表于 2017-05-24 15:07:26 回复(0)

九千亿高尔基

最多M-1 最少M/2-1 向上取整

发表于 2018-10-21 21:36:27 回复(0)

逆袭的黑马

不懂这个B树，还没复习到。

发表于 2020-12-26 17:03:52 回复(0)

你永远得不到的祖奶奶

发表于 2020-06-23 20:34:39 回复(0)

Astrallee

应该是非树根最多m-1 最少m/2-1 向上取整不是吗。。数根节点不是至少两个树，一个关键字吗

发表于 2019-12-07 23:07:46 回复(0)

MichaelOven

题***

发表于 2019-01-30 23:28:15 回复(0)

Forrestcloud

B树的定义：

树中每个节点至多有m棵子树；
若根节点不是叶子结点，则至少有两棵子树；
除根节点之外的所有非终端节点至少有m/2（向上取整）棵子树；
所有非终端节点包含如下数据信息：关键字个数n，指向子节点的指针，关键字的值；
所有叶子结点都出现在同一层次上，并且不带信息；

综上，因为是m阶的B树，所以，子节点数最多为m，关键字数目最多则只有m-1，10-1=9；

又因为m阶B 树，至少m/2棵子树，向上取整，也就是最少10/2=5棵子树，那么关键字最少则只有5-1=4个了；

另外，题目的条件也有点问题，应该说明为非根节点！

编辑于 2017-09-11 11:13:16 回复(0)

大胆试吧

根节点[1,M]

非根节点叶子结点最多M-1 最少M/2-1 向上取整

注意关键字与儿子数的区别

发表于 2017-09-02 09:12:19 回复(0)

王智宏基

复习下b树,

[摘自Wikipedia]

For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a₁ and a₂. All values in the leftmost subtree will be less than a₁, all values in the middle subtree will be between a₁ and a₂, and all values in the rightmost subtree will be greater than a₂

发表于 2017-09-01 20:30:18 回复(0)

千寻者

这道题应该考得是非根结点与叶子结点的结点的情况，如果像题干所说的是根结点，那么最少应该可是是1个结点。

发表于 2017-08-08 21:34:08 回复(0)

Toktok

《算法导论》第十八章:

B树T是具有以下性质的有根树(根为T.root)

......

5.每个结点所包含的关键字个数有上界和下界。用一个被称为B树的最小度数的固定整数t>=2来表示这些界:

a.除了根结点以外的每个结点必须至少有t-1个关键字。因此，除了根结点以外的每个内部结点至少有t个孩子，如果树非空，根结点至少有一个关键字

b.每个结点至多可包含2t-1个关键字。因此，一个内部结点至多可有2t个孩子。当一个结点恰好有2t-1个关键字时，称该结点是满的。

我认为应该选B

发表于 2017-07-21 07:01:05 回复(0)

sunlight_run

n阶B-二叉树，每个书根节点最多n-1关键字，最少n/2 - 1个关键字

编辑于 2017-06-26 10:03:09 回复(0)

korky

B-树

是一种多路搜索树（并不是二叉的）：

1. 定义任意非叶子结点最多只有M个儿子；且M>2；

2. 根结点的儿子数为[2, M]；

3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；

4. 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

5. 非叶子结点的关键字个数=指向儿子的指针个数-1；

6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树， P[M] 指向关键字大于 K[M-1] 的子树，其它 P[i] 指向关键字属于 (K[i-1], K[i]) 的子树；

8. 所有叶子结点位于同一层；

编辑于 2017-06-01 10:16:50 回复(0)

在一个10阶的B-树上，每个树根结点中所含的关键字数目最多允

问题信息

热门推荐

相关试题