[理工] [資結] BST尋找中間值問題!

看板Grad-ProbAsk作者 (綜合水果武士)時間15年前 (2011/02/12 21:53), 編輯推噓2(2推 0噓 6→)
留言8則, 5人參與, 最新討論串1/1
題目就是若BST各node存有鍵值,如何尋找中間值?(i.e n/2 lagest) 時間複雜度又是多少?是否可於O(logn)完成? 想不太出來...有請高手指點!感激不盡! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.84.231.145
→
02/12 22:08, , 1F
沒辦法吧? 等高手
02/12 22:08, 1F
→
02/12 22:48, , 2F
從N個node找, 光作traversal就要 O(N)了, 應該不可能在
02/12 22:48, 2F
→
02/12 22:48, , 3F
O(logn)裡找出來吧?
02/12 22:48, 3F
推
02/12 22:49, , 4F
要存有Rank 就可以O(log n) 不然是辦不到的
02/12 22:49, 4F
→
02/12 22:49, , 5F
有可能不用作traversal就找到中間值的方法嗎 @@?
02/12 22:49, 5F
推
02/12 22:50, , 6F
F大的意思是在construct的時候就先記住rank吧?!
02/12 22:50, 6F
→
02/12 22:53, , 7F
嗯, 不然樹都長好了, 要再標rank不就又是另一個麻煩
02/12 22:53, 7F
→
02/13 22:20, , 8F
請問所未的RANK指的是?要怎做才能O(logn)?
02/13 22:20, 8F
‣ 更多 st84514 的文章
文章代碼(AID): #1DLf3Wvz (Grad-ProbAsk)