不相交设置数据结构和二叉树？

Question

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

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

快速注意，当我被问及“如何使用二叉树来表示二叉树队列中的每个二叉树”时，这是指您必须彼此堆叠的二叉树。就像B1附加一个B1成为一个B2，然后两个B2成为一个B3，依此类推。

Answer 1

不相交集数据结构是用于表示partition of a set S的数据结构。您从一组元素S开始，每个元素都属于它自己的组。例如：在并查集

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

一个操作是在工会操作，其包含给定的元素的两个集合结合在一起。例如，unioning一起1和2给出了回分区

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

Unioning一起3和5产生

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

现在，unioning一起1和3产生的分区

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

的找到操作告诉你给定元素属于哪个集合。通常，这是通过查找返回其所属元素的代表性元素来完成的。这通常使得

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

例如，发现（1）可能返回2等发现（2）= 2，找到（3）= 2，求（5）= 2

不连续集数据结构通常用作Kruskal最小生成树算法中的子例程，因为它们提供了一种非常快速的方法来检查图中的两个节点是否已连接，并且标记两个连接组件中的所有节点都已连接的简单方法在添加边时添加到另一个。使用按级联和按路径压缩的实现，可以在O（n α（n））时间内完成在不相交集林中的n个操作，其中α（n）是inverse Ackermann function，成长缓慢但有效的是一个常量（它在任何输入最多四个小于宇宙的大小。）

---

至于二叉树和二进制树：我觉得你问的是如何代表二叉树，它是多路树，使用二叉树，最多有两个孩子。并非所有的二叉树都是二叉树，所以必须使用合适的编码。

这样做的一种方法是使用称为left-child right-sibling表示的东西。这代表了许多路树作为一个二叉树根据以下设置：

• 的左孩子每个节点的点到节点的第一个孩子。
• right每个节点的子节点指向其下一个兄弟节点（与同一父节点在同一图层中的节点）。

例如，假设该二叉树：

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

的左子右兄弟表示将

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

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

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

这些定义遵循一个事实，即二叉树是堆排序的，然后转换为左孩子右兄弟表示。使用这种表示法，将二者连接在一起的速度非常快。我会把这个作为练习留给读者。 :-)

希望这有助于！

Answer 2

Disjoint set基本上是联合查找数据结构。

你本来有一组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) - 这将导致unioning含2与的设置设置含3，你将结束与{1,2,3,4},{5}

关于视频请求：This lecture from Berkley似乎覆盖材料相当不错。

---

关于二叉树 - 这是实现的一种方式，每个“根”有其儿子，但树实际上是“倒挂”，而不必从父亲指针儿子，你必须从儿子的指针对父亲。
这样，每个节点的canon表示就是节点所通向的根节点，这就保证了我们在a和b-然后是find(a) = find(b)上做了联合，因为它们具有相同的根。

我希望它能为您提供一些有关此DS的信息。
祝你好运！

Answer 3

我在uni学到的不相交集合围绕着三个基本功能。

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传递，它使它指向该集合的代表

另一个，联合按排名，其中维持排名每个集给予最大的“深度”集。工会时，如果每组的排名相同，则将其添加到排名中，并将一位代表改为指向另一位。如果它们不同，那么较小的一组更改为指向较大的代表，并且等级保持不变。这个渐近上限与这些函数的使用次数非常接近。

希望有所帮助。