作者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