证明:对于任一包含n个元素的堆中,至多有个高度为h的节点?-笔试面试资料

这是qklbishe.com第19913 篇笔试面试资料
提供答案分析,通过本文《证明:对于任一包含n个元素的堆中,至多有个高度为h的节点?-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
证明:对于任一包含n个元素的堆中,至多有证明:对于任一包含n个元素的堆中,至多有个高度为h的节点?个高度为h的节点?

证明:对于任一包含n个元素的堆中,至多有个高度为h的节点? 神弑
堆这种数据结构的性质使得其必然是完全二叉树,但可不一定是满完全二叉树,为了方便分析,假定它是满完全二叉树(即完美二叉树):
所以这时它也就有完美二叉树的性质:
1、n=n0+n1+n2
2、2n2=n-1
(n2是含有两个孩子的节点数目,n是一棵树所有的节点数目。
想象一下二叉树每个含有两个孩子的节点都会引入两个节点数,每个含有一个孩子的节点都会引入一个节点数,所以有n1+2n2=n-1,n-1是因为根节点只表明了它有两个孩子节点,并没有表明它自己这个节点,因为完美二叉树没有一个孩子的节点,所以n1不存在。故有以上2n2=n-1)
联立两式,得出h=0(由树底~根节点:0~log2n)时的结点数为:
                                                            n0=(n+1)/2^1
h=1时的结点数为:
                                                            n0=(n-(n+1)/2)/2=(n-1)/2^2=(n-1)/4<n/4
h=2时的结点数为:
                                                            n0=(n-(n+1)/2-(n-1)/4)/2=(n-1)/2^3<(n-1)/8<n/8
同理可证:n0<n/2^(h+1),即至多有n/2^(h+1)个高度为h的结点。

今天 10:54:51 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 证明:对于任一包含n个元素的堆中,至多有个高度为h的节点?-笔试面试资料

提供最优质的资源集合

立即查看 了解详情