本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- 加权 quick-find 算法
题目
1.5.10 在加权 quick-union 算法中，假设我们将 id[find(p)] 的值设为 q 而非 id[find[q]]，所得的算法是正确的吗？答：是，但这会增加树的高度，因此无法保证同样的性能。
1.5.10 In the weighted quick-union algorithm,suppose that we set id[find(p)] to q instead of to id[find(q)]. Would the resulting algorithm be correct?Answer : Yes, but it would increase the tree height, so the performance guarantee would be invalid.
分析
我们看看find函数的代码
private int find(int p) { // Follow links to find a root.
while (p != id[p]) p = id[p];
return p;
}
然后看一下union函数
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
// Make smaller root point to larger one.
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
count--;
}
如果按题目中所说，做如下改动
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
if (sz[i] < sz[j]) {
id[i] = q;//改动1，将q直接作为id[i]的子节点
sz[j] += sz[i];
} else {
id[j] = p;//改动2，将p直接作为id[j]的子节点
sz[i] += sz[j];
}
count--;
}
我们仍然通过轨迹图来展示树的变化，以书中的图例为例：
显而易见，树的高度增加了。
答案
见分析
题目
1.5.11 实现加权 quick-find 算法，其中我们总是将较小的分量重命名为较大分量的标识符。
这种改变会对性能产生怎样的影响？
1.5.11 Implement weighted quick-find, where you always change the id[] entries of the smaller component to the identifier of the larger component. How does this change affect performance?
分析
题目尚未看懂，待分析
