c - union find 不同情况下的操作

Question

这是Narasimha Karumanchi 的数据结构书的一段（不相交集ADT ）

快速查找实现（快速查找）

此方法使用一个数组，其中数组包含每个元素的集合名称。

在这个表示中执行 union(a,b)[假设 a, 在集合 i 中，b 在集合 j 中] 我们需要扫描整个数组并将所有 i 更改为 j。这需要 O(n)。

如果查找操作需要 O(1) 那么为什么要扫描完整的数组并将所有 i 更改为 j ，其中只有两个需要更改，所以它是 O(n)

=============

使用存储每个元素的父元素的数组而不是使用 root 作为其集合名称，解决联合 O(n)

它如何使用父母解决问题？以及根方法和父方法如何为我们提供倾斜树？

score 1 · Accepted Answer

假设您在 2 个集合中有 8 个元素，其中集合标识符为 1 和 2（因此在您的描述中 i = 1 和 j = 2）。假设集合 1 中有 4 个元素（元素 0、1、3、7），集合 2 中有 4 个元素（元素 2、4、5、6）。

快速查找实现将此数组表示为：

[ 1, 1, 2, 1, 2, 2, 2, 1 ]

并如下表示（元素 1 和 2 都有自循环）：

     1           2
   / | \       / | \
  0  3  7     4  5  6

如果您执行 union(1, 2) 并且只更新集合标识符（假设我们正在更新集合 2 中的元素以指向集合 1），那么您将拥有一个数组，例如：

[ 1, 1, 1, 1, 2, 2, 2, 1 ]

如果您执行 find(2)，您会得到标识符 1，这是正确的。但是如果你执行 find(4)，你会得到标识符 2，这是不正确的，因为元素 4 现在属于集合 1。

因此，您必须扫描完整的数组（因此该操作的时间复杂度为 O(n)）以更新标识符，以得到以下数组作为联合操作的结果：

[ 1, 1, 1, 1, 1, 1, 1, 1 ]

以及以下表示（其中 1 具有自循环）

         1
   / / | | \ \ \
  0 2  3 4  5 6  7

我相信你会在本书后面看到，union-find 数据结构有更有效的实现，它们基于按秩和路径压缩的联合。