請教一下各位大大對於這兩題的看法
105 台大電機丙 資結 如圖
https://i.imgur.com/5tazIR9.png
這題 有多一個 equal 害我不知道應該是false 還是 true
因為他們 insert 都是 O( n log n )
這題不知道該用實際時間還是用複雜度時間...
還是這題的shorter是指樹的高度...?
106 台大電機丙 資結 如圖
https://i.imgur.com/1bYNigY.png
這個題目的意思
是有可能建完變成 balanced binary tree 嗎?
還是不管怎麼建都是 unbalanced binary tree ?
麻煩各位大大惹

覺得第一題是指樹高,false(三個點的時候)

這些是多選題嗎？12 abc 都不對 d 是對的e 的話是 O(n) 那題目寫 O(n log n) 應該也沒錯？

12.A的機率要怎麼算啊@@

你只要考慮 n = 2^k - 1 的情況 隨機插入變成 perfectbalanced search tree 機率非常非常小..

12 (b) amortized的情況下為什麼不是O(log n) ?

expected 是 O(log n), amortized 應該不會是O(log n)因為 amortized 是指一連串的 operation 的 worst case執行時間 隨機插入的話 有 > 0 的機率 樹會非常不平衡所以 amortized 沒辦法是 O(log n)

第一題我寫true,找不到反例，有大大可以找出個反例嗎 感謝

如果題目指的是樹高，這應該是反例如果是執行時間AVL Tree應該會快一些https://i.imgur.com/nN5HpGc.jpg

e 為什麼比較緊的upper bound是O(n)？不是直接建一個AVL tree給n個data，所以是O（nlogn）嗎？順便問題目的意思，使不平衡變平衡，有這種演算法調整嗎？類似heap的bottom-up法

先 inorder traverse 把元素存成 sorted array然後 sorted array 轉 balanced tree這樣作會使用額外 O(n) 的空間 不過實際上有其他方法可以O(n) 時間 O(1) 空間把 unbalnaced tree變成balanced tree可以搜 Day–Stout–Warren algorithm

推F大，受益良多XD

原來如此，又是一個thread bt應用嗎謝f大，順便問有些題目出題者的想法，我記得有時候題目的upper bound不夠緊，答案就會算錯那像這種時候，這題的e到底可不可以算對呢？還是要寫老師想看的答案？

我想除了改考卷的人之外沒人可以回答這問題吧..

我認為選擇題就選對的，計算、簡答題才要寫tight的我認為選擇題就選對的，計算、簡答題才要寫tight的