由于用根结点表示子集的类别,那么“查找”某一个元素所属的集合,只要从该结点出 发,沿父链域找到树的根结点即可。实现集合的“并”操作只要将一棵子树的根指向另一棵 子树的根即可。例如,上图(a)和(b)中的两棵树分别表示子集S1={1,3,5,7}和S2={2, 4,6,8}。图中的(c)就实现了S3=S1US2 SS, S (a)n个集合 (b)合并操作 合并操作的一个极端情况 每次合并前都需要进行两次查找,查找所需要的时间由树的高度决定,合并所需的时间 为O(1)。容易看出,在最坏情况下,合并可能使n个结点的树退化成一条链。下面就是 个例子。将上图(a)表示的子集合并时,每次都把集合元素多的根结点指向含元素少的根结 点,经过n-1次合并操作后得到的树的高度就为n,如上图(b所示。 为了防止树退化为单链,应该让每个结点到其相应根结点的距离尽可能小,可以做如下 两种改进。 第一种改进的方法是在做“合并”操作之前先判别子集中所含成员的数目,然后令含成 员少的子集的树根指向含成员多的子集的根,称作“重量权衡合并规则”( weighted union le)。把小树合并到大树中去,可以把树的整体深度限制在O(logn),每次Find操作只需要 O(ogn)时间。 树的父指针表示与 Union/find算法实现 class Par TreeNode i 树结点类定义 ∥结点的值 ParTreeNode<t> "p ∥父结点指针 n Count: ∥子树元素数目 Par TreeNodeo ∥构造函数 virtual -Par TreeNodeoti ∥析构函数 get Value ∥/返回结点的值5 由于用根结点表示子集的类别，那么“查找”某一个元素所属的集合，只要从该结点出 发，沿父链域找到树的根结点即可。实现集合的“并”操作只要将一棵子树的根指向另一棵 子树的根即可。例如，上图(a)和(b)中的两棵树分别表示子集 S1 = {1，3，5，7}和 S2 = {2， 4，6，8}。图中的(c)就实现了 S3 = S1∪S2。 每次合并前都需要进行两次查找，查找所需要的时间由树的高度决定，合并所需的时间 为 O(1)。容易看出，在最坏情况下，合并可能使 n 个结点的树退化成一条链。下面就是一 个例子。将上图(a)表示的子集合并时，每次都把集合元素多的根结点指向含元素少的根结 点，经过 n - 1 次合并操作后得到的树的高度就为 n，如上图(b)所示。 为了防止树退化为单链，应该让每个结点到其相应根结点的距离尽可能小，可以做如下 两种改进。 第一种改进的方法是在做“合并”操作之前先判别子集中所含成员的数目，然后令含成 员少的子集的树根指向含成员多的子集的根，称作“重量权衡合并规则”（weighted union rule）。把小树合并到大树中去，可以把树的整体深度限制在Ｏ(logn)，每次 Find 操作只需要 O(logn)时间。 树的父指针表示与 Union/Find 算法实现 template<class T> class ParTreeNode { // 树结点类定义 private: T value; // 结点的值 ParTreeNode<T> *parent; // 父结点指针 int nCount; // 子树元素数目 public: ParTreeNode(); // 构造函数 virtual ~ParTreeNode(){}; // 析构函数 T getValue(); // 返回结点的值 合并操作的一个极端情况 1 2 3 „„ n S1 S2 S3 Sn (a) n个集合 1 2 1 2 n 3 1 2 3 „ „„ (b) 合并操作