0

网上有很多关于不相交集结构的描述和例子。

在某些情况下，对于每个集合，它都存储“排名”。当一个集合合并到另一个集合中时，如果它们的等级相同，则前者的等级增加 1。

在其他情况下，对于每个集合，它都会存储其大小。当一个集合合并到另一个集合中时，它们的大小会被添加。

在这里它存储排名。

在维基百科文章中，它存储排名。

在康奈尔大学的讲义中，它存储了排名。

在Sedgewick 和 Wayne的“算法”示例中，它存储大小。

在这里，它还存储尺寸（主站点）。

科门等人。写：

显而易见的方法是使具有较少节点的树的根指向具有更多节点的树的根。我们将使用一种简化分析的方法，而不是显式地跟踪以每个节点为根的子树的大小。对于每个节点，我们维护一个等级，它是节点高度的上限。在按秩联合中，我们在 UNION 操作期间使秩较小的根指向秩较大的根。

哪个更好/更合适？

4

1 回答 1

0

所有分析（是？）表明，当与树折叠技术结合使用时，这两种方法都提供了最佳的 O(alpha) 复杂度。

那么唯一的实现特定差异来自大小或排名变量所采用的大小。大小可以最大，size_t但等级可以始终以三位编码。

有时，这三位可以编码在要处理的数据/节点中未使用的位中，从而获得更好的性能（速度和大小）。

于 2017-07-30T05:55:46.003 回答