经典算法代码实现-union find算法3- weighted quick union方法
介绍了union find要解决的问题，基本的quick find和quick union方法，
其中,quick union方法在实际中已经比较快了， 当然在有些情况下，树可能会很高，所以，极端情况下每次树的高度都会加1。
这里，记录一个改进的方法。
weighted quick union方法
在quick union中，由于find和union的主要复杂度就来自于root操作，而root操作由树的高度决定。
既然quick union的问题在于树可能会一直长高，那么其实可以考虑是否能够避免树一直长高，
比如原来有两个节点连在一起， 高度是2， 这时候和另外一个节点union的时候，取决于union的顺序，树的高度可能是3（就是把2的树的根节点挂到1的根节点上），也可能仍然是2（就是把1的根节点挂到2上）。
那么，如果我们每次操作的时候都把1的根节点挂到2的根节点上，那么就可以减少树长高的概率。
同理推广到其他例子，每次union 的时候，看看那个节点高度比较小，把小的挂到大的节点上，树的高度就会长的比较慢。
但要记录树的高度会略麻烦，union的过程中不容易计算，实际上，只要用这个connected component里面的节点个数来作为判断依据，效果是一样的。
所以， 整体改动只有两个：
1. 记录每个root的节点个数
2. 每次union的时候， 从个数比较小的union到个数比较大的。
Read full article from 经典算法代码实现-union find算法3- weighted quick union方法
No comments:
Post a Comment