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