[理工]資結觀念一問

[ssssIssss (O_O)]

http://i.imgur.com/0wNqjKL.jpg

對於以下兩個複雜度，不太理解緣由，跪求解釋

1.search kth item in AVL tree =O(logn)
   不是很理解此處要如何以logn搜得

2.output all data elements in order in singly linked-list =O(n)
  也不是很懂，我想到最快的方法是先全output再排序，要O(nlogn)

感謝大家，剩不多天了，加油！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.94.109
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486180080.A.958.html
※ 編輯: ssssIssss (140.112.94.109), 02/04/2017 11:48:45
推 Transfat: 第二題應該是已經假設linked-list已經sorted好，再outpu
→ Transfat: t出來，才會是O(n)
考場上，遇到都要預先假設sorted？
推 s89162504: avl高度logn搜尋走到葉子最多也是logn次比較
是的，不過kth的話，應該要在每個node上附上他擁有的左子樹的node樹以供判斷，所以
我覺得O(logn)不太能理解@@
※ 編輯: ssssIssss (140.112.94.109), 02/04/2017 12:25:22
推 s89162504: 每個點都記說比自己小的有幾個 可以在logn統計出來 更
→ s89162504: 新只要常數
是分攤的概念嗎？在建樹的時候每次都順便花常數時間記下比自己小的（像是在insert n
ew node時路過便更新），然後search時就只要花費O(logn)找出k便可？
※ 編輯: ssssIssss (140.112.94.109), 02/04/2017 12:29:13
推 Transfat: 我是會假設已經sorted好欸，因為課本上也是寫O(n) //沒
→ Transfat: 記錯的話

如同遇到linked-list的insert和delete一樣，直接假設已經的得到前一個node，所以只
需O(1)嗎，懂了！
※ 編輯: ssssIssss (223.136.98.91), 02/04/2017 12:45:20
推 Transfat: 沒錯～
→ aa06697: 第一題可以google augmented bst 在建樹時要先記錄一些值
推 cjoek: AVL TREE本身就是 Binary Search tree 所以對他做中序巡防
→ cjoek: 就可以照順序印出來了
推 cjoek: 回錯了 sorry QQ
→ gigayaya: 1:你要找第k個，先算root的樹高，比k大就去左子樹找，
→ gigayaya: 比k小去右子樹找k-高，如此遞迴，你每次的成本就是在算
→ gigayaya: 樹高=O(nlogn)
→ gigayaya: 打錯，每次算樹高=(logn)
→ ken52011219: 應該不用到 augmenting BST 只是search而已
→ ken52011219: augmenting BST 主要目的在 find min or max 可以不
→ ken52011219: 用到 logn
推 FRAXIS: 不用 augmenting BST 要怎樣在O(lg n)時間內找到第 k 大？
→ ken52011219: 不是問 K th 嗎@@? 還是我理解有誤
是問kth沒錯喔！

我找到解法了，它命名為Augmented tree data structure，不知道跟你們說的Augmented
 BST是否一樣

作法如下：建樹時，順便記錄自己左子樹的node數（假設為n）。在做search kth時，確
定root，若k=n+1則得解為root，若k<n+1則往左走、k>n+1則往右。最多走tree的高。

複雜度為O(logn)
※ 編輯: ssssIssss (140.112.94.109), 02/05/2017 10:40:28
→ ken52011219: 我重新看了一次argument data structure , AA大說的
→ ken52011219: 沒錯 是我觀念有誤
考前多得到一個觀念就是賺啊！XD
※ 編輯: ssssIssss (140.112.94.109), 02/05/2017 11:32:13