文章目录
  1. 1. 证明:在任一含n个元素的堆中,至多有$\lceil n/2^{h+1} \rceil$高度为h的节点
  2. 2. 第一种证明Base Case的方法
  3. 3. 第二种证明Base Case的方法
  4. 4. Inductive step

证明:在任一含n个元素的堆中,至多有$\lceil n/2^{h+1} \rceil$高度为h的节点

此题我觉得意义不是很大,肯定有更加优雅的证明方法。有趣的是答案基本上把二叉树的性质都来了一遍,所以我就当做复习,把它翻译下来了。

用数学归纳法证明。

Base case:此处,n非变量而h为变量,我们设h = 0的时候,即高度为0的时候,至多有$\lceil n/2 \rceil$ 个高度为0的节点。

注意,堆可以被当做为一棵完全二叉树,最后一层可能除外

第一种证明Base Case的方法

第一个性质是,令x是深度H(H为树的高度)的节点数量,这里有$n-x$为奇数。这点很容易证明,把深度为H的节点取下来后,剩下的就是一颗完全二叉树,所以$n-x$必然为奇数。

另外一个性质是,在任何非空二叉树中,度为2的节点的个数比叶节点个数少1, 即$f(n) = n-1$。这个性质也可以用数学归纳法证明:

Base case: 当$n=1$时,度为2的节点数为0, 满足条件。

Inductive step: 当$f(n) = n-1$时,$f(n+1) = n$。

对于任意的二叉树,增加一个节点的可能性只有两种,一:使某个度0节点变成度1节点,二:使某个度1节点变成度2节点。对于第一种情况,叶节点不变,度2节点不变,对于第二种情况,叶节点和度二节点都加一,故Inductive step也成立。

由于高度为0的节点都是叶节点,而度2节点都是内部节点,当最深节点数为偶数的时候,内部节点也就是度二节点,所以存在$n = 2k - 1$ (k为高度为0的节点),$k = \lceil n/2 \rceil$, 故Base case成立。同样,当最深节点数为奇数的时候,我们把它加到偶数,即k+1 = $\lceil (n+1)/2 \rceil =\lceil n/2 \rceil + 1$,等于号成立因为n是偶数。

第二种证明Base Case的方法

令x是深度的节点数量,当x是偶数的时候,存在x/2个节点是深度H节点的母节点。因此存在$2^{H-1}-x/2$个节点不是深度H节点的母节点,所以高度0节点的数量为

$$2^{H-1}-x/2+x = 2^H/2+x/2 = (2^H + x)/2 = \lceil (x^H+x-1)/2 \rceil = \lceil n/2 \rceil$$

注意,$n = 2^H + x - 1$因为整个树从0深度到H-1深度有$2^H - 1$个节点,H深度有x个节点。

同样,对于x为奇数,存在

$$x-1+2^{H-1}-(x-1)/2 = (2^H+x-1)/2 = n/2 = \lceil n/2 \rceil$$

Inductive step

令$n_h$为T树高度h的节点数量。

令H’为H移除叶子后的数,$n^{\prime} = n - n_0 = n - \lceil n/2 \rceil = \lfloor n/2 \rfloor $(根据base case)。

请注意,T树中原来高度为h的节点在T’树上高度都-1,即

$$ n_h = n^{\prime}_{h-1} $$

所以

$$n_h = n^{\prime}_{h-1} \leq \lceil n^{\prime}/2^h \rceil = \lceil \lfloor n/2 \rfloor /2^h \rceil \leq \lceil (n/2)/2^h \rceil = \lceil n/2^{h+1} \rceil$$

实际上这里的数学归纳法并不直观。它把一棵高度为h的树的高度$n_s(s=1,2..h)$拆成base case,也就是说,在某树下,有满足以当时n’的$\lceil n’/2 \rceil$个高度为0的节点,而在树不停的增长过程中,到倒数第二步的时候,假设满足此时n’有$\lceil n’/2^h \rceil$个高度为h-1的节点,推导至最后的结论。反过来说,作为某高度h的节点$\lceil n/2^{h+1} \rceil$之所以满足是因为每取走它的叶子,那些节点的高度-1,而n亦对折,最后这些节点暴露成0高度节点。

文章目录
  1. 1. 证明:在任一含n个元素的堆中,至多有$\lceil n/2^{h+1} \rceil$高度为h的节点
  2. 2. 第一种证明Base Case的方法
  3. 3. 第二种证明Base Case的方法
  4. 4. Inductive step