关于 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上得不到结论，谁能指正我的错误？谢谢
最佳答案
我会这样证明。
子节点的权重必然大于其父节点的 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)
关于algorithm - 如何获取BB[α]树的高度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33466785/