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

看板Grad-ProbAsk作者 (2010)時間14年前 (2010/01/15 23:58), 編輯推噓3(307)
留言10則, 4人參與, 最新討論串1/3 (看更多)
想請問關於這個定理, 再證明過程中, 最後會用到 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

01/16 00:02, , 1F
因為多了樹根 整個高度加一
01/16 00:02, 1F

01/16 00:03, , 2F
那請問 I 的是?
01/16 00:03, 2F

01/16 00:13, , 3F
還有自己的兩個邊阿
01/16 00:13, 3F

01/16 00:24, , 4F
可是NL跟NR是代表左右子樹的node數~I就很奇怪= =
01/16 00:24, 4F

01/16 00:25, , 5F
應該說要計算root從左樹到外部的每個內部邊
01/16 00:25, 5F

01/16 00:26, , 6F
因為有NL個點,所以會有NL-1個邊,在加上根到左樹的邊
01/16 00:26, 6F

01/16 00:27, , 7F
有點像OBST的算法
01/16 00:27, 7F

01/16 00:28, , 8F
這樣子樹就會被多算一次,因為多了個根,每個邊都+1
01/16 00:28, 8F

01/16 11:48, , 9F
我還是不懂= = 這個我卡好久..轉不過來XDD
01/16 11:48, 9F

01/20 04:13, , 10F
把樹根拔掉再差回去 別鑽牛角尖
01/20 04:13, 10F
文章代碼(AID): #1BK92oJi (Grad-ProbAsk)
文章代碼(AID): #1BK92oJi (Grad-ProbAsk)