algorithm - 作为 n 的函数，Btree 的最大高度是多少？

Question

我有以下问题:

For a B-tree of degree 1, what is the maximum height for a the tree as a function of the number of keys n in the tree?

而且我认为因为树的阶数是 1，这意味着键的数量可以在 1 到 2 之间。因此我选择了一棵每个节点只有 1 个键的树，这样我就可以拥有最大的高度。添加我得到的每个级别的节点数

2^0+2^1+2^2+...+2^h= n，其中n是节点数，h是树的高度并解决它我得到高度 h 是 log(n+1) 但我不确定这是正确的答案。有什么想法吗？

Answer 1

二叉树的高度h=log(n+1)-1

这是推导

这里我假设根的高度为零

所以

n=2^0+2^1+2^2........2^h

应用几何级数公式并得到

h=log(n+1)-1.

这里的对数基数是 2。所以当每个级别只有一个节点时。我们可以得到 log(2)base 2, n 次 SO 最大高度变为

h=n-1