[理工] 107台大电机丙资演 sdfg014025xx PTT批踢踢实业坊

楼主: sdfg014025xx (随便就好) 2019-02-11 00:36:45

https://i.imgur.com/QWtUB1H.jpg
想请问第八题是T还是F
我总觉得insertion不会到O(n)这么多？

作者: alen0303 (艾伦零参智商负三) 2019-02-11 02:01:00

感觉是false 只要O(logn)

作者: liu1030 (113鸡鸡男) 2019-02-11 03:29:00

balanced O(logn)

作者: realmanKG (各位观众，五支菸) 2019-02-11 20:39:00

请问楼上为什么是O(logn)? 我的看法是今天若是做了rotation势必要对所有节点都去做一次更新，如t()就是一定得要从最后一个node开始一个一个更新的，不知道能否说明得清楚点？感谢

作者: FRAXIS (喔喔) 2019-02-12 12:52:00

rotation 只要更新该更新的地方就好了..

继续阅读