作者EntHeEnd (...)
看板Grad-ProbAsk
標題Re: [理工] [資結]-交大98-資訊聯招-DS&algo核對
時間Mon Feb 8 22:46:56 2010
請問一下 union by weight
和 union by rank 的差別
是union by weight 要把 set 點數少的 接到點數多的嗎 ?
然後 union by rank 是要把tree高度小的 接到高度大的
可是我看課本上面 union by weight
似乎是針對用linked list 表達的 set用的
他的list 長度就是他的weight
所以他問uoion by weight時
是把它本來的tree 當成用一個linked list存
(這樣算weight似乎比較合理 還是說weight就直接算該set的總node數就好了)
另外如果是union by weight 就是把總點數少的 接到多的那棵tree 的root就好
不用去管高度
union by rank(height)才是看高度 ?
※ 引述《qwertz (人生苦短，來日方長)》之銘言：
: 3-(6) after collaps
: k k
: ↗ ↖ ↗↑↖
: j P i j p
: ↗ ↗↑↖ ↗↑↖
: i q r s q r s
: 這題我有問題
: 題目的 Union 要求不是用 weighting rule 嗎
: 樹根 p 的樹的 node 數 > 樹根 k 的 node 樹
: 4 3
: 所以Union過後應該是像下圖這樣嗎?
: p
: ↗ ↗ ↖ ↖
: q r s k
: ↗
: j
: ↗
: i
: 然後執行 collasing rule 的 Find(i) 之後變成
: p
: ↗ ↗ ↗ ↖ ↖ ↖
: q r s k i j
: 這樣對嘛?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.125.176
1F：→ taitin:weight的定義就是針對node數來定義的 02/08 23:35
2F：→ taitin:rank的話我沒看過XD，應該是你說的那樣 02/08 23:40
3F：→ EntHeEnd:喔喔 感謝 因為我看課本weight他似乎是用在單linked list 02/08 23:57
4F：→ EntHeEnd:計算他的長度已得到weight 02/08 23:58