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

Re: [問題] ancestry problem

看板Prob_Solve (計算數學 Problem Solving)作者時間17年前 (2007/06/21 00:26), 編輯推噓3(3推 0噓 1→)
留言4則, 3人參與, 最新討論串5/15 (看更多)
來點直覺的想法吧~ 對 node 編號, 從 root 開始, 由上至下, 由左至右, 編號: 1, 2, 3, ... 如果 tree 不是 complete, 那麼空的 node 也要給編號. 你會發現父子關係是... 父親編號往左 shift 1 bit 等於左兒子編號, 再加 1 就是右兒子. 所以... (剩下你自己想 XD) ※ 引述《hardcover (精裝版喔)》之銘言： : 給一顆 binary tree， : 問某個 node 是不是另一個 node 的 ancestor， : 要在 constant time 決定。 : 允許 O(n) 的 preprocessing。 : n: # of node : 我做了幾次嚐試都失敗，至少要logn， : 3 種 traversal，也看不出什麼線索。 : thanks -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.64.86.11
推
06/21 00:30, , 1F
thanks, 你這樣好像也要 logn
06/21 00:30, 1F
推
06/21 00:58, , 2F
有點困惑 (太久沒唸書了XD) 請問對整數 shift n bits (一
06/21 00:58, 2F
→
06/21 01:01, , 3F
次做完) 算是 O(1) 還是 O(n) ???
06/21 01:01, 3F
推
06/21 01:23, , 4F
這只有找直接的節點才是O(1),距離遠一點就是O(logn)
06/21 01:23, 4F
‣ 更多 jeunder 的文章
文章代碼(AID): #16ULLBS1 (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 5 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 jeunder 的文章
文章代碼(AID): #16ULLBS1 (Prob_Solve)