作者aassxxzz (poyu~)
看板Grad-ProbAsk
标题Re: [理工] [资结]-tree的证明..
时间Sat Feb 13 03:34:14 2010
首先先说明proper binary tree其实就是full binary tree.
(一开始没看到这一行就浪费了一堆时间做白工T T)
所以题目说有n个node，我令 n=(2^h)-1,height
步骤一跳过
步骤二令h<K时皆成立
考虑h=k
E(T)
=E(T左子树)+E(T右子树)+2^(h-1) 因为每增加一层深度，所以leaf的长度都+1
因子树之高必小於h，由归纳法假设可知...@#$@...
=l(T左子树)+N左子树-1 +l(T右子树)+N右子树-1 + 2^(h-1)
=[ l(T)-N左子树内部节点-N右子树内部节点 ] +N左子树-1 +N右子树-1 +2^(h-1)
每个internal node因为都会提高一层，所以长均要+1,除了root
=[ l(T) - (2^(h-2) -1) -(2^(h-2) -1) ] + 2^(h-1)-1-1 + 2^(h-1)-1-1 +2^(h-1)
= 删一删 = l(T) + 2^h -2 = l(T) + (2^h -1) -1 = l(T) + n-1
其实在第三个等号那边
可不用l(T)-N左子内-N右子内,直接l(T)-(2^(h-1)-1-1)也是可以(以整颗树的观点来看)
但是我都会先把树画出来再解，所以才会那样写(不然直接写都会忘东忘西)
其实这题跟离散比较有关XD
※ 引述《bernachom (Terry)》之铭言：
: http://u.battown.net/0y3
: 这好像是用数学归纳法证的..
: 可是一直没头绪..
: 麻烦各位帮忙了
: 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.122.216.23
※ 编辑: aassxxzz 来自: 122.122.216.23 (02/13 03:40)
※ 编辑: aassxxzz 来自: 122.122.216.23 (02/13 04:19)
1F：推 bernachom:谢谢您的帮忙^^ 02/13 10:54