Re: [問題] ancestry problem

[march20 ()]

※ 引述《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)
推 TonyQ:在complete tree的case下是 O(lgn) (因為高度就是lgn)
→ TonyQ:其他的狀況就應該是 O(n)  (上限n)
推 ephesians:為什麼是O(n),以二元樹的情況明明不做陣列循序搜尋
推 march20:你是說前置的 O(n) 還是後面單次 query 的 O(n)?
推 march20:如果是後者. 呃, 如果今天好死不死這個 binary tree
推 march20:全都是 degree 2 的 node, 然後要查的點剛好是 首跟尾
推 march20:這樣不就相當於 "全部找一遍" 了嗎?
推 march20:盲點在於, 樹高=lg(n) 只有在 complete tree 才成立
推 march20:對任意樹來說, 應該說 "平均來說, 樹高約略是 log(n)"
推 march20:(啊, 以上說法有bug, 應該是 degree=1 的 node 有二, 其
推 march20:餘 degree 皆為 2 )
推 ephesians:當然是query啊,建樹一定是O(n)嘛,有什麼好考慮的?
※ 編輯: march20         來自: 71.136.243.18        (06/22 16:52)