并查集 disjoint-set union

集合的表示

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

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

并查集如何存储

可以用树结构表示结合，树的每个节点代表一个集合元素

双亲表示法：孩子指向双亲。

应用

tssn

按秩归并对union函数改进

按树高
比规模

路径压缩对find函数改进

资料

https://blog.csdn.net/hongxue8888/article/details/103116667

黄浩杰 https://www.youtube.com/watch?v=YKE4Vd1ysPI

findRoot(x)
union(x,y)

如果1，2 2，3 3，4这种数据会形成一个链，那么可以使用压缩路径解决这个问题

并查集（Union-Find）不属于二叉树、平衡树或多叉树中的任何一种，而是一种专门用于处理不相交集合的合并与查询问题的抽象数据结构。以下是详细分析：

一、并查集的本质与特性

1. 非树形结构

并查集逻辑上可视为森林（多棵树的集合），但物理实现通常是数组。每个元素通过数组下标关联其父节点，最终指向根节点（代表整个集合）。

核心操作
：
- Find(x)：查找元素 x 所属集合的根节点（路径压缩优化后，可直接跳到根节点）。
- Union(x, y)：合并 x 和 y 所在的集合（通常通过将一个根节点指向另一个根节点实现）。

2. 与传统树的区别

无固定度数限制：节点的子节点数不确定，取决于合并顺序。
无平衡要求：树的高度可能很高，但通过路径压缩和按秩合并等优化，操作的均摊时间复杂度接近 (O(1))。
单向父子关系：仅需维护 “子节点→父节点” 的指针，无需双向连接。

二、并查集 vs. 二叉树 / 平衡树 / 多叉树

维度	并查集	二叉树 / 平衡树 / 多叉树
物理结构	数组（存储父节点索引）	节点 + 指针的树形结构
节点度数	无固定度数（动态变化）	固定度数（二叉树≤2，多叉树≥2）
平衡性	无需平衡（依赖路径压缩）	平衡树需维护子树高度差（如 AVL、红黑树）
核心操作	合并集合、查询连通性	搜索、插入、删除（如 BST、B 树）
应用场景	连通性问题、图论（如最小生成树）	排序、区间操作、字符串匹配

三、常见误区澄清

并查集是二叉树？
- 错误。二叉树每个节点最多 2 个子节点，而并查集中节点的子节点数无限制（可能有多个）。
并查集是平衡树？
- 错误。平衡树通过旋转等操作保持子树高度平衡，而并查集的树结构可能极不平衡（如链状），但通过路径压缩优化操作效率。
并查集是多叉树？
- 错误。多叉树有明确的树形结构和节点连接，而并查集仅关注 “节点→根节点” 的关系，树的具体形态不重要。

四、并查集的正确分类

并查集属于专用数据结构，设计目标是高效处理集合的合并与查询。其核心优化技术包括：

路径压缩：在 Find 操作时，将节点直接连接到根节点，减少后续查询的时间。
按秩合并：优先将小树合并到大树，避免树高度过快增长。

五、典型应用场景

连通性判断：判断图中两点是否连通（如社交网络中的好友关系）。
最小生成树（Kruskal 算法）：通过并查集快速判断边是否会形成环。
网格问题：如岛屿数量统计、迷宫连通性分析。
食物链问题：维护元素间的层次关系（如带权并查集）。

总结

并查集是一种基于数组和路径压缩的抽象数据结构，不属于二叉树、平衡树或多叉树。其独特的设计使其在处理集合合并与查询问题时比传统树形结构更高效。理解其 “动态森林” 本质，能避免与其他树结构混淆。