另外一种特殊的树结构: 并查集 一种很不一样的树形结构

前面我们接触的树结构都是由父亲指向孩子，但是我们的并查集却是由孩子指向父亲。这种奇怪的树结构可以非常高效的回答一类问题: 连接问题 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树。