已知一棵5阶b树共有53个关键字,则树的最大高度为()，最小高度为()。 数据结构题，求详解过

Question

，谢谢。

Answer 1

按照定义，B-树的根结点最少可以只有一个关键字，普通结点最少2个关键字
所有结点最多有4个关键字
因此，最少时有最大高度，下面是关键字数：
第1层：1个
第2层：（1+1）*2=4
第3层：2 *（2+1）*2=12
第4层：2*（2+1）*（2+1)*2= 36
1+ 4+12+36= 53，因此最大高度为4
最多时的关键字数：
第1层：4个
第2层：(4+1) * 4 = 20个
第3层：(4+1) *(4 + 1) *4 = 100
20 + 4 = 24 < 53, 24 + 100 = 124 > 53 ，因此最小高度为3

Answer 2

补充一下，B树的叶子结点不能存储关键字，所以层数需要多加一层，但是高度的定义是层数减一，所以答案没有问题。另外，深度与层数是一样的因为一般算根结点的深度是1，不过有时候是0，这样的话就与高度一样。