如何通过Linked list实现Disjoint-set数据结构？

Question

我不知道如何通过Linked list实现Disjoint-set数据结构？谁能告诉我？我特别感到困惑的是find-set()如何在这样的实现中工作O(1)时间.thx~

Answer 1

虽然不相交集数据结构通常被解释为树林,但它通常用数组实现:一个数组用于将索引映射到其父类的索引,另一个数组用于将索引映射到其等级.这消除了许多毫无意义的开销(在空间和时间上),这在理论上是不相关的,但它在实践中.您可能需要一种方法来在索引和某种对象的实例之间进行映射.

find顺便说一句,在O(1)中不起作用.排名的诀窍阻止find了线性时间,但在最坏的情况下它仍然可以采用对数步数.O(α(n))时间是一个摊销时间,解释它的来源是很棘手的 - 你可以在一个良好但非线性集合联合算法的效率[Tarjan]中找到分析.

这是它可以工作的一种方式:

disjoint_set {
    int[] parent, rank;
    makeset(int n)
    {
        rank = new int[n];
        parent = new int[n];
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int i)
    {
        if (parent[i] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }

    void union(int x, int y)
    {
        x_root = find(x);
        y_root = find(y);
        if (x_root != y_root) {
            if (rank[x_root] < rank[y_root])
                parent[x_root] = y_root;
            else if (rank[x_root] > rank[y_root])
                parent[y_root] = x_root;
            else {
                parent[y_root] = x_root;
                rank[x_root]++;
            }
        }
    }
}