普林斯顿公开课 算法1-9：并查集-高速合并
浏览数：24 /
时间：2015年06月08日
本节讲的是并查集的第二种实现方法。这样的方法的合并操作开销非常小，可是查找操作开销非常大。
数据结构
这样的算法的数据结构和高速查找方法的数据结构是一样的，也是N个整数组成的数组。
数组中每一个元素id[i]的含义是指i的上级是id[i]。
根节点
一个节点的根节点就是id[id[id[...id[i]....]]]，一直循环直到数值不再变化为止。因为算法的特性，这样的循环永远不会造成死循环。
查找操作
查找操作就是推断两个节点的根节点是否同样。
合并操作
合并节点p和节点q就是将p节点的根节点的父节点设置为q节点的根节点。这样仅仅须要改变一个值，因此开销少了非常多。
复杂度
这样的方法尽管性能方面提升了非常多，可是仍然不够，由于最坏的情况下，查找操作的复杂度将达到N。
对照
高速查找方法中合并的开销太大，可是建立的树结构是平坦的，所以查找操作的开销极小，可是合并操作中建立平坦的树开销很大。
高速合并方法中树形结构可能会很高。这样的情况下查找操作的开销很大，复杂度能够达到N。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
