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

[assassin88 (2010)]

想請問關於這個定理，

再證明過程中，

最後會用到 I = IL + IR + ( NL + NR ) // 請問會什麼要加上 ( NL + NR )？

另外，E = EL + ER + ( NL + 1 ) + ( NR + 1 ) // 為何加 ( NL + 1 ) + ( NR + 1 )？

麻煩了~~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.57.78.253
→ ftpui:因為多了樹根 整個高度加一
→ assassin88:那請問 I 的是？
推 taitin:還有自己的兩個邊阿
→ assassin88:可是NL跟NR是代表左右子樹的node數~I就很奇怪= =
推 taitin:應該說要計算root從左樹到外部的每個內部邊
→ taitin:因為有NL個點，所以會有NL-1個邊，在加上根到左樹的邊
→ taitin:有點像OBST的算法
→ taitin:這樣子樹就會被多算一次，因為多了個根，每個邊都+1
→ assassin88:我還是不懂= =   這個我卡好久..轉不過來XDD
推 imnewlegend:把樹根拔掉再差回去 別鑽牛角尖