自学内容网 自学内容网

并查集 Rank 的优化

并查集 Rank 的优化

并查集是一种数据结构,用于处理一些不交集的合并及查询问题。它支持两种操作:查找(Find)和合并(Union)。查找操作用于确定某个元素属于哪个子集,而合并操作用于将两个子集合并成一个集合。在并查集中,每个子集用一棵树来表示,树根的元素作为该子集的代表。

并查集的基本操作

初始化

每个元素最初都是一个单独的集合,即自己是自己集合的代表。

查找(Find)

查找操作用于确定某个元素所在的集合。在树形结构中,这通常是通过沿着从元素到其根的路径向上移动来实现的。

合并(Union)

合并操作用于将两个元素所在的集合合并为一个集合。这通常是通过将一个集合的根连接到另一个集合的根来实现的。

Rank 优化

在标准的并查集实现中,合并操作可能不够高效。特别是在合并两个集合时,如果随意选择一个集合的根作为新根,可能会导致树的高度增加,从而降低查找操作的效率。为了优化这一点,可以使用 Rank 优化。

Rank 优化的基本思想是:在合并两个集合时,总是将较小树的根连接到较大树的根。这里的“大小”通常是通过树的高度来衡量的,这个高度被称为 Rank。

Rank 的定义

每个集合的 Rank 是其树的高度的一个上界。当两个集合合并时,将 Rank 较小的集合的根连接到 Rank 较大的集合的根。如果两个集合的 Rank 相同,则选择其中一个作为根,并将它的 Rank 增加 1。

优化后的合并操作

  1. 查找两个元素所在集合的根。
  2. 比较两个根的 Rank。
  3. 将 Rank 较小的根连接到 Rank

原文地址:https://blog.csdn.net/wjs2024/article/details/142710376

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!