集合的表示：

• 集合运算：交、并、补、差，判定一个元素是否属于某集合

• 并查集：集合并、查某元素属于什么集合

• 数组中每个元素类型的描述为：

• 集合运算：

1. 查找某个元素所在的集合（用根节点表示）

2. 集合的并运算
• 分别找到X1和X2两个元素所在集合树的根节点
• 如果它们不同根，则将其中一个根节点的父节点指针设置成另一个根节点的数组下标

分析

• 在上面的算法中，Find 对于每个元素都需要遍历一遍集合，而且 Union 又需要调用 Find ，如果集合中所有元素都操作一遍，时间复杂度会来到，数据量较大的时候会非常慢；

按秩归并

1. 将矮树贴到高树上，以此来控制树的高度，降低时间复杂度；
❓
树的高度应该存到哪里？
S[Root] = -树高;

2. 将规模小的树贴到规模大的树上。 S[Root] = -元素个数;

• 优点：
1. 单次操作的时间复杂度会降低到级别
2. 不会破坏树的结构（与压缩路径比起来）

压缩路径

 

• 优点：时间复杂度可以降低到常数级别