PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] ancestry problem

看板Prob_Solve (計算數學 Problem Solving)作者 (Link)時間17年前 (2007/06/20 20:17), 編輯推噓2(2推 0噓 8→)
留言10則, 3人參與, 最新討論串4/15 (看更多)
※ 引述《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
推
06/20 20:34, , 1F
應該是 RMQ ? (Range Min Query) 據我所知, RMQ 會 reduct
06/20 20:34, 1F
→
06/20 20:34, , 2F
http://0rz.tw/072N8 試試看吧= =，要花一點時間看
06/20 20:34, 2F
→
06/20 20:37, , 3F
對= =是RMQ 對不起我錯了
06/20 20:37, 3F
→
06/20 20:35, , 4F
到 lowest common ancestor
06/20 20:35, 4F
→
06/20 20:38, , 5F
其實是我題目看錯了....對不起
06/20 20:38, 5F
→
06/20 20:38, , 6F
或是有更好的做法?
06/20 20:38, 6F
→
06/20 20:42, , 7F
這樣應該可以用..就判對LCA是不是詢問的兩個節點之一
06/20 20:42, 7F
→
06/20 20:43, , 8F
這是廣用解法，單問A是不是B的祖先應該有很簡單的方法
06/20 20:43, 8F
※ 編輯: LinkCar 來自: 61.230.15.240 (06/20 20:46)
推
06/20 20:52, , 9F
wow, 看起來 +-1 RMQ 簡單好用, 我覺得夠好了 XD
06/20 20:52, 9F
→
06/21 00:31, , 10F
感恩哩
06/21 00:31, 10F
‣ 更多 LinkCar 的文章
文章代碼(AID): #16UHgyil (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 LinkCar 的文章
文章代碼(AID): #16UHgyil (Prob_Solve)