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

[taitin (小南)]

※ 引述《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
→ assassin88:感謝你還特地解釋~這個我昨天有想通了
→ assassin88:我是以左右子樹算出的IL及IR對root而言每一次均少一
→ assassin88:因此root要再加迴左右子樹的node數~這樣想不知正確與否
→ taitin:YES