并查集 rank 的优化

并查集 rank 的优化

并查集是一种数据结构，用于处理一些不交集的合并及查询问题。它支持两种操作：查找（Find）和合并（Union）。查找操作用于确定某个元素属于哪个集合，而合并操作用于将两个集合合并成一个。并查集在处理如连通性问题、图的动态连通性等场景时非常有用。

并查集的基本原理

并查集的基本思想是，初始时，每个元素构成一个单独的集合，每个集合用一棵树来表示。树中的每个节点都有一个指针指向其父节点，根节点的父节点指针指向自己。在合并操作中，将一棵树的根节点指向另一棵树的根节点，从而实现两个集合的合并。在查找操作中，通过遍历父节点指针，找到某个元素的根节点，从而确定该元素所在的集合。

rank 优化

在并查集的实现中，rank 优化是一种常见的优化策略，用于提高并查集的效率。rank 优化的基本思想是，在合并操作中，总是将较小的树合并到较大的树上。这样，可以避免树的高度过高，从而减少查找操作的时间复杂度。

具体来说，每个节点除了有一个指向父节点的指针外，还有一个 rank 值，表示该节点所在树的秩（高度）。在合并操作中，比较两个根节点的 rank 值，将 rank 值较小的根节点指向 rank 值较大的根节点。如果两个根节点的 rank 值相等，则选择其中一个作为新的根节点，并将其 rank 值加 1。

rank 优化的实现

以下是 rank 优化的并查集的 Python 实现：

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

在这个实现中，find 函数用于查找某个元素的根节点，union 函数用于合并两个集合。在 union 函数中，我们使用了 rank 优化，将 rank 值较小的根节点指向 rank 值较大的根节点，从而保持树的高度最小。

rank 优化的效果

通过 rank 优化，我们可以将并查集的查找操作的时间复杂度从 O(n) 降低到几乎 O(1)，从而大大提高并查集的效率。在实际应用中，rank 优化是一种非常有效的优化策略，被广泛应用于各种场景，如网络流量的连通性分析、图像处理中的连通区域标记等。