作者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/m.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