[理工] 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

感谢两位我再研究一下！

继续阅读