Re: [理工] [資結]-交大98-資訊聯招-DS&algo核對
請問一下 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
→
02/08 23:35, , 1F
02/08 23:35, 1F
→
02/08 23:40, , 2F
02/08 23:40, 2F
→
02/08 23:57, , 3F
02/08 23:57, 3F
→
02/08 23:58, , 4F
02/08 23:58, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 9 篇)：