[理工] 資料結構的題目求教

看板Grad-ProbAsk作者 (阿鼎)時間11年前 (2015/01/24 21:45), 11年前編輯推噓5(5推 0噓 15→)
留言20則, 4人參與, 最新討論串1/1
(1)Find the average-case height of a binary tree with five nodes. You have to consider all possible binary trees with five nodes. Assume that each of these is equally likely to occur. (2)Approximate the best-case height of a binary tree with n nodes. (以big-O表 示) 請問這兩題怎麼解? 請高手幫個忙 囧RZ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 124.9.199.198 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422107134.A.69C.html ※ 編輯: sads333 (124.9.199.198), 01/24/2015 21:47:07
推
01/24 22:35, , 1F
(2)best case相當於高度最小化=complete B.T，N個no
01/24 22:35, 1F
→
01/24 22:35, , 2F
des的complete B.T的高度=log(N+1)取上高斯=O(logN)
01/24 22:35, 2F
→
01/24 22:45, , 3F
(1)5個nodes可以造出來的B.T=(1/6)*C(10,5)=42，其
01/24 22:45, 3F
→
01/24 22:45, , 4F
中高度3的有5種、高度5的有2種（畫出來就知道了），
01/24 22:45, 4F
→
01/24 22:45, , 5F
其餘皆為高度4，然後把總高度乘一乘加一加之後除以4
01/24 22:45, 5F
→
01/24 22:45, , 6F
2就是avg. case了吧
01/24 22:45, 6F
推
01/24 23:08, , 7F
高度3應該有6種?　可以height=0開始定義?
01/24 23:08, 7F
推
01/24 23:25, , 8F
哦對!少算一種,是6種沒錯
01/24 23:25, 8F
→
01/24 23:27, , 9F
題目沒給的話感覺自己假設height從0或1開始都ok
01/24 23:27, 9F
推
01/24 23:31, , 10F
這題是哪間學校的,還不錯!
01/24 23:31, 10F
→
01/25 01:07, , 11F
高度5的不只2種吧...
01/25 01:07, 11F
→
01/25 01:47, , 12F
好像是耶...一開始沒認真想只下意識想到左斜和右斜
01/25 01:47, 12F
→
01/25 01:47, , 13F
，2^4 !?
01/25 01:47, 13F
→
01/25 09:50, , 14F
哈 我也是....
01/25 09:50, 14F
→
01/25 14:38, , 15F
8種?
01/25 14:38, 15F
→
01/25 14:46, , 16F
我的想法是root之後的每個level都能選左或右，所以2
01/25 14:46, 16F
→
01/25 14:46, , 17F
^4
01/25 14:46, 17F
推
01/25 17:25, , 18F
印象台大有考過...15分
01/25 17:25, 18F
→
01/25 17:26, , 19F
總共好像...42?
01/25 17:26, 19F
→
01/25 17:26, , 20F
謝謝 確實16種
01/25 17:26, 20F
‣ 更多 sads333 的文章
文章代碼(AID): #1Kmw7-QS (Grad-ProbAsk)