[理工] 107台大電機丙 資演

[sdfg014025xx (隨便就好)]

https://i.imgur.com/QWtUB1H.jpg
想請問第八題是T還是F

我總覺得insertion不會到O(n)這麼多？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.138.157
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549816607.A.F12.html
→ alen0303: 感覺是false 只要O(logn)
推 liu1030: balanced O(logn)
推 realmanKG: 請問樓上為什麼是O(logn)? 我的看法是今天若是做了rota
→ realmanKG: tion勢必要對所有節點都去做一次更新，如t()就是一定得
→ realmanKG: 要從最後一個node開始一個一個更新的，不知道能否說明
→ realmanKG: 得清楚點？ 感謝
推 FRAXIS: rotation 只要更新該更新的地方就好了..