The DISJOINT SET ADT ｜ UNION-FIND
- 定义：
- A relation R is defined on a set S if for every pair of elements (a, b), a, b 属于S, a R b is either true or false. If a R b is true, then we say that a is related to b.
- UNION：需要合并
- 顺序相关，A合并到B，还是B合并到A是不相同的
- 两种实现的方式：链表和数组
- 查询和寻找一般是同对出现的，先执行find然后再执行union
- union的操作是常数关系
- Smart UNION 算法进行判断：
- union-by-size:
- find的操作变成的时间复杂度了
- 时间复杂度：
- union-by-height:理论上时间复杂度是最低的
- 矮的树并到高的树上面
- 路经压缩：
- union by rank:
- 最快的算法
- 算法的结论：
五种实现方式，union by rank一定是带有路径压缩的
分别涉及random，union_by_size 和 union_by_height 几种并查集的模式
路径压缩
现在我们所提到的union/find算法对大多数情况是完全适用的，如果运行find比union多很多，那么其运行时间就比快速查找算法的运行时间要糟。因此，我们可以是算法加速的唯一方法就是对find进行更加聪明的操作
路径压缩 路径压缩是在一次find操作中进行执行的，而与用来执行union的方法没有任何关系
路径压缩是让每一个节点在一条路径中的所有节点x，让他们的父节点都变成root根节点
return S[x] = Find_path_compression(S[x], S) 这一步是整个运算表达式的关键同时改变S[x]的值
union_by_rank和path_compression的最坏情况
总运行时间为
union/find 的算法分析
M次union和find的总运行时间变为O(M log* N)