算法练习(96): 画出数组所对应的树(1.5.9)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 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 算法得到的结果。

答案

见分析