在CLRS，三版，第155页，这是因为在MAX-HEAPIFY，

In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY,

孩子们的子树各有大小至多 2N / 3 -The最坏的情况下   当树的最底层是完全半满的发生。

The children’s subtrees each have size at most 2n/3—the worst case occurs when the bottom level of the tree is exactly half full.

我明白为什么这是最糟糕的时候，树的底部级别为半满。而且它也回答了这个问题最坏的情况下在MAX-HEAPIFY

I understand why it is worst when the bottom level of the tree is exactly half full. And it is also answered in this question worst case in MAX-HEAPIFY

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

My question is how to get 2n/3?

为什么如果底层是半满，那么孩子树的大小可达到2n / 3

Why if the bottom level is half full, then the size of the child tree is up to 2n/3?

如何计算的？

感谢

推荐答案

在一个树结构，其中每个节点有恰好为0或2个孩子，节点0子女数比节点带2个孩子的数目多一个。 {说明：节点中的高度h数为2 ^ h时，它通过的几何级数求和公式等于（节点总和从高度0到h-1）+ 1;而从高处0到h-1的所有节点都恰好有2个孩子}

In a tree where each node has exactly either 0 or 2 children, the number of nodes with 0 children is one more than the number of nodes with 2 children.{Explanation: number of nodes at height h is 2^h, which by the summation formula of a geometric series equals (sum of nodes from height 0 to h-1) + 1; and all the nodes from height 0 to h-1 are the nodes with exactly 2 children}

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

让k为在R节点的数目L中的节点的数量为k +（K + 1）= 2K + 1节点的总数为n = 1 +（2K + 1）+ K = 3K + 2（根加大号加R）。的比例为（2K + 1）/（3K + 2），这是由2/3以上为界。无恒小于2/3的作品，因为当k趋于无穷大的极限是2/3。

Let k be the number of nodes in R. The number of nodes in L is k + (k + 1) = 2k + 1. The total number of nodes is n = 1 + (2k + 1) + k = 3k + 2 (root plus L plus R). The ratio is (2k + 1)/(3k + 2), which is bounded above by 2/3. No constant less than 2/3 works, because the limit as k goes to infinity is 2/3.