作者jeunder ()
看板Prob_Solve
标题Re: [问题] ancestry problem
时间Thu Jun 21 00:26:50 2007
来点直觉的想法吧~
对 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
1F：推 hardcover:thanks, 你这样好像也要 logn 06/21 00:30
2F：推 jeunder:有点困惑 (太久没念书了XD) 请问对整数 shift n bits (一 06/21 00:58
3F：→ jeunder:次做完) 算是 O(1) 还是 O(n) ??? 06/21 01:01
4F：推 ephesians:这只有找直接的节点才是O(1),距离远一点就是O(logn) 06/21 01:23