联合查找数据结构 [英] Union-find data structure

问题描述

对于许多问题，我看到建议的解决方案是使用union-find数据结构。我试图读一下它，并想想如何实现（使用C ++）。我目前的理解是，它只是一组列表。因此，要找到一个元素属于哪个集合，我们需要 n * log n 操作。当我们必须执行联合时，我们必须找到需要合并的两个集合，并对它们执行 set_union 。这看起来对我来说效率不高。是我对这个数据结构的理解正确还是我缺少了一些东西？

For many problems I see the solution recommended is to use a union-find data structure. I tried to read about it and think about how it is implemented (using C++). My current understanding is that it is nothing but a list of sets. So to find which set an element belongs we require n*log n operations. And when we have to perform union, then we have to find the two sets which needs to be merged and do a set_union on them. This doesn't look terribly efficient to me. Is my understanding of this data structure correct or am I missing something?

推荐答案

数据结构可以表示为树，分支转向（而不是向下指向，分支向上指向父级，并将子级与其父级链接）。

The data structure can be represented as a tree, with branches reversed (instead of pointing down, the branches point upwards to the parent---and link a child with its parent).

如果我记得正确，显示（容易）：

If I remember correctly, it can be shown (easily):

• 路径压缩（无论何时查找集合A的父 压缩路径，使得每次未来调用这些将在时间O（1）中提供父节点）将导致每次调用的O（log n）复杂度;

• that path compression (whenever you do a lookup for the "parent" of a set A, you "compress" the path so that each future call to these will provide the parent in time O(1)) will lead to O(log n) complexity per call;

平衡（你保持大约跟踪每个集合的孩子的数量，当你必须联合两组，你使一个与最少的孩子孩子的最多）也导致一个每次调用的O（log n）复杂度。

that balancing (you keep approximately track of the number of children each set has, and when you have to "unite" two sets, you make the one with the fewer children child of the one with the most) also leads to a O(log n) complexity per call.

获得一个平均复杂度，这是阿克曼的逆，这是塔里木的这个结构的主要发明。

A more involved proof can show that when you combine both optimizations, you obtain an average complexity that is the inverse of ackermann, and this was Tarjan's main invention for this structure.

后来显示，对于一些特定的使用模式，这种复杂性实际上是不变的。但我不认为它已被证明是全球不变的（虽然对于所有实际目的，ackermann的倒数约为4）。

It was later shown, I believe, that for some specific usage patterns, this complexity is actually constant. But I don't think it was ever proven that it is globally constant (though for all practical purpose inverse of ackermann is about 4).

这篇关于联合查找数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！