请教一下各位大大对于这两题的看法
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的