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

Question

有人可以解释什么是Disjoint Sets Data Structure是什么？或者将我链接到YouTube视频或解释它的文章.

几分钟前我搜索过它,我得到的只是一些数学课程,其中包含一个看起来像维恩图的图像.也许就是这样,但我不确定,所以任何帮助都会受到赞赏.

简而言之,当我被问到"如何使用二叉树来表示二项式队列中的每个二叉树时"这是指你必须相互堆叠的二叉树.就像B1连接B1一样成为B2,那么两个B2成为B3,依此类推.

Answer 1

不相交的集合数据结构是用于表示集合 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)是逆Ackermann函数,一个生长得如此缓慢的函数它实际上是一个常数(对于任何小于宇宙大小的输入,它最多为四个.)

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

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

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

例如,给定这个二叉树:

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

左子右兄弟代表将是

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

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

• 树中的每个节点都大于或等于(或小于或等于,取决于这是最小堆还是最大堆)其左子树中的每个节点.
• 根节点没有正确的子节点.

这些定义遵循以下事实:二叉树是堆排序的,然后转换为左子右兄弟表示.使用此表示法,将二叉树连接到二叉树是非常快的.我将把它作为练习留给读者.:-)

希望这可以帮助!