推 hardcover:thanks, 你這樣好像也要 logn 06/21 00:30
推 jeunder:有點困惑 (太久沒唸書了XD) 請問對整數 shift n bits (一 06/21 00:58
→ jeunder:次做完) 算是 O(1) 還是 O(n) ??? 06/21 01:01
推 ephesians:這只有找直接的節點才是O(1),距離遠一點就是O(logn) 06/21 01:23
來點直覺的想法吧~
對 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