在有关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)+叶节点数<= 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)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句