algorithm - Max-Heapify 中的最坏情况——如何获得 2n/3？

Question

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

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.

我理解为什么当树的底层刚好半满时情况最糟。并且在这个问题中也有回答worst case in MAX-HEAPIFY: "the worst case occurs when the bottom level of the tree is exactly half full"

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

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

如何计算？

谢谢

Answer 1

在一棵树中，每个节点恰好有 0 个或 2 个子节点，具有 0 个子节点的节点数比具有 2 个子节点的节点数多 1。{解释:高度为 h 的节点数为 2^h，通过几何级数的求和公式等于(从高度0到h-1的节点之和)+ 1；并且所有从高度 0 到 h-1 的节点都是恰好有 2 个 child 的节点

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

设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。