Re: [問題] ancestry problem
看板Prob_Solve (計算數學 Problem Solving)作者march20時間17年前 (2007/06/22 16:39)推噓4(4推 0噓 3→)留言7則, 3人參與討論串11/15 (看更多)
※ 引述《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)
→
06/22 16:41, , 1F
06/22 16:41, 1F
推
06/22 17:58, , 2F
06/22 17:58, 2F
→
06/22 18:01, , 3F
06/22 18:01, 3F
→
06/22 18:02, , 4F
06/22 18:02, 4F
推
06/22 18:29, , 5F
06/22 18:29, 5F
推
06/22 19:00, , 6F
06/22 19:00, 6F
推
06/23 01:14, , 7F
06/23 01:14, 7F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 11 之 15 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
