Tree and Equivalence Problem

Published: August 03, 2020 by Authur Lee

• Categories:
• Data_Structure 44

• Tags:
• Equivalence 1
• Tree 7

等价关系和等价类

【等价关系】如果集合S中的关系R是自反的、对称的和传递的，则称它为一个等价关系。

【等价类】设R是集合S的等价关系。对任何，由给出的集合称为 生成的一个等价类。

【R等价类】若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分(即：可以按R将S划分为若干不相交的子集S1,S2…，它们的并为S，则这些子集Si便称为S的R等价类)。

【等价问题】许多应用问题可以归结为按给定的等价关系划分某集合为等价类，通常称这类问题为等价问题。

如何划分等价类

假设集合S有n个元素，m个形如(x,y)(x,y属于S)的等价偶对确定了等价关系R，需求S的划分。

确定等价类的算法：

1. 令S中的每个元素各自形成一个只含单个成员的子集，记为S1,S2,…,Sn。
2. 重复读入m个偶对，对每个读入的偶对(x,y)，判定x和y所属子集。不失一般性，假设，，若Si与Sj不等，则将Si并入Sj并置Si为空(或将Sj并入Si并置Sj为空)。则当m个偶对都被处理过后，S1,S2,…,Sn中所有非空子集即为S的R等价类。

划分等价类需对集合的操作有三：

1. 构造只含单个成员的集合
2. 判定某个单元素所在的子集
3. 归并两个户不相交的集合为一个集合。

用树型结构表示等价类

以集合为基础的抽象数据类型可有多种实现方法，如用位向量表示集合或用有序表表示集合等。而在这里，我们要用树型结构来表示集合。

【实现集合的并】由于各子集中的成员均不相等，则实现集合的“并”操作，只要将一棵子集树的根指向令一棵子树的根即可。如下图。

【确定某个成员所在的集合】从该成员结点出发，顺链而进，直至找到树的根结点为止。看上图理解。

为了实现上述的两种操作，我们应该采用双亲表示法作为存储结构。

【算法：查找函数】

int find_mfset(MFSet S, int i) {
	// 找集合S中i所在子集的根
	if(i < 1 || i > S.n) return -1;	// i不属于任何一个子集
	for(j = i; S.nodes[j].parent > 0; j = S.nodes[j].parent);
	return j;
}

【算法：归并操作】

Status merge_mfset(MFSet &S, int i, int j) {
	// S.nodes[i]和S.nodes[j]分别为S的两个互不相交的子集Si和Sj的根结点
	// 求Si和Sj的并集
	if(i < 1 || i > S.n || j < 1 || j > S.n) return ERROR;
	S.nodes[i].parent = j;
	return OK;
}

两个算法的时间复杂度：

• 查找：O(d)，d为树的深度
• 归并：O(1)

对上述操作的改进

在极端的情况下(每次都是含成员多的根结点指向含成员少的结点)，会导致全部操作的时间复杂度为O(n^2)。

于是，我们要加对之进行改进。

【改进方法】在作“并”操作之前，先判断子集中所含成员的数目，然后令含成员少的子集树根结点指向含成员多的子集的根(为此，需要改变存储结构：令根结点的parent域存储子集中所含成员数目的负值)。

为什么是“负值”呢？ 因为双亲表示法是一个静态链表。关于树各种表示法 另外，初始时parent = -1.

【算法：改进之后的归并操作】

void mix_mfset(MFSet &S, int i, int j) {
	// S.nodes[i]和S.nodes[j]分别为S的互不相交的两个子集Si和Sj的根结点。
	// 求并集
	if(i < 1 || i > S.n || j < 1 || j > S.n) return ERROR;
	if(S.nodes[i].parent > S.nodes[j].parent) {
		// 如果Si所含成员数比Sj少
		// 注意哦，根结点的parent < 0
		S.nodes[j].parent += S.nodes[i].parent;
		S.nodes[i].parent = j;
	}
	else {
		S.nodes[i].parent += S.nodes[j].parent;
		S.nodes[j].parent = i;
	}
	return OK;
}

此算法得到的集合树，其深度不超过 ，其中n为S所有子集所含成员数的总和。

此时，归并操作的时间复杂度为，而利用查找和归并操作解等价问题的时间复杂度为O(nlogn)。

压缩路径

从上文中我们可以知道，树的深度约大，确定元素所在集合所花的时间也就越多，于是我们采取压缩路径的方法，进一步减少树的高度(最后让树的高度为2)。

【压缩路径】当所查元素i不在树的第二层时，将所有从根到元素i路径上的元素都变成树根的孩子。

下面是一个图，演示了在查找8时的前后对比图。

【算法：查找加上“压缩路径”的功能】

int fix_mfset(MFSet &S, int i) {
	// 确定i所在子集，并将从i至根路径上所有结点都变成根的孩子结点
	if(i < 1 || i > S.n) return -1;	// i不是S中任一子集的成员
	for(j = i; S.nodes[j].parent > 0; j = S.nodes[j].parent); // 找到树根结点j
	/*下面为压缩步骤*/
	for(k = i; k != j; k = t) {
		t = S.nodes[k].parent;	// 存储下一个要操作的点
		S.nodes[k].parent = j;	// 将当前结点变为根的孩子结点
	}
	return j;
}

利用fix_mfset函数和mix_mfset函数，划分大小为n的集合为等价类的时间复杂度为 。对于通常所见到的正整数n而言，