作者LinkCar (Link)
看板Prob_Solve
標題Re: [問題] ancestry problem
時間Wed Jun 20 20:16:59 2007
※ 引述《hardcover (精裝版喔)》之銘言：
: 給一顆 binary tree，
: 問某個 node 是不是另一個 node 的 ancestor，
: 要在 constant time 決定。
: 允許 O(n) 的 preprocessing。
: n: # of node
: 我做了幾次嚐試都失敗，至少要logn，
: 3 種 traversal，也看不出什麼線索。
: thanks
這題應該是轉換成 +-1RQM 的問題。
就可以在O(n) preprocessing結束。
然後O(1)的詢問
轉成RMQ要先做EULER TRAVERSAL
路徑所經過的節點的，把該節點的LEVEL依序存在一個陣列裡。
詢問兩節點間的最小LEVEL(在陣列內RANGE MIN QUERY)
又TREE裡面節點跟節點之間高度只差一，所以陣列裡面兩兩相鄰差一。
因此叫做+-1RMQ
....
....
但是RMQ怎麼以O(n)preprocess
我以前有看過文章....但是文章找不到了，他的方法我也沒學起來@@
我找到文章再丟連結，我一時找不到我那時候看的文章
抱歉，看到同樣問題分享一下我的經驗，雖然還沒解決問題= =
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.15.240
1F：推 ledia:應該是 RMQ ? (Range Min Query) 據我所知, RMQ 會 reduct 06/20 20:34
3F：→ LinkCar:對= =是RMQ 對不起我錯了 06/20 20:37
4F：→ ledia:到 lowest common ancestor 06/20 20:35
5F：→ LinkCar:其實是我題目看錯了....對不起 06/20 20:38
6F：→ ledia:或是有更好的做法? 06/20 20:38
7F：→ LinkCar:這樣應該可以用..就判對LCA是不是詢問的兩個節點之一 06/20 20:42
8F：→ LinkCar:這是廣用解法，單問A是不是B的祖先應該有很簡單的方法 06/20 20:43
※ 編輯: LinkCar 來自: 61.230.15.240 (06/20 20:46)
9F：推 ledia:wow, 看起來 +-1 RMQ 簡單好用, 我覺得夠好了 XD 06/20 20:52
10F：→ hardcover:感恩哩 06/21 00:31