完全二叉树的高度为什么是对lgN向下取整

完全二叉树的高度为什么是对lgN向下取整,第1张

完全二叉树的高度为什么是对lgN向下取整

完全二叉树的高度为什么是对lgN向下取整呢?

说明一下这里的高度:只有根节点的树高度是0。


设一棵完全二叉树节点个数为N,高度为h。


所以总节点个数N满足以下不等式

1 + 21 + 22 +……+ 2h-1 < N <= 1 + 21 + 22 +……+ 2h 即 2h - 1 < N <= 2h+1 - 1,所以 2h < N+1 <= 2h+1,两边同取以2为底的对数得 h < log2(N+1) <= h+1。



若 N+1 = 2k ,此时完全二叉树为满二叉树,解上述不等式得 h < k <= h+1,所以 k-1 <= h < k,所以 h = k-1。


而 log2N = log2(2k -1),又因为比 2k -1 小且离其最近的2的幂是 2k-1 ,

所以 log2N> log2(2k-1) = k-1,因此对 log2N 向下取整即为 k-1,即二叉树的高度等于对 log2N 向下取整。



若 N+1 不等于2的幂,设2k-1 < N+1 < 2k,所以 k-1 < log2(N+1) < k,所以 k-2 < h < k,所以 h = k-1。


设此时对应的满二叉树节点数为N0,所以 k-1 = 对log2N0向下取整,

h = k-1 也等于对log2N0向下取整。


因为 N > 2k-1 -1,即 N >= 2k-1,N0 <= 2k -1,所以对log2N0向下取整等于对 log2N 向下取整。


所以二叉树的高度等于对 log2N 向下取整。



证毕。


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/589620.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-12
下一篇 2022-04-12

发表评论

登录后才能评论

评论列表(0条)

保存