工会找到分离集加权快速联合与路径压缩算法

Question

关于有关联合这个问题找到分离集，与路径压缩算法加权快速联合

Weighted Quick-Union with Path Compression algorithm

不路径压缩影响IZ []数组（包含以i为根的树的长度的数组）？

Answer 1

就我所了解的代码而言，数组iz []表示给定不相交集合中元素的数量。压缩路径时，不会为每组修改该数字。因此，路径压缩不会影响iz []数组。

Answer 2

我会开始引用一些基本观点。首先，这是用于实现不相交集合的最优算法，并且称为Union by Rank with path compression heuristic。该算法需要2个数组，第一个（id [] there）用作到父级的链接，第二个（iz []）给出该set中的节点数。

我们有2个操作 - 联盟和连接。

联盟是通过'等级'来完成的，通过使更小的树子成为更大的子树，从而导致更低分摊成本，因此长度趋于最小。

当连接方法被调用后，在我们了解了该树的根后，我们使用了一种路径压缩技术，该技术基本上将该特定节点指向该树的根，因此在将来我们不必遍历整个分支。由于iz []只包含该集合的节点数量，因此不会受到路径压缩的影响。