如何获得BB [α]树的高度

大卫

在有关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] 删除。

编辑于
0

我来说两句

0条评论
登录后参与评论

相关文章

来自分类Dev

如何获得BB [α]树的高度

来自分类Dev

如何计算树的高度

来自分类Dev

如何获得带有spacy的依赖树的高度?

来自分类Dev

如何运行BST树功能的高度

来自分类Dev

如何递归地找到特里树的高度

来自分类Dev

如何在C中找到特里树的高度

来自分类Dev

如何数学推导此递归树的叶的高度和数量

来自分类Dev

getHeight如何递归确定二叉树的高度?

来自分类Dev

如何找到二叉搜索树的最大高度?

来自分类Dev

如何在C中找到三叉树的高度

来自分类Dev

如何在树中找到右侧孩子的高度减去左侧孩子的高度

来自分类Dev

如何获得topLayoutGuide的高度?

来自分类Dev

合并排序lg(n)+1中递归树的高度如何

来自分类Dev

如何证明二叉搜索树的平均高度为O(logn)?

来自分类Dev

合并排序lg(n)+1中递归树的高度如何

来自分类Dev

如何在将视图添加到视图树之前计算 UIViewController 高度?

来自分类Dev

如何使用elixir递归实现二叉搜索树的高度?

来自分类Dev

如何获得Bootstrap Popover高度?

来自分类Dev

如何获得div的外部高度?

来自分类Dev

我如何获得UILabel的高度?

来自分类Dev

如何获得 DirectWrite 布局的高度?

来自分类Dev

玫瑰树Haskell的高度

来自分类Dev

高度平衡的树-改进

来自分类Dev

计算树的高度-Java

来自分类Dev

选择树的根,使树的高度最小

来自分类Dev

如何在不使用递归和级别顺序遍历的情况下找到二叉树的高度?

来自分类Dev

如何获得TFS项目树的平面视图?

来自分类Dev

如何获得声纳树参数的值

来自分类Dev

堆树高度vs BST高度