数据结构-并查集

1.并查集原理在一些应用问题中需要将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-findset)。比如给学生进行编号{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 数组用来存储该小集体数组中的数字代表该小集体中具有成员的个数初始时每个元素对应数组中的值均为-1。假设s1{0,6,7,8}s2{1,4,9}s3{2,3,5}10个学生形成了3个小团体。0,1,2担任队长。每个团体都可以看成一棵树队长是根节点其他成员为叶子节点。在数组中将成员在数组中的初始值加到队长的初始值中即-1。仔细观察数组中内融化可以得出以下结论1.一个位置值是负数那他就是树的根这个负数的绝对值就是这棵树的数据个数。2.一个位置的值是正数这个正数就是双亲节点在数组中的下标。集合的合并若要s1{0,6,7,8}s2{1,4,9}这两个集合则让其中任意一个集合成为另一集合的子节点。假设将s2合并到s1成为它的子节点对应修改数组中对应元素的值。原来的根节点1在数组中存储值的绝对值为其成员个数值为-3。将其加到根节点0在数组中的值上其值变为-7。由于子节点应存储根节点的下标值1对应的数组值为0.