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