algorithm - clrs书中heapsort算法的声明

Question

请解释图中划线的部分。它来自 CLRS 的第 6.2 节。子树的大小最多为 2n/3 是多少？

Answer 1

请记住，对于时间复杂度而言，二叉树的平衡通常是一件好事!最坏情况下的时间复杂度发生在树最不平衡的时候。我们在这里使用堆 - 堆是 complete二叉树。一棵完整的树可能具有的最不平衡是当它的最底层是半满时。如下所示。

          -------*-------
         /                \
        *                  *
       / \                / \
      /   \              /   \
     /     \            /     \
    /-------\          /-------\
   /---------\                       <-- last level is half-full

假设最后一层有m个节点。那么左子树中必然还剩下m-1个节点。

          -------*-------
         /                \
        *                  *
       / \                / \
      /   \              /   \
     / m-1 \            /     \
    /-------\          /-------\
   /--- m ---\  

为什么？一般而言，具有 m 个叶节点的树必须具有 m - 1 个内部节点。想象一下，如果这 m 个叶节点代表 tournament 中的玩家，如果每场比赛淘汰一名选手，则必须进行m-1场比赛才能决出胜负。每个游戏对应一个内部节点。因此有m - 1个内部节点。

因为树是完整的，所以右子树也必须有m - 1个节点。

          -------*-------
         /                \
        *                  *
       / \                / \
      /   \              /   \
     / m-1 \            / m-1 \
    /-------\          /-------\
   /--- m ---\  

因此我们有节点总数(包括根节点):

n = 1 + [(m - 1) + m] + (m - 1)
  = 3m - 1

令 x = 左子树中的节点数。然后:

x = (m - 1) + m
  = 2m - 1

我们可以求解这些联立方程，消除变量 m:

2n - 3x = 1
      x = (2n - 1) / 3

因此 x 小于 2n/3。这解释了原始声明:

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