作者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)