作者taitin (小南)
看板Grad-ProbAsk
标题Re: [理工] [DS]-E = I + 2N
时间Sat Jan 16 23:08:17 2010
※ 引述《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
1F：→ assassin88:感谢你还特地解释~这个我昨天有想通了 01/17 17:53
2F：→ assassin88:我是以左右子树算出的IL及IR对root而言每一次均少一 01/17 17:54
3F：→ assassin88:因此root要再加回左右子树的node数~这样想不知正确与否 01/17 17:54
4F：→ taitin:YES 01/17 22:17