证明：对于任一包含n个元素的堆中，至多有个高度为h的节点？

[问答题]

证明：对于任一包含n个元素的堆中，至多有

个高度为h的节点？

查看答案及解析

神弑

堆这种数据结构的性质使得其必然是完全二叉树，但可不一定是满完全二叉树，为了方便分析，假定它是满完全二叉树（即完美二叉树）：

所以这时它也就有完美二叉树的性质：

1、n=n₀+n₁+n₂

2、2n₂=n-1

(n₂是含有两个孩子的节点数目，n是一棵树所有的节点数目。

想象一下二叉树每个含有两个孩子的节点都会引入两个节点数，每个含有一个孩子的节点都会引入一个节点数，所以有n₁+2n₂=n-1,n-1是因为根节点只表明了它有两个孩子节点，并没有表明它自己这个节点，因为完美二叉树没有一个孩子的节点，所以n₁不存在。故有以上2n₂=n-1)

联立两式，得出h=0（由树底~根节点：0~log₂n）时的结点数为：

n₀=(n+1)/2^1

h=1时的结点数为：

n₀=(n-(n+1)/2)/2=(n-1)/2^2=(n-1)/4<n/4

h=2时的结点数为：

n₀=(n-(n+1)/2-(n-1)/4)/2=(n-1)/2^3<(n-1)/8<n/8

同理可证：n₀<n/2^(h+1)，即至多有n/2^(h+1)个高度为h的结点。

发表于 2022-01-08 10:54:51 回复(0)

提交观点

问题信息

上传者：小小

难度：

1条回答 0收藏 1614浏览

扫一扫，把题目装进口袋