[理工] 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 只要更新該更新的地方就好了..

繼續閱讀