Re: [理工] [DS]-E = I + 2N
※ 引述《assassin88 (2010)》之銘言：
: 想請問關於這個定理，
: 再證明過程中，
: 最後會用到 I = IL + IR + ( NL + NR ) // 請問會什麼要加上 ( NL + NR )？
: 另外，E = EL + ER + ( NL + 1 ) + ( NR + 1 ) // 為何加 ( NL + 1 ) + ( NR + 1 )？
: 麻煩了~~
假設一個情況 A
/ \
樹甲 B C (B,C為內部節點)則 I1=2 =>AB+AC
D
/
A
/ \
樹乙 B C I=2+2+1=5 ....(1)
但其實I也可以這樣算
I= I1+DA+AB+AC=2AB+2AC+DA跟1式中的2+2+1是一樣的意思
因為AB跟AC被加了兩次
而其實 AB+AC+DA這三個邊跟樹甲的node數有關
可以發現當node數為3的時候也多加了3
這是因為樹甲三個點的樹本來就只有3-1個邊
再加上D點加入後多出的DA這個邊
因此可得知 若子樹N個節點
新樹的 內部路徑=子樹的內部路徑+子樹的節點數
也就是 I=IL+NL的由來。
同理，右子樹也一樣
因此 I=IL+NL+IR+NR
而外部路徑的概念應該要跟這個是一樣的，
只是他多了一個邊所以要加一
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.224.78
→
01/17 17:53, , 1F
01/17 17:53, 1F
→
01/17 17:54, , 2F
01/17 17:54, 2F
→
01/17 17:54, , 3F
01/17 17:54, 3F
→
01/17 22:17, , 4F
01/17 22:17, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：