博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
证明:n个结点的堆中结点i的子树大小至多为2n/3
阅读量:5078 次
发布时间:2019-06-12

本文共 435 字,大约阅读时间需要 1 分钟。

证明:n个结点的堆中结点i的子树大小至多为2n/3

堆中结点数目为n,因为做子树数目肯定大于等于右子树数目,所以底层半满时左子树最大(含结点数目最多)

假设高度为h的堆底层正好半满,此时左子树高度为0的结点数目为k个,则右子树中与左子树在同一层的结点数目也为k个(此时为空)

当对是满二叉树时,结点数目为n+k个,高度1-h之间有2^(h)-1个结点,高度0有2^(h) == 2k个结点,因此结点总数为2^h - 1 + 2^(h) = 4*k-1个结点(2*k = 2^(h))

可得:n+k = 4*k -1

            n = 3*k - 1

左子树结点数目为:(n+k-1)/2 = (4*k-2)/2 = 2*k - 1 = 2*(n+1)/3 - 1 = (2*n-1)/3 < 2*n/3

因此结点i的子树大小至多为2*n/3

转载于:https://www.cnblogs.com/taotao315/archive/2013/03/11/2953783.html

你可能感兴趣的文章
32位与64位 兼容编程
查看>>
iframe父子页面通信
查看>>
ambari 大数据安装利器
查看>>
java 上传图片压缩图片
查看>>
magento 自定义订单前缀或订单起始编号
查看>>
ACM_拼接数字
查看>>
计算机基础作业1
查看>>
Ubuntu 深度炼丹环境配置
查看>>
C#中集合ArrayList与Hashtable的使用
查看>>
从一个标准 url 里取出文件的扩展名
查看>>
map基本用法
查看>>
poj-1163 动态规划
查看>>
Golang之interface(多态,类型断言)
查看>>
Redis快速入门
查看>>
BootStrap---2.表格和按钮
查看>>
Linear Algebra lecture 2 note
查看>>
CRC计算模型
查看>>
Ajax之404,200等查询
查看>>
Aizu - 1378 Secret of Chocolate Poles (DP)
查看>>
csv HTTP简单表服务器
查看>>