1

有人可以解释什么是不相交集数据结构吗？或者将我链接到解释它的 YouTube 视频或文章。

几分钟前我搜索了它，我得到的只是一些数学课，其中涉及一个看起来像维恩图的图像。也许就是这样，但我不确定，所以任何帮助表示赞赏。

顺便说一句，当我被问到“如何使用二叉树来表示二叉树队列中的每个二叉树”时，这是指您必须相互堆叠的二叉树吗？就像 B1 与 B1 连接成为 B2，然后两个 B2 成为 B3，依此类推。

4

3 回答 3

6

不相交集数据结构是用于表示集合 S 的一个分区的数据结构。您从一组元素 S 开始，每个元素都属于它自己的组。例如：

{1} {2} {3} {4} {5} {6}

对不相交集数据结构的一种操作是联合操作，它将包含给定元素的两个集合组合在一起。例如，将 1 和 2 合并在一起会返回分区

{1, 2} {3} {4} {5} {6}

结合在一起 3 和 5 产生

{1, 2}, {3, 5}, {4}, {6}

现在，将 1 和 3 联合在一起会产生分区

{1, 2, 3, 5}, {4}, {6}

查找操作告诉您给定元素属于哪个集合。通常，这是通过 find 返回它所属元素的代表元素来完成的。通常这样做是为了

find(x) == find(y)  if and only if  x and y are in the same set.

例如，find(1) 可能返回 2，因此 find(2) = 2、find(3) = 2、find(5) = 2。

不相交集数据结构通常用作 Kruskal 最小生成树算法中的子程序，因为它们提供了一种非常快速的方法来检查图中的两个节点是否已连接，并且可以简单地标记两个连接组件中的所有节点都已连接到当添加一条边时。使用具有联合排序和路径压缩的不相交集森林实现，可以在 O(n α(n)) 时间内完成对不相交集森林的 n 次操作，其中 α(n) 是反阿克曼函数，一个增长如此缓慢的函数，它实际上是一个常数（对于任何小于宇宙大小的输入，它最多为四个。）

至于二叉树和二叉树：我认为您要问的是如何使用二叉树来表示二叉树，它们是多路树，最多有两个孩子。并非所有二叉树都是二叉树，因此必须使用合适的编码。

一种方法是使用称为左子右兄弟表示的东西。根据以下设置，这将多路树表示为二叉树：

  • 每个节点的左子节点指向该节点的第一个子节点。
  • 每个节点的右子节点指向它的下一个兄弟节点（同一层中具有相同父节点的节点）。

例如，给定这个二叉树：

     a
   / | \
  b  c  d
 /|  |
e f  g
  |
  h

左孩子右兄弟表示将是

                 a
                /
               b
            /    \
           e      c
            \    / \
             f  g   d
            /
           h

顺便说一句 - 如果你在二叉树上这样做，你最终会得到一个二叉树的表示形式，称为半序半树，它是具有以下属性的二叉树：

  • 树中的每个节点都大于或等于（或小于或等于，取决于这是最小堆还是最大堆）其左子树中的每个节点。
  • 根节点没有右孩子。

这些定义源于二叉树是堆排序的，然后转换为左子右兄弟表示。使用这种表示，链接到二叉树的速度非常快。我将把它作为练习留给读者。:-)

希望这可以帮助！

于 2012-12-12T22:09:37.010 回答
1

我在大学学到的不相交的集合围绕三个基本功能展开。

make_set(x) - makes a new disjoint contains only the element x
find_set(x) - gives you the set that contains element x
union(x,y) - unions the sets that contain x and y

他们提到的实现是使用链表。也就是说，每个集合都有一个代表创建该集合的元素。( make_set(x)) 然后用unions(x,y)， 的结束指针x移动到指向y。Union并且make_set很快，但这对于find_set（实际上是O（最大集））来说非常慢

更好的实现使用了两种称为路径压缩的方法，它作为一个元素通过union和/或传递find_set，它使它指向集合的代表

另一个是union-by-rank，它为每个集合保持一个排名，给出集合的最大“深度”。联合时，如果每组的等级相同，则将等级增加一位，并更改一位代表指向另一位。如果它们不同，则将较小的集合更改为指向较大的代表，并且等级保持不变。this 的这个渐近上界非常接近函数的使用次数。

希望有帮助。

于 2012-12-12T22:18:27.913 回答
1

不相交集基本上是一个联合查找数据结构。

您最初有一组n节点，并且您对它find(node)进行union(node1,node2)了操作。

  • union(node1,node2)正在将节点“组合”在一组中
  • find(node)正在寻找node（例如，通过给出根，如稍后解释）的规范表示

例如，您最初拥有{1},{2},{3},{4},{5}，并且您这样做：

union(1,2)
union(3,4)

然后你最终拥有{1,2},{3,4},{5}.
这也意味着在这一点上find(1) == find(2)（它是同一套！）

如果你稍后union(2,3)- 它将导致包含 2 的集合与包含 3 的集合合并，你最终会得到{1,2,3,4},{5}

关于视频请求：伯克利的这次讲座似乎很好地涵盖了这些材料。

关于二叉树 - 这是一种实现方式，每个“根”都有其儿子，但树实际上是“颠倒的”，而不是从父亲到儿子的指针，而是从儿子到父亲的指针。
这样，每个节点的规范表示是该节点通向的根，这确保了如果我们在aand b- then上进行联合find(a) = find(b)，因为它们具有相同的根。

我希望它能给你一些关于这个 DS 是什么的线索。
祝你好运！

于 2012-12-12T22:01:55.640 回答