作者cormen5566 (風行者)
看板Grad-ProbAsk
標題Re: [問題] Binary Treee
時間Wed Apr 22 20:49:01 2009
※ 引述《peterpan126 (雲淡風輕)》之銘言：
: 例題.Why do we use a binary tree to represent a general tree?
: Please state your opinions.
: 可否給個完整的說明呢!謝謝..
因為可以減少浪費的空間!
若以degree d來論
每個node宣告如下圖:
______________________________
| data | link 1 | ... | link d |
______________________________
則具n個node的tree所真正有用到的link數為 n - 1
所有的link數卻有n*d個
所以,link的有效使用率為
(n * d - (n - 1)) / n * d
其中 d=2時為最佳使用率,i.e., n+1/2n
因此,多數人都使用Binary Tree來表示!!!
有錯請鞭囉^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.229.77.39
1F：→ peterpan126:謝謝 04/23 11:29