本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- union
题目
1.5.9 画出下面的 id[] 数组所对应的树。这可能是加权 quick-union 算法得到的结果吗？解释为什么不可能，或者给出能够得到该数组的一系列操作。
1.5.9 Draw the tree corresponding to the id[] array depicted at right. Can this be the result of running weighted quick-union? Explain why this is impossible or give a sequence of operations that results in this array.
分析
要解决这个问题，我们先看一下书中的这张图：
书中的这张图很直观的展示了树和数组之间的转化关系，也就是说要想找到数组对应的树，关键是要找到根节点(根节点的i值和id[i]是一致的)。找到根节点后再去找其他节点的值。
回到这题，我们也能很容易找到根节点，就是
| i | 1 |
|---|---|
| id[i] | 1 |
找到了根节点其他节点顺藤摸瓜即可。
第一步，找到根节点
第二步，找到1对应的0、3和6，即是1的子节点
| i | 0 | 3 | 6 |
|---|---|---|---|
| id[i] | 0 | 1 | 1 |
依次类推，我们就能得到树的图为：
乍一看，这个图满足 加权union-find的条件：每个节点的子节点都是“平衡”的，但回到书中，我们看一下这个定理：
就可以知道这个树的大小是10，深度为4，因为 lg10 < 4，所以并不满足“加权union-find算法构造的森林中的任意节点的深度最多为lgN”这个条件。因此这个表不可能是加权 quick-union 算法得到的结果。
答案
见分析
