Question

数据结构B树问题

B树的根节点是不是可以只有1个关键字 两个分支 ？那第二层每个分支至少有多少个关键字呀 比如是6阶的是不是第二层至少是4个关键字 就是每个分支至少2个关键字
像这题就有点不会：高度为5且符合6阶B_树约束条件的树，至少包含 ________________个结点。 答案是30 怎么算的 。。。别告诉我5*6就可以 我要详细点
答案也不一定对。。。。我也不知道真正答案 我感觉答案不是30

Answer 1

按照B-树的定义，m阶B- 树中结点的关键字个数为上取整（m / 2）- 1 ~ m - 1，根结点除外，最少可以只有一个关键字
因为B树中关键字代表查找成功，子树个数代表查找失败，因此相应地，每个结点的子树个数为上取整（m / 2） ~ m，根最少2个子树
因此，6阶B- 树正常每个结点关键字个数为2 ~ 5 之间，根结点最少只有1个关键字
高度为5的6阶B-树最少结点个数：
根只有1个结点
第 2 层最少只有2 个结点
第 3 层最少2 * 3 = 6 个结点
第 4 层最少6 * 3 = 18 个结点
如果严格按照B- 树的定义，第 5 层为最下层，是叶子结点（外结点），代表查找失败，没有关键字
如果不是这样严格定义，第5层则应该还有3 * 18 = 54 个结点
答案是1 + 2 + 6 + 18 = 27