接触并查集结构

概述

并查集（Disjoint set或者Union-find set）是一种树型的数据结构（一定要一次性给定数据源，不支持流的处理），常用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

基本操作

1. 可查询两条数据是否存在于同一个集合。
2. 可合并两条数据（任意节点，而不是标准节点）所在集合。

（1）合并集合

合并过程.png
首先，每个节点由一个size和一对键值对组成（key是我们的data，value是对应的父级，开始父级都是自己）有犹豫key和value是不是非要使用包装对象呢？还是基本类型也可以？ 根据内部实现的结构
合并的过程，举了一个实际的例子。2和1合并，先各自向上找各自树的标志节点即根节点，接着根据标志节点的size将小的树连在大的树的标志节点上，最后更改合并后标志节点的size为合并后的值。为什么标志节点的size可以代表这棵树？ 因为这棵树也是合并来的，刚开始大家都是孑然一身。

（2）判断是否在同一集合

这个过程相对比较清晰。查2和1是否同源，两个节点分别向上查找自己的标志节点，相同即同源。

优化

按照上面的操作有时就会出现一些‘比较深的’树，查找这些枝干上的节点比其他的要费力许多。自己有点怀疑就举例一次合并的过程。

麻烦的例子.png
优化的方案：在查找某条数据的标志节点时，查找完将路径上经过的所有节点改为标志节点的直接子节点。
由于查找标志节点在合并和查同源的操作中都有用到，可以有效的避免上面的结构出现。即使不巧就是出现了，不巧还需要走最深的枝干，那么走一次，或者查过路径上的其他节点就可以使下一次变的省力。

这样的结构有什么作用呢？在查找和合并的次数逼近或超过数据量O(n)时，单次操作的时间复杂度约为O(1)常数级。

上code

实现上可以按构造树（用指针关联）的思路，操作上较为繁琐，而且对于JavaScript不查引用的基本类型数据需要使用包装对象。
我采用Map结构（实现Map可以数组、对象模拟，直接用ES6偷个懒），操作便捷，查表的过程有效避免引用类型的问题。

class Node{
    constructor(str){
        
    }
}
class UnionFindSet{
    constructor(NodeList){
        this.fatherMap = new Map();
        this.sizeMap = new Map();
        for( Node in NodeList){
            this.fatherMap.set(Node, Node);
            this.sizeMap.set(Node, 1);
        }
    }
    findHead(node){
        let father = this.fatherMap.get(node);
        if(father && father !== node){
            father = this.findHead(father);
        }
        this.fatherMap.set(node, father);
        return father;
    }
    isSameSet(a, b){
        return this.findHead(a) === this.findHead(b);
    }
    union(a, b){
        if(!a || !b){
            return;
        }
        let aHead = this.findHead(a),
         bHead = this.findHead(b);
        if(aHead !== bHead){
            let aSize = this.sizeMap.get(aHead),
             bSize = this.sizeMap.get(bHead);
            if(aSize > bSize){
                this.fatherMap.set(bHead, aHead);
                this.sizeMap.set(aHead, aSize + bSize);
            } else {
                this.fatherMap.set(aHead, bHead);
                this.sizeMap.set(bHead, aSize + bSize);
            }
        }
    }
}

Node是给出的包装对象，内部可以自己设计，装什么类型的数据，不用Node直接传入基本类型的数组也可以。