[理工] DS AVLTree 時間複雜度問題

[mingcloud (逆宇)]

AVL Tree 的操作
找到第K個item(由小到大算過來第K個)
的時間是 O(logn)

想不太通原因
如果是先用inorder把全部的東西由小到大dump出來
然後再去找第K個
這樣子的話時間應該是 O(n) --> n個node dump出來的時間

但是為甚麼書上 跟 洪逸上課教的時候
都是說 O(logn) 想了一個晚上想不通@@

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.53.3
※ 編輯: mingcloud       來自: 118.166.53.3         (07/04 23:25)
推 bkt800216:樹的高度不是log n?
→ mingcloud:阿 我知道樹的高度是logn 但是樹高 跟 找到由小到大第K
→ mingcloud:個item 的關係是在?
推 FRAXIS:他是假設Tree中每個節點存有其子樹所含節點個數
→ FRAXIS:有子樹節點數目的資訊的話，就可以O(lg n)的時間內解決..
→ mingcloud:喔喔 好 感謝樓上大大的解說...原來有這個前提不知道
→ mingcloud:不過感覺他那個表格很多前提都沒有說得很清楚...
推 Numbstu:程式不會是這樣跑的(全部丟出來再挑) >>這樣是O(N)
→ Numbstu:但實際上不是這樣跑的;AVL是完整樹;用陣列儲存
→ Numbstu:但是在跑AVL時不會是sequence