由一些不相交子集构成,合并查集的基本操作是 I)Find:判断两个结点是否在同一个集合中; 2) Union:归并两个集合 像栈、队列一样,并査集也是一种重要的抽象数据类型,可以用于求解等价类问题, 划分等价类需要对集合进行三种操作: I)构造只含有一个元素的集合; 2)判定某个元素所在的子集,目的是为了确定两个元素是否在同一个集合之中。即搜 索包含该元素的等价类,对于同一个集合中的元素返回相同的结果,否则返回不同的结果; 3)归并两个不相交的集合为一个集合 由于用根结点表示子集的类别,那么“查找”某一个元素所属的集合,只要从该结点出 发,沿父链域找到树的根结点即可。实现集合的“并”操作只要将一棵子树的根指向另一棵 子树的根即可。 每次合并前都需要进行两次查找,查找所需要的时间由树的高度决定,合并所需的时间 为0(1)。容易看出,在最坏情况下,合并可能使n个结点的树退化成一条链。 为了防止树退化为单链,应该让每个结点到其相应根结点的距离尽可能小,可以做如下 两种改进。 第一种改进的方法是在做“合并”操作之前先判别子集中所含成员的数目,然后令含成 员少的子集的树根指向含成员多的子集的根,称作“重量权衡合并规则”( weighted union rue)。把小树合并到大树中去,可以把树的整体深度限制在O(ogn,每次Find操作只需要 O(ogn)时间。 另一个办法是采用路径压缩( path compression)技术。在执行Find操作时,把结点到 树根的路径上所有结点的父指针都指向根结点。路径压缩可以缩短结点与根之间的路径 (4)带双标记的层次次序表示 由层次次序的性质可知,任何结点的子结点都排在该结点的所有兄弟结点后面。并且 任何结点的最后一个兄弟结点不会再有下一个兄弟,即最后一个兄弟的rtag为1。由结点的 层次次序以及ltag、rtag两个标志位,就可以确定树的左孩子/右兄弟链表中结点的link和 rik值。rik的值很容易确定:结点的rag为1,则rik为空;结点的rtag为0,则rink 指向该结点紧邻的下一个结点 当一个结点x的tag为0时,其lnk不空,应该指向结点序列中排在结点x的兄弟结 点后面的那个结点y。由于跟层次序列相关,需要使用队列。顺序扫描树的层次序列,若结 点的ltag值为1时,则置其link为空;否则把该结点x放入队列。如果遇到tag为1的结 点,这时该结点的兄弟结点链已经扫描完毕,下一个将要扫描的结点y就是结点x的最左孩3 由一些不相交子集构成，合并查集的基本操作是： 1) Find：判断两个结点是否在同一个集合中； 2) Union：归并两个集合。 像栈、队列一样，并查集也是一种重要的抽象数据类型，可以用于求解等价类问题。 划分等价类需要对集合进行三种操作： 1) 构造只含有一个元素的集合； 2) 判定某个元素所在的子集，目的是为了确定两个元素是否在同一个集合之中。即搜 索包含该元素的等价类，对于同一个集合中的元素返回相同的结果，否则返回不同的结果； 3) 归并两个不相交的集合为一个集合。 由于用根结点表示子集的类别，那么“查找”某一个元素所属的集合，只要从该结点出 发，沿父链域找到树的根结点即可。实现集合的“并”操作只要将一棵子树的根指向另一棵 子树的根即可。 每次合并前都需要进行两次查找，查找所需要的时间由树的高度决定，合并所需的时间 为 O(1)。容易看出，在最坏情况下，合并可能使 n 个结点的树退化成一条链。 为了防止树退化为单链，应该让每个结点到其相应根结点的距离尽可能小，可以做如下 两种改进。 第一种改进的方法是在做“合并”操作之前先判别子集中所含成员的数目，然后令含成 员少的子集的树根指向含成员多的子集的根，称作“重量权衡合并规则”（weighted union rule）。把小树合并到大树中去，可以把树的整体深度限制在Ｏ(logn)，每次 Find 操作只需要 O(logn)时间。 另一个办法是采用路径压缩（path compression）技术。在执行 Find 操作时，把结点到 树根的路径上所有结点的父指针都指向根结点。路径压缩可以缩短结点与根之间的路径。 (4) 带双标记的层次次序表示 由层次次序的性质可知，任何结点的子结点都排在该结点的所有兄弟结点后面。并且 任何结点的最后一个兄弟结点不会再有下一个兄弟，即最后一个兄弟的 rtag 为 1。由结点的 层次次序以及 ltag、rtag 两个标志位，就可以确定树的左孩子/右兄弟链表中结点的 llink 和 rlink 值。rlink 的值很容易确定：结点的 rtag 为 1，则 rlink 为空；结点的 rtag 为 0，则 rlink 指向该结点紧邻的下一个结点。 当一个结点 x 的 ltag 为 0 时，其 llink 不空，应该指向结点序列中排在结点 x 的兄弟结 点后面的那个结点 y。由于跟层次序列相关，需要使用队列。顺序扫描树的层次序列，若结 点的 ltag 值为 1 时，则置其 llink 为空；否则把该结点 x 放入队列。如果遇到 rtag 为 1 的结 点，这时该结点的兄弟结点链已经扫描完毕，下一个将要扫描的结点 y 就是结点 x 的最左孩