Re: [理工] [DS]-E = I + 2N

[chris750630 (何去何從？)]

※ 引述《assassin88 (2010)》之銘言：
: 想請問關於這個定理，
: 再證明過程中，
: 最後會用到 I = IL + IR + ( NL + NR ) // 請問會什麼要加上 ( NL + NR )？
: 另外，E = EL + ER + ( NL + 1 ) + ( NR + 1 ) // 為何加 ( NL + 1 ) + ( NR + 1 )？
: 麻煩了~~

E=I+2n

I.B.  n=1 => I=0 E=2=I+2n 成立
I.H.  n<=k  E=I+2k 成立
I.S.  n`=k+1 E`=E+3=I+2k+3=I+1+2(k+1)=I`+2n 成立
       A
      / \
     B   C          => E`=E+1+2
    / <- 欲加入        I`=I+1
   D                   n`=n+1

故根據M.I. E=I+2n 成立
==========
為啥沒有 ( NL + NR ) or ( NL + 1 ) + ( NR + 1 ).....

--

我絕對不會說 這是我的無名.........

http://www.wretch.cc/blog/chris750630

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 203.73.27.116
推 taitin:他的方法是bottom up  加的節點是根
→ taitin:可是你的是由上往下，加的是leave
→ chris750630:soga
推 assassin88:@@