看板 [ Prob_Solve ]
討論串[問題] ancestry problem
共 15 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
2
3
下一頁
尾頁
#1
[問題] ancestry problem
推噓2(2推 0噓 5→)留言7則，0人參與, 最新作者hardcover (精裝版喔)時間17年前 (2007/06/20 14:49), 編輯資訊
4
0
0
內容預覽:
給一顆 binary tree，. 問某個 node 是不是另一個 node 的 ancestor，. 要在 constant time 決定。. 允許 O(n) 的 preprocessing。. n: # of node. 我做了幾次嚐試都失敗，至少要logn，. 3 種 traversal，也
#2
Re: [問題] ancestry problem
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者hardcover (精裝版喔)時間17年前 (2007/06/20 17:23), 編輯資訊
0
0
0
內容預覽:
對厚 ， 是 logn XD是我沒說清 楚 ，. O(n) 是指第一次，此後問你類似的問是你都要在 O(1) 之內回答。. thanks. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140.114.88.92.
#3
Re: [問題] ancestry problem
推噓1(1推 0噓 0→)留言1則，0人參與, 最新作者ledia時間17年前 (2007/06/20 17:49), 編輯資訊
0
0
0
內容預覽:
老實說, 我記得不是很清楚了 囧. 很對不起上這堂課的好老師 Orz. 不過如果方便的話, 我建議你可以翻一翻. Algorithms on Strings, Trees, and Sequences (Dan Gusfield). ISBN:0521585198. 這一本書. 裡面第八章是 Con
(還有281個字)
#4
Re: [問題] ancestry problem
推噓2(2推 0噓 8→)留言10則，0人參與, 最新作者LinkCar (Link)時間17年前 (2007/06/20 20:17), 編輯資訊
0
0
0
內容預覽:
這題應該是轉換成 +-1RQM 的問題。. 就可以在O(n) preprocessing結束。. 然後O(1)的詢問. 轉成RMQ要先做EULER TRAVERSAL. 路徑所經過的節點的，把該節點的LEVEL依序存在一個陣列裡。. 詢問兩節點間的最小LEVEL(在陣列內RANGE MIN QUER
(還有138個字)
#5
Re: [問題] ancestry problem
推噓3(3推 0噓 1→)留言4則，0人參與, 最新作者jeunder時間17年前 (2007/06/21 00:26), 編輯資訊
1
0
0
內容預覽:
來點直覺的想法吧~. 對 node 編號, 從 root 開始, 由上至下, 由左至右, 編號: 1, 2, 3, .... 如果 tree 不是 complete, 那麼空的 node 也要給編號.. 你會發現父子關係是.... 父親編號往左 shift 1 bit 等於左兒子編號, 再加 1 就
首頁
上一頁
1
2
3
下一頁
尾頁