Max-Heapify最糟糕的情况 – 你如何得到2n / 3？
在CLRS，第三版，第155页中给出了在MAX-HEAPIFY中，
每个子树的最大尺寸至多为2n / 3 ，最差的情况发生在树的底部正好满一半的时候。
我明白为什么最差的时候，树的底部正好是半满的。 在这个问题中也回答了MAX-HEAPIFY中的最坏情况：“最坏的情况发生在树的底部正好是半满的时候”
我的问题是如何获得2n / 3？
为什么如果最低水平是一半，那么子树的大小是2n / 3？
如何计算？
谢谢
在每个节点只有0个或2个子节点的树中，有0个子节点的节点数比1个有2个子节点的节点数多一个{说明：高度为h的节点数为2 ^ h，由几何级数的求和公式等于（从高度0到h-1的节点之和）+ 1; 所有从0到h-1的节点都是刚好有2个子节点的节点}
ROOT LR / \ / \ / \ / \ ----- ----- ***** 令k为R中的节点数.L中的节点数为k +（k + 1）= 2k + 1。节点总数为n = 1 +（2k + 1）+ k = 3k + 2 （根加L加R）。 比例是（2k + 1）/（3k + 2），其上限为2/3。 没有恒定不到2/3的作品，因为k的限制无穷大是2/3。
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）：
在左子树中的节点数= 1 + 2 + 4 + 8 … 2 ^（h + 1）= 2 ^（h + 2）-1 …..（i）
（ii）右子树中的节点数= 1 + 2 + 4 + 8 … 2 ^（h）= 2 ^（h + 1）
因此，插入：
树中的节点数= 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。
对于高度为h二叉树，节点数为f(h) = 2^h - 1 。 在上面的情况下，我们已经完成了下半部分完整的二叉树。 我们可以将其视为root + left complete tree + right complete tree集合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） f(h-2) = 2^(h-2) - 1 = (2^(h-1)-1+1)/2 - 1 = (f(h-1) - 1)/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）
添加到swen的答案。 当（2k + 1）/（3k + 2）趋向于2/3时，当k趋于无穷大时，
（k + 1 / k）/ k（3 + 2 / k）= Lim_（k→inf）（2k + 1）/（3k + 2）= Lim_ ）（2 + 1 / k）/（3 + 2 / k）
申请的限制，你会得到2/3
在 –
- 级别0，即根是2 ^ 0
- 1级是2 ^ 1
- 二级是2 ^ 2
- …
- 级别n是2 ^ n
从0级到n级的所有节点的总和，
- S = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + … + 2 ^ n
从几何级数求和规则我们知道
- （x-1）/（x-1）x ^ 0 + x ^ 1 + x ^ 2 + … + x ^
代入x = 2，我们得到
- S = 2 ^（n + 1）-1，即2 ^（n + 1）= S + 1
由于2 ^（n + 1）是第n + 1层的总节点数，可以说0个子节点的个数比2个子节点的个数多1个。
现在让我们计算左子树，右树和总数中的节点数。
- 假设root = k的左子树中的非叶节点的数量。
-
通过以上推理，左子树或者根= k + 1中的叶子节点的数目。根树的右子树中的非叶子节点的数目被称为树正好是半满的。
-
根的左子树中的节点总数= k + k + 1 = 2k +
- 树中节点的总数，n =（2k + 1）+ k + 1 = 3k + 2。
- （2k + 1）/（3k + 2）的节点数在2/3以上。
这就是说每个孩子的子树最多有2n / 3个大小的原因。
