作爲n的函數，Btree的最大高度是多少？

Question

我有以下問題：

爲1度的B樹，什麼是最大高度的樹作爲 樹按鍵的數量n的功能？

我認爲，因爲樹的順序是1，這意味着鍵的數量可以在1和2之間。因此，我拿了一棵樹，每個節點只有一個鍵，所以我可以有最大高度。添加我得到的每個級別的節點數

2^0 + 2^1 + 2^2 + ... + 2^h = n，其中n是節點的數量，h是高度樹 並解決它我得到的高度是log（n + 1），但我不確定這是正確的答案。 任何想法？

Answer 1

m階B樹的最壞情況高度爲logm/2n。

參見：http://en.wikipedia.org/wiki/B-tree#Best_case_and_worst_case_heights

Answer 2

身高二叉樹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