algorithm - 不相交集数据结构和二叉树？

Question

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

几分钟前我搜索了它，我得到的只是一些数学课，其中涉及一张看起来像维恩图的图像。也许就是这样，但我不确定，因此感谢您的帮助。

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

Answer 1

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

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

union 操作是对不相交集数据结构的一种操作，它将包含给定元素的两个集合组合在一起。例如，将 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 最小生成树算法中的子例程，因为它们提供了一种非常快速的方法来检查图中的两个节点是否连接，并提供了一种标记两个连接组件中的所有节点的简单方法添加边时相互连接。使用 disjoint-set forest 通过按秩并集和路径压缩实现，可以在 O(n α(n)) 时间内完成对不相交集森林的 n 次操作，其中 α(n) 是 inverse Ackermann function ，一个增长如此缓慢的函数，它实际上是一个常数(对于小于宇宙大小的任何输入，它最多为 4。)

---

至于二叉树和二叉树:我想你问的是如何使用二叉树来表示二叉树，二叉树是多路树，最多有两个子树。并非所有的二叉树都是二叉树，因此必须使用合适的编码。

一种方法是使用一种叫做 left-child right-sibling 的东西表示。根据以下设置，这将多路树表示为二叉树:

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

例如，给定这个二叉树:

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

左子右兄弟表示将是

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

顺便说一下 - 如果您在二叉树上执行此操作，您最终会得到一个二叉树的表示形式，称为 half-ordered half-tree，它是一个二叉树以下属性:

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

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

希望这对您有所帮助!