一天 一个数据结构知识——并查集

        众所周知，学习一个数据结构就要了解它的三要素：逻辑结构，存储结构，数据的运算。那么首先我们要知道并查集的逻辑结构是什么？（逻辑结构就是元素间的逻辑关系，包括线性结构，非线性结构（集合、树形结构、网状结构））。

        并查集是一种集合，但是它是把属于同一个集合的元素放到同一棵树上，这样多个集合就是多个互不相交的树。并和查就是其两个基本操作，查就是从这个元素找到其根节点从而确定其属于哪个集合，并就是让一棵树成为另一棵树的子树，把两个集合并起来。

        而树的表示主要有三种：双亲表示法，孩子表示法，孩子兄弟表示法。

        显然，双亲表示法来表示树，更容易实现并查集。因为双亲表示法是在每个节点中保存一个指向父节点的指针，因为指针都是指向父节点的，因此找到根节点实现查操作就更容易，如果想要进行并操作，则只需让其中一棵树的根节点指向另一棵树的根节点。

        用这种方式，并查集,并的时间复杂度为O(1)，find查的最坏时间复杂度为O(n)，树的高度越高最坏时间复杂度越大，因此我们要尽可能让树变矮。最直接的办法，就是在并的时候让小树并到大树上，如何判断树大树小呢，我们可以用根节点的绝对值表示树的节点总数。同时在union时记得累加节点总数。优化后树的高度会不超过[log2n]+1。