加速并査集运算的另一个办法是采用路径压缩( path compression)技术。在执行Find 操作时,把结点到树根的路径上所有结点的父指针都指向根结点。例如下图(a)表示了依次 合并集合{7,9,10}、{5,6,8}、{2,4}和{1,3}后所形成的树。下图b)表示出了查找结 点7的根时,对结点7到根所涉及的结点进行压缩路径之后的树形态。路径压缩可以缩短结 点与根之间的路径。 (a)路径压缩之前 (b)路径压缩之后 路径压缩示例 带路径压缩的 FindPC算法 template<class t> Par TreeNode<t>' Par Tree<T> FindPC(Par TreeNode<t> *node)const i f (node->getParentO=NULL) node->setParent(FindPC(node->get ParentO) return node->getParentO 路径压缩大大加速了Find运算。在执行 Union时总是将小树并到大树上,而且在执行 Find时实行路径压缩,则可以证明n次Find至多需要O(n(n)时间。其中α(n)是单变量 Ackermann函数的逆,它是一个增长速度比logn慢得多但又不是常数的函数。在实际应用 中,α(n)往往小于4。因此,执行一串交错的合并和查找操作所需要的时间几乎与合并和查 找的次数成线性关系。上述路径压缩算法是目前最有效的并查集实现方法 8.总结 树”这一章介绍了树以及森林的概念、术语及表示方法。联系到树形结构的具体应用, 在存储器中有许多不同的表示树形结构的方法。本章重点介绍了链式存储和顺序存储。在树7 } } } 加速并查集运算的另一个办法是采用路径压缩（path compression）技术。在执行 Find 操作时，把结点到树根的路径上所有结点的父指针都指向根结点。例如下图(a)表示了依次 合并集合{7，9，10}、{5，6，8}、{2，4}和{1，3}后所形成的树。下图(b)表示出了查找结 点 7 的根时，对结点 7 到根所涉及的结点进行压缩路径之后的树形态。路径压缩可以缩短结 点与根之间的路径。 带路径压缩的 FindPC 算法 template<class T> ParTreeNode<T>* ParTree<T>::FindPC(ParTreeNode<T> *node) const { if (node->getParent() == NULL) return node; node->setParent(FindPC(node->getParent())); return node->getParent(); } 路径压缩大大加速了 Find 运算。在执行 Union 时总是将小树并到大树上，而且在执行 Find 时实行路径压缩，则可以证明 n 次 Find 至多需要 O(nα(n))时间。其中 α(n)是单变量 Ackermann 函数的逆，它是一个增长速度比 logn 慢得多但又不是常数的函数。在实际应用 中，α(n)往往小于 4。因此，执行一串交错的合并和查找操作所需要的时间几乎与合并和查 找的次数成线性关系。上述路径压缩算法是目前最有效的并查集实现方法。 8．总结 “树”这一章介绍了树以及森林的概念、术语及表示方法。联系到树形结构的具体应用， 在存储器中有许多不同的表示树形结构的方法。本章重点介绍了链式存储和顺序存储。在树 路径压缩示例 1 2 3 4 5 6 7 8 9 10 （a）路径压缩之前 （b）路径压缩之后 1 2 4 3 5 6 8 7 9 10