不相交集结构

描述

顾名思义，不相交集数据结构的集合之间是没有交集的，这种结构常常需要实现两种运算：

• Find(x): 查找元素x所在的集合的名字
• Union(x, y): 包含元素x和y的两个集合用他们的并集替换

实现数据结构

以上两种算法都要求能够找到元素所在的集合的名字，因此可以构造树结构，将该树的根作为集合的名字，树上的结点都有一个指向父节点的指针，这样每个结点都能够找到该集合的名字。

//class TreeNode 的成员和函数
TreeNode nextTreeNode;  //指向父节点, 为空则是根节点
int val;                //存放值
int height;             //树的高度（这里只有该结点为根节点时才有效）

get,set方法;

TreeNode find(TreeNode x);       //找到x的根节点
TreeNode union(TreeNode x);      //合并两颗树（必须保证参数是根节点，即find(this).union(Find(x))

按秩合并措施

很明显，如果随意地合并两个集合，那么树的高度最坏会达到$O(n)$级别，所以采取以下措施：

高树和矮树合并时，把高树的根节点作为新的根节点，并成为矮树的根节点的父节点。

如果两棵树高度相同，任意哪个作为根节点都行，但是树的高度也要增加。

实现代码：

public TreeNode union(TreeNode x) {
    // TODO Auto-generated method stub
    if(height <= x.height){
        setNextTreeNode(x);
        if(height == x.height){
            x.height++;
        }
        return x;
    } else {
        x.setNextTreeNode(this);
        return this;
    }
}

查找集合&路径压缩

要寻找到一个集合的名字很容易，采取的数据结构就是围绕这一需求而设计的，但是为了避免树的高度过大，在查找到一条路径后可以采取路径压缩的策略来降低树的高度。

基本思路：在找到树的根节点后，重新遍历这条路径上的所有结点，让他们都指向树的根节点，最终完成路径压缩。

public TreeNode find() {
       // TODO Auto-generated method stub
       TreeNode p = this;
       while(!p.isRoot()){
           p = p.getNextTreeNode();
       }
       TreeNode root = p;
       p = this;
       while(!p.isRoot()){
           TreeNode nextNode = p.getNextTreeNode();
           p.setNextTreeNode(root);
           p = nextNode;
       }
       return root;
   }