作者assassin88 (2010)
看板Grad-ProbAsk
標題[理工] [DS]-E=I+2N
時間Fri Jan 15 23:58:40 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
1F：→ ftpui:因為多了樹根 整個高度加一 01/16 00:02
2F：→ assassin88:那請問 I 的是？ 01/16 00:03
3F：推 taitin:還有自己的兩個邊阿 01/16 00:13
4F：→ assassin88:可是NL跟NR是代表左右子樹的node數~I就很奇怪= = 01/16 00:24
5F：推 taitin:應該說要計算root從左樹到外部的每個內部邊 01/16 00:25
6F：→ taitin:因為有NL個點，所以會有NL-1個邊，在加上根到左樹的邊 01/16 00:26
7F：→ taitin:有點像OBST的算法 01/16 00:27
8F：→ taitin:這樣子樹就會被多算一次，因為多了個根，每個邊都+1 01/16 00:28
9F：→ assassin88:我還是不懂= = 這個我卡好久..轉不過來XDD 01/16 11:48
10F：推 imnewlegend:把樹根拔掉再差回去 別鑽牛角尖 01/20 04:13