并查集
什么是并查集
并查集的核心是parent
指针,一个结点可以找到自己所属的结点。从而把结点归类。有两个核心操作:
- Union(用来合并两个并查集)
- Find(用于查找一个结点的
parent
)
所以并查集可以叫做:union-find data structure。
什么是路径压缩
我们看两个结点是否属于同一个并查集,实际上只看最顶层的那个parent
,如果这两个结点属于同一个最顶层parent
,那么它们就在同一个并查集中。
所以我们实际上只需要两层的树结构,让所有其他结点的parent
指针指向最顶层parent
,这样就能达到扁平化并查集的目的,从而使Find
操作从O(logN)
的时间复杂度变成O(1)
。这就叫:路径压缩
代码如下:
1 | public void findParent(UnionFindSetNode node){ |
这段代码很巧妙,可以在查找本结点父亲的时候,将路径上的所有祖先扁平化。
合并操作
核心目标是:尽可能减少深度。所以需要注意的点是:把深度小的并查集归并到深度大的并查集。我们给并查集多添加一个深度属性:rank,比如两层的并查集,parent 的 rank 就是 1,叶子节点们的 rank 就是 0。
代码如下:
1 | public void union(UnionFindSetNode node1, UnionFindSetNode node2){ |