如何获取BB[α]树的高度
How to get the height of BB[α] tree
关于 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 是节点总数
但是，我的推导在维基百科上得不到结论，谁能指正我的错误？谢谢
我会这样证明。
child 节点的权重必然大于其 parent 的 alpha 倍。
因此 parent 权重至少是 child 权重的 1/(1-a) （考虑到 alpha 肯定小于 0.5 并且 child 到 [=24 的间隔=] alpha 与 1-alpha 的比率。
因此，如果我们有一些高度 h，则 parent 重量必须至少为 (1/1-a)^h 从最深的 child 到 parent .
所以 w=n >= (1/(1-α))^h
h <= log_{1/(1-α)}(n)（选择不同的方法来表示碱基 :D）
关于 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 是节点总数
但是，我的推导在维基百科上得不到结论，谁能指正我的错误？谢谢
我会这样证明。
child 节点的权重必然大于其 parent 的 alpha 倍。 因此 parent 权重至少是 child 权重的 1/(1-a) （考虑到 alpha 肯定小于 0.5 并且 child 到 [=24 的间隔=] alpha 与 1-alpha 的比率。
因此，如果我们有一些高度 h，则 parent 重量必须至少为 (1/1-a)^h 从最深的 child 到 parent .
所以 w=n >= (1/(1-α))^h
h <= log_{1/(1-α)}(n)（选择不同的方法来表示碱基 :D）