作者gash55025502 (白影弓)
看板Grad-ProbAsk
标题[理工] 106清大计科
时间Sun Nov 24 00:39:59 2019
https://i.imgur.com/7slHXHc.jpg
https://i.imgur.com/pOfvmbj.jpg
想问一下这题
下面是我写的答案
因为他是问高度
我推到倒数第二行後就不知道该怎麽解了
想问一下这题的正确解法应该怎麽解才好 感谢各位～
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.75.80.197 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1574527201.A.AAD.html
1F：推 ekids1234: 不知道能不能说 AVL Tree 树高必定小<= Full BT 树高 11/24 02:06
2F：→ gash55025502: 楼上 同node数的情况下应该是AVLTree会比较高吧～？ 11/24 09:22
3F：→ gash55025502: 感觉full BT像是最小高度 但不知道最大高度要怎麽 11/24 09:23
4F：→ gash55025502: 表达 11/24 09:23
5F：推 mistel: 最大高度不是就是你写的那个吗？F2h-1的h是用最少节点能 11/24 12:31
6F：→ mistel: 形成的最高的AVL tree 11/24 12:31
7F：→ mistel: 但我觉得你这样写怪怪的 是怎麽推得h=O(logn)的？ 11/24 12:32
8F：→ gash55025502: 对 最後一句有点用猜的 我想问的是要怎麽推出h=O(?) 11/24 12:58
9F：推 zuchang: 左右同取log 不行吗 11/24 15:13
11F：→ b10007034: 其实你已经写得差不多了，捡个尾刀吧 11/24 15:32
12F：→ b10007034: 笔误，1/c在log里面 11/24 15:37
13F：→ gash55025502: 感谢两位 我再研究一下！ 11/24 18:00