Re: [問題] ancestry problem

[march20 ()]

※ 引述《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)
→ march20:CLRS="Cormen, Leiserson, Rivest, Stein"
推 seanwu:好漂亮的作法....不過複雜度似乎不是 O(1) ?
→ seanwu:它的O(A(n))只是disjoint-set的效率，當然跟整體有關，
→ seanwu:但整個演算法的複雜度最差應該是O(n) ?
推 LPH66:那還是算前處理吧? (如果是指那個遞迴的話)
推 seanwu:嗯?不太明白，我以為每次問{u,v}都要叫一次?
推 march20:又據說其實這就是 RMQ :P