作者march20 ()
看板Prob_Solve
標題Re: [問題] ancestry problem
時間Fri Jun 22 16:39:05 2007
※ 引述《hardcover (精裝版喔)》之銘言：
: 給一顆 binary tree，
: 問某個 node 是不是另一個 node 的 ancestor，
: 要在 constant time 決定。
: 允許 O(n) 的 preprocessing。
: n: # of node
: 我做了幾次嚐試都失敗，至少要logn，
: 3 種 traversal，也看不出什麼線索。
: thanks
啊, 來回覆原 po XD
一聽到這個題目, 印象中有個 disjoint set 相關的 data structure/algorithm
然後 time complexity 是 inverse Akerman function (可以當作 O(1) 來看).
一查果然有這題.
如果你手上有 CLRS 的 "Introduction to Algorithms" 第二版
請讀一下 chapter 21. 該章的習題最後一題剛好就是你問的問題.
(細節我全忘了, 請原諒版主懶惰 XD)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.136.243.18
※ 編輯: march20 來自: 71.136.243.18 (06/22 16:40)
1F：→ march20:CLRS="Cormen, Leiserson, Rivest, Stein" 06/22 16:41
2F：推 seanwu:好漂亮的作法....不過複雜度似乎不是 O(1) ? 06/22 17:58
3F：→ seanwu:它的O(A(n))只是disjoint-set的效率，當然跟整體有關， 06/22 18:01
4F：→ seanwu:但整個演算法的複雜度最差應該是O(n) ? 06/22 18:02
5F：推 LPH66:那還是算前處理吧? (如果是指那個遞迴的話) 06/22 18:29
6F：推 seanwu:嗯?不太明白，我以為每次問{u,v}都要叫一次? 06/22 19:00
7F：推 march20:又據說其實這就是 RMQ :P 06/23 01:14