[理工] 106清大計科 gash55025502 PTT批踢踢實業坊

作者: gash55025502 (白影弓) 2019-11-24 00:39:59

https://i.imgur.com/7slHXHc.jpg
https://i.imgur.com/pOfvmbj.jpg
想問一下這題
下面是我寫的答案
因為他是問高度
我推到倒數第二行後就不知道該怎麼解了
想問一下這題的正確解法應該怎麼解才好感謝各位～

作者: ekids1234 (∵:☆星痕╭☆) 2019-11-24 02:06:00

不知道能不能說 AVL Tree 樹高必定小<= Full BT 樹高

作者: gash55025502 (白影弓) 2019-11-24 09:22:00

樓上同node數的情況下應該是AVLTree會比較高吧～？感覺full BT像是最小高度但不知道最大高度要怎麼表達

作者: mistel (Mistel) 2019-11-24 12:31:00

最大高度不是就是你寫的那個嗎？F2h-1的h是用最少節點能形成的最高的AVL tree但我覺得你這樣寫怪怪的是怎麼推得h=O(logn)的？

作者: gash55025502 (白影弓) 2019-11-24 12:58:00

對最後一句有點用猜的我想問的是要怎麼推出h=O(?)

作者: zuchang (chang) 2019-11-24 15:13:00

左右同取log 不行嗎

作者: b10007034 (Warren) 2019-11-24 15:32:00

https://i.imgur.com/3uvmQFw.jpg其實你已經寫得差不多了，撿個尾刀吧筆誤，1/c在log裡面

作者: gash55025502 (白影弓) 2019-11-24 18:00:00

感謝兩位我再研究一下！

繼續閱讀