心理

当前位置 /首页/完美生活/心理/列表

b树一定要有一个结点的关键字

b树一定要有一个结点的关键字

按照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

TAG标签:关键字 结点 #