Max-Heapify中的最坏情况 - 你如何得到2n/3？

Question

在CLRS,第三版,第155页,给出了在MAX-HEAPIFY中,

孩子们的子树每个都有2n/3的大小- 最坏的情况发生在树的底层正好是半满的时候.

我理解为什么当树的底层正好是半满时它是最糟糕的.并且在这个问题中也回答了MAX-HEAPIFY中的最坏情况:"最坏的情况发生在树的底层恰好是半满的时候"

我的问题是如何获得2n/3？

为什么如果底层是半满的,那么子树的大小是2n/3？

怎么计算？

谢谢

Answer 1

在每个节点具有0或2个子节点的树中,具有0个子节点的节点数比具有2个子节点的节点数多1个.{解释:高度h处的节点数是2 ^ h,由几何级数的求和公式等于(从高度0到h-1的节点之和)+ 1; 从高度0到h-1的所有节点都是正好有2个孩子的节点

    ROOT
  L      R
 / \    / \
/   \  /   \
-----  -----
*****

令k为R中的节点数.L中的节点数为k +(k + 1)= 2k + 1.节点总数为n = 1 +(2k + 1)+ k = 3k + 2 (root加L加R).比率为(2k + 1)/(3k + 2),高于2/3.没有小于2/3的常数可以工作,因为k到无穷大的极限是2/3.

Answer 2

Understand the maximum number of elements in a subtree happens for the left subtree of a tree that has the last level half full.Draw this on a piece of paper to realize this.

一旦明确,2N/3的界限很容易得到.

我们假设树中的节点总数是N.

树中的节点数= 1 +(左子树中的节点数)+(右子树中的节点数)

对于树的最后一层半满的情况,我们假设右子树是高度h,那么左子树是高度(h + 1):

Left Subtree中的节点数= 1 + 2 + 4 + 8 .... 2 ^(h + 1)= 2 ^(h + 2)-1 .....(i)

右子树中的节点数= 1 + 2 + 4 + 8 .... 2 ^(h)= 2 ^(h + 1)-1 .....(ii)

因此,插入:

树中的节点数= 1 +(左子树中的节点数)+(右子树中的节点数)

=> N = 1 + (2^(h+2)-1) + (2^(h+1)-1)

=> N = 1 + 3*(2^(h+1)) - 2

=> N = 3*(2^(h+1)) -1

=> 2^(h+1) = (N + 1)/3

将此值插入等式(i),我们得到:

Number of nodes in Left Subtree = 2^(h+2)-1 = 2*(N+1)/3 -1 =(2N-1)/3 < (2N/3)

因此,具有N个节点的树的子树中的最大节点数的上限是2N/3.

Answer 3

对于高度的完整二叉树h,节点数是f(h) = 2^h - 1.在上面的例子中,我们有几乎完整的二叉树,下半部分已满.我们可以将其视为集合root + left complete tree + right complete tree.如果原始树的高度是h,那么左边的高度是h - 1右边h - 2.等式变成了

n = 1 + f(h-1) + f(h-2) (1)

我们想要解决上面f(h-1)表达的问题n

f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/2 (2)

在(1)中使用上面我们有

n = 1 + f(h-1) + (f(h-1) - 1)/2 = 1/2 + 3*f(h-1)/2

=> f(h-1) = 2*(n-1/2)/3

因此O(2n/3)