tem*_*boy 5 algorithm quick-union
我需要帮助理解关于加权快速联合的问题给出的解释：
以下哪个
id[]数组可能是对一组10项目运行加权快速联合算法的结果？检查所有适用。回想一下，我们的加权快速联合算法使用按大小（节点数）联合（而不是按高度联合）。
不正确：
9 1 7 3 4 9 6 7 8 9
解释：9-5 7-2 5-0不正确：
2 2 2 2 5 1 2 3 1 2
解释：2-9 3-7 9-3 5-4 0-2 1-8 8-4 4-9 8-6正确：
9 9 3 4 9 4 9 9 4 2
说明：id[]数组包含一个循环：2->3->4->9->2正确：
0 2 3 0 0 2 2 9 3 0
解释：以父为2 <根的树的大小是以父为根的树的大小的两倍2正确：
0 4 6 7 4 1 5 1 7 3
解释：森林高度=4 > lg N = lg(10)
您还没有提供完整的上下文，但我将尝试根据我对加权联合的了解来回答。
我是否必须查看每个元素才能确定是否存在循环？
不。这会违背快速联合的目的。一个循环表示联合操作没有正确执行。并且任何时候都不应该有循环。
我怎么知道一棵树的大小？
最初所有树的大小为 1。在union操作中，我们对正在连接的 2 棵树的大小求和。我们通过一个数组来跟踪大小（比如SZ[]）。给定树的大小在数组 ( SZ[root(i)])中的根偏移处更新。
我怎么知道森林的高度？
这也必须被跟踪。最初所有树的高度都为 1。当您加入 2 棵树时 - 比如说A & B，您将 A 的根作为新根。那么加入的树的高度将是max(A.height, B.height+1).