作者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