作者march20 ()
看板Prob_Solve
标题Re: [问题] ancestry problem
时间Thu Jun 21 07:45:08 2007
※ 引述《jeunder ()》之铭言：
: 标题: Re: [问题] ancestry problem
: 时间: Thu Jun 21 00:26:50 2007
:
: 来点直觉的想法吧~
:
: 对 node 编号, 从 root 开始, 由上至下, 由左至右, 编号: 1, 2, 3, ...
: 如果 tree 不是 complete, 那麽空的 node 也要给编号.
:
: 你会发现父子关系是...
: 父亲编号往左 shift 1 bit 等於左儿子编号, 再加 1 就是右儿子.
:
: 所以... (剩下你自己想 XD)
:
: 推 hardcover:thanks, 你这样好像也要 logn 06/21 00:30
我想原 jeunder 是想这样做的
先跑一次对全部的 node 做编号, 这是 O(n)
(DFS 即可, 所以时间复杂度是 O(|V| + |E|), 因为是 binary tree,
所以是 O(|V|) , 也就是 O(n))
每个node 的编号就是该 node 同高度的 full binary 里的编号
(想像没有长出来的 node 编号是空的. 不过要注意, 这些空的 node 并没真的去 visit)
: 推 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
不是 O(1) 也不是 O(log n), 其实是 O(n) @@
对整数 shift n bits 确实是 O(1), 但如果这颗树的高度是 100, 200,
(一代单传的树, 然後传 100 或 200 代就是了, 并不难造 XD)
或怎更多时, 铁定不是 O(1) 可以完成的 XD
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 128.54.49.35
※ 编辑: march20 来自: 128.54.49.35 (06/21 07:45)
※ 编辑: march20 来自: 128.54.49.35 (06/21 07:46)
1F：推 TonyQ:在complete tree的case下是 O(lgn) (因为高度就是lgn) 06/21 12:20
2F：→ TonyQ:其他的状况就应该是 O(n) (上限n) 06/21 12:21
3F：推 ephesians:为什麽是O(n),以二元树的情况明明不做阵列循序搜寻 06/21 13:24
4F：推 march20:你是说前置的 O(n) 还是後面单次 query 的 O(n)? 06/21 14:52
5F：推 march20:如果是後者. 呃, 如果今天好死不死这个 binary tree 06/21 14:53
6F：推 march20:全都是 degree 2 的 node, 然後要查的点刚好是 首跟尾 06/21 14:53
7F：推 march20:这样不就相当於 "全部找一遍" 了吗? 06/21 14:54
8F：推 march20:盲点在於, 树高=lg(n) 只有在 complete tree 才成立 06/21 14:55
9F：推 march20:对任意树来说, 应该说 "平均来说, 树高约略是 log(n)" 06/21 14:56
10F：推 march20:(啊, 以上说法有bug, 应该是 degree=1 的 node 有二, 其 06/21 14:58
11F：推 march20:余 degree 皆为 2 ) 06/21 14:59
12F：推 ephesians:当然是query啊,建树一定是O(n)嘛,有什麽好考虑的? 06/21 17:48
※ 编辑: march20 来自: 71.136.243.18 (06/22 16:52)