algorithm - 如何获取BB[α]树的高度

Question

关于 BB[α] 树的维基百科:https://en.wikipedia.org/wiki/Weight-balanced_tree高度 h <= log(1/(1-α))N(底数为 1/(1-α))。

我不明白他们是如何得出这个结论的。

由性质可知，对于任意节点，父节点v的权值至少比v的权值大1/(1-α)倍，如果树高为h，则我们可以知道根的权值是(1/(1-α))^h，也就是叶节点的个数

考虑到内部节点，它是 2^0 + 2^1 + ... + 2^(h-2) + # of leaf nodes <= N, N 是节点总数

但是，我的推导在wikipedia上得不到结论，谁能指正我的错误？谢谢

Answer 1

我会这样证明。

子节点的权重必然大于其父节点的 alpha 倍。因此，父项权重至少是子项权重的 1/(1-a)(考虑到 alpha 肯定小于 0.5，并且子项与父项比率的区间以 alpha 比 1-alpha 给出。

因此，如果我们有一些高度 h，那么从最深的子节点到父节点，父节点权重必须至少为 (1/1-a)^h。

所以 w=n >= (1/(1-α))^h

h <= log_{1/(1-α)}(n)(选择不同的方法来表示碱基 :D)