另外一种特殊的树结构: 并查集 一种很不一样的树形结构
前面我们接触的树结构都是由父亲指向孩子，但是我们的并查集却是由孩子指向父亲。这种奇怪的树结构可以非常高效的回答一类问题: 连接问题 Connectivity Problem
如上图一张图中，有很多点，每两个点之间有没有连接的问题。给出任意两点是否有路径相连。
并查集可以非常快的查看到网络中节点间的连接状态。网络是个抽象的概念:用户之间形成的网络
每两个人通过各自的好友连接起来，设计网络。商品，图书，音乐专辑节点之间定义边。交通系统之间的网络，计算机网络路由器为节点。
并查集 还是数学中的集合类实现,主要操作在求集合的并集。
连接问题 和 路径问题
存在路径一定连接， 不存在路径一定不连接。
回答两个节点之间的连接问题是要比回答路径问题要回答的问题少。
只需要回复是或不是，问a与b的路径，返回一个具体的路径。 只想知道连接状态，求解路径会消耗性能。
完全可以使用复杂度更高的算法进行求解，但是之所以复杂度更高，其实是因为求解出了很多我们问的问题并不关心的内容。
和堆作比较，我们可以使用线性表，链表保持有序就可以了。顺序表不止可以取出最大的元素(最大堆)，也可以取出第二大，第三大，第k大。但是我们用堆时，只关心最高的那个，因此顺序表维护了很多我们并不需要的信息，性能消耗O(n); 堆只关注最大的，因此堆性能更高。
回答额外问题，性能变低。
并查集Union Find 对于一组数据，主要支持两个动作:
union(p, q)
isConnected( p, q)
逐步优化我们的并查集，首先设计一个并查集接口。
package cn.mtianyan;
public interface UF {
int getSize(); // 对当下这些元素
boolean isConnected(int p, int q); // id为p id为q是否相连
void unionElements(int p, int q);
}
union是将两个元素合并起来。
并查集的内部只存0-9这十个编号，不会关注它具体代表。每一个元素存储它所属的集合的id
如上图是分成了两个集合，数组称之为id。对应的集合id相同则相连。
isConnected( p, q) = find(p) == find(q) Quick Find时间复杂度O(1)，直接取出数组index对应的值。
经过union之后，数组变为如上图所示。遍历，将所有id为0的改为1。
package cn.mtianyan;
/**
* 我们的第一版Union-Find
*/
public class UnionFind1 implements UF {
private int[] id; // 我们的第一版Union-Find本质就是一个数组
public UnionFind1(int size) {
id = new int[size];
// 初始化, 每一个id[i]指向自己, 没有合并的元素
for (int i = 0; i < size; i++)
id[i] = i;
}
@Override
public int getSize() {
return id.length;
}
/**
* 查找元素p所对应的集合编号 O(1)复杂度
*
* @param p
* @return
*/
private int find(int p) {
if (p < 0 || p >= id.length)
throw new IllegalArgumentException("p is out of bound.");
return id[p];
}
/**
* 查看元素p和元素q是否所属一个集合 O(1)复杂度
*
* @param p
* @param q
* @return
*/
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
/**
* 合并元素p和元素q所属的集合 O(n) 复杂度
*
* @param p
* @param q
*/
@Override
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
for (int i = 0; i < id.length; i++)
if (id[i] == pID)
id[i] = qID;
}
}
某一个操作O(n)，性能比较差，需要进行改进。创建一棵树，从孩子指向父亲。
Quick Union
标准的并查集实现思路: 将每一个元素，看做是一个节点
如果是让7和2合并，不需要把每个节点都与之连接，而是将5和2连接起来就可以了。7和3连接，与上面得到的结果是一样的。
每一个节点本身只有一个指针,parent(i)表示第i个元素所在的节点指向了哪个元素。
森林中有十棵树，Union(4,3) 就是让4指针指向3。
数组中
查询4所在的链的根节点(8自己指自己)，然后让9指向4所在树根节点。
Union的复杂度是O(h)级别的，h是当前union的这两个元素所在树的深度。代价: 查询操作时得查询根节点。
package cn.mtianyan;
/**
* 我们的第二版Union-Find
*/
public class UnionFind2 implements UF {
/**
* 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
* parent[i]表示第一个元素所指向的父节点
*/
private int[] parent;
/**
* 构造函数
* @param size
*/
public UnionFind2(int size){
parent = new int[size];
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < size ; i ++ )
parent[i] = i;
}
@Override
public int getSize(){
return parent.length;
}
/**
* 查找过程, 查找元素p所对应的集合编号 O(h)复杂度, h为树的高度
* @param p
* @return
*/
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while(p != parent[p])
p = parent[p]; // 不断上移，直到指向自己
return p;
}
/**
* 查看元素p和元素q是否所属一个集合 O(h)复杂度, h为树的高度
* @param p
* @param q
* @return
*/
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
/**
* 合并元素p和元素q所属的集合 O(h)复杂度, h为树的高度
* @param p
* @param q
*/
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
parent[pRoot] = qRoot;
}
}
基于size的优化
第一版就是数组，第二版形成了树结构，孩子指向父亲。通过节点查到根节点。测试前面两个的性能
package cn.mtianyan;
import java.util.Random;
public class Main {
private static double testUF(UF uf, int m) {
int size = uf.getSize();
Random random = new Random();
long startTime = System.nanoTime();
for (int i = 0; i < m; i++) {
int a = random.nextInt(size);
int b = random.nextInt(size);
uf.unionElements(a, b);
}
for (int i = 0; i < m; i++) {
int a = random.nextInt(size);
int b = random.nextInt(size);
uf.isConnected(a, b);
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
// int size = 10000;
// int m = 10000;
// UnionFind1慢 : 0.03809207 s UnionFind2 : 0.026871858 s
// int size = 100000;
// int m = 10000;
// UnionFind1 慢于 UnionFind2 size就是O(n)的n;
// UnionFind1 : 0.206028658 s UnionFind2 : 0.001796639 s
int size = 100000;
int m = 100000;
// UnionFind2 慢于 UnionFind1
// UnionFind1 : 4.361822269 s UnionFind2 : 9.56344783 s 1 JVM 访问数组连续空间速度快，两个操作都是O(h)，树深度高。
UnionFind1 uf1 = new UnionFind1(size);
System.out.println("UnionFind1 : " + testUF(uf1, m) + " s");
UnionFind2 uf2 = new UnionFind2(size);
System.out.println("UnionFind2 : " + testUF(uf2, m) + " s");
}
}
充分考虑合并的两个树的特点: 9想加入原本的集合，可以是8直接连上9，但也可以是9指向根节点8。
package cn.mtianyan;
/**
* 我们的第三版Union-Find
*/
public class UnionFind3 implements UF {
/**
* 我们的第三版Union-Find, 使用一个数组构建一棵指向父节点的树
* parent[i]表示第一个元素所指向的父节点
*/
private int[] parent;
private int[] sz; // sz[i]表示以i为根的集合中元素个数
/**
* 构造函数
* @param size
*/
public UnionFind3(int size){
parent = new int[size];
sz = new int[size];
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < size ; i ++ ){
parent[i] = i;
sz[i] = 1;
}
}
@Override
public int getSize(){
return parent.length;
}
/**
* 查找过程, 查找元素p所对应的集合编号 O(h)复杂度, h为树的高度
* @param p
* @return
*/
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while(p != parent[p])
p = parent[p]; // 不断上移，直到指向自己
return p;
}
/**
* 查看元素p和元素q是否所属一个集合 O(h)复杂度, h为树的高度
* @param p
* @param q
* @return
*/
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
/**
* 合并元素p和元素q所属的集合 O(h)复杂度, h为树的高度
* @param p
* @param q
*/
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
// 根据两个元素所在树的元素个数不同判断合并方向
// 将元素个数少的集合合并到元素个数多的集合上
if(sz[pRoot] < sz[qRoot]){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{ // sz[qRoot] <= sz[pRoot]
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}
构造函数中sz进行初始化，UnionEelements中进行维护。
int size = 100000;
int m = 100000;
UnionFind3 uf3 = new UnionFind3(size);
System.out.println("UnionFind3 : " + testUF(uf3, m) + " s");
基于Rank的优化
上一节中的优化目的是为了不要合并时树的高度疯狂增加，尽量少的增加。
rank就是树的高度，深度。
节点多不一定深度大，8合并过来，深度从2,3变为了4。
因此更合理的是如上图，深度低的合并到深度高的。
基于raink的优化 rank[i]表示根节点为i的树的高度
package cn.mtianyan;
/**
* 我们的第四版Union-Find
*/
public class UnionFind4 implements UF {
private int[] parent;
private int[] rank; // rank[i]表示以i为根的集合所表示的树的层数
/**
* 构造函数
* @param size
*/
public UnionFind4(int size){
parent = new int[size];
rank = new int[size];
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
for( int i = 0 ; i < size ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
@Override
public int getSize(){
return parent.length;
}
/**
* 查找过程, 查找元素p所对应的集合编号 O(h)复杂度, h为树的高度
* @param p
* @return
*/
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while(p != parent[p])
p = parent[p]; // 不断上移，直到指向自己
return p;
}
/**
* 查看元素p和元素q是否所属一个集合 O(h)复杂度, h为树的高度
* @param p
* @param q
* @return
*/
@Override
public boolean isConnected( int p , int q ){
return find(p) == find(q);
}
/**
* 合并元素p和元素q所属的集 O(h)复杂度, h为树的高度
* @param p
* @param q
*/
@Override
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// 根据两个元素所在树的rank不同判断合并方向
// 将rank低的集合合并到rank高的集合上
if(rank[pRoot] < rank[qRoot])
parent[pRoot] = qRoot; // 合并以后，上限没变
else if(rank[qRoot] < rank[pRoot])
parent[qRoot] = pRoot;
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 此时 才需要维护rank的值
}
}
}
UnionFind4 uf4 = new UnionFind4(size);
System.out.println("UnionFind4 : " + testUF(uf4, m) + " s");
int size = 10000000;
int m = 10000000;
运行结果:
这里因为一些未知的不可控因素，find4反倒更慢了，不太清楚发生了什么。
老师的是这样的，一样的代码，我已经排除了JDK版本的问题，与老师代码不一致的问题，就不清楚其他还有啥问题了。
但是从逻辑上来看，rank的优化更合理。
路径压缩 Path Compression
上图中的三种方式实际是等价的,深度不同，效率不同。
路径压缩该在什么时候触发？find过程中，会从该节点一直向上到根节点。
让自己的爷爷来当自己的爸爸。
parent[p] = parent [parent[p]];
/**
* 查找过程, 查找元素p所对应的集合编号 O(h)复杂度, h为树的高度
* @param p
* @return
*/
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while(p != parent[p]){
parent[p] = parent[parent[p]];
p = parent[p]; // 不断上移，直到指向自己
}
return p;
}
其他代码与find4相比不变，只添加一行代码
UnionFind5 uf5 = new UnionFind5(size);
System.out.println("UnionFind5 : " + testUF(uf5, m) + " s");
可以看到是要优于UnionFInd 3 4 的。
Rank在添加上路径压缩之后已经不是节点所对应的深度值了，但是依然可以表现出深度大小前后的相对顺序。
更多和并查集相关的话题
上一节中我们路径压缩的效果如上图所示。最理想的情况是如下图所示
压缩后的parent数组如上图所示。
private int find(int p){
if(p < 0 || p >= parent.length)
throw new IllegalArgumentException("p is out of bound.");
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
// while(p != parent[p]){
// parent[p] = parent[parent[p]];
// p = parent[p]; // 不断上移，直到指向自己
// }
// return p;
// path compression 2, 递归算法
if(p != parent[p])
parent[p] = find(parent[p]); // 让根节点来做p节点的父亲
return parent[p]; // 返回整棵树的根节点
}
这是从宏观语义来写的find函数，不理解可以使用小数据量进行学习。
UnionFind6 uf6 = new UnionFind6(size);
System.out.println("UnionFind6 : " + testUF(uf6, m) + " s");
没有非递归的性能好，虽然压缩的树高度很低，但是压缩时的递归有性能消耗。
我们调用过find4的结果，再调用find4，会进行进一步的压缩。再调用find3，也会变扁平。
并查集的时间复杂度分析
查或者合并 O(h) h为树的高度。 严格意义上，加入了压缩路径的并查集 是O(log *n)
iterated logarithm
递归的定义，递归到底logn=0;近乎可以理解为O(1)级别的算法,比O(1)慢，比O(logn)快。
leetcode标签: 并查集; 图论中路径也是可以求解这个问题的。
我们介绍完了四种变种树: 堆，线段树，Trie，并查集。 下一章回归二分搜索树，深入解决不平衡问题(可能会退化成链表)，使得我们的二分搜索树自平衡，不会退化成链表。
下一章学习AVL树。
网友评论