并差集的本质是采用双亲表示法的树
| 数据元素 | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| S[] | -1 | 0 | -1 | -1 | 1 | 1 | 2 | 3 | 3 | 3 | 3 | 4 | 4 |
并差集是逻辑结构——集合的一种具体实现，只进行“并”和“查”两种基本操作 具体代码实现可以参考5.5查并集.h
O(n)(高度 h=结点数 n 时)O(1)实际是通过优化合并操作来优化查找的时间复杂度
树越高查找的时间越长，所以通过优化合并的操作来让树尽可能的矮
现在所有根结点的值都是 -1，可以利用根结点的值附带上集合结点数量信息，每次合并都让小树合并到大树上
下面表格是优化后的并差集，0 号位置的-6表示A为根结点的树的总结点数是 6 个。同理C为根结点的树的总结点数是 2 个。
| 数据元素 | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| S[] | -6 | 0 | -2 | -5 | 1 | 1 | 2 | 3 | 3 | 3 | 3 | 4 | 4 |
优化后的代码可以参考5.5查并集.h中的BetterUnion
优化后Find的时间复杂度为 O(log2n)
此时构造的树高度不超过 (log2n)+1