第三十三课程 Disjoint Set

Let root1 and root2 be two items that are roots of their respective trees. Here is code for the union operation with the union-by-size strategy.

public void union(int root1, int root2) {   (ref:union(int root1, int root2))
  if (array[root2] < array[root1]) {                 // root2 has larger tree
    array[root2] += array[root1];        // update # of items in root2's tree
    array[root1] = root2;                       // make root2 parent of root1
  } else {                                  // root1 has equal or larger tree
    array[root1] += array[root2];        // update # of items in root1's tree
    array[root2] = root1;                       // make root1 parent of root2
  }
}

this code is just keeped short for class ,is not a very well encapsulated union operation though, and the reason why is that a good union operation would hide the fact that certain node are roots of the tree, because really a disjoint set data structure, all the external caller is really supposed to know is that this is a set, they're not supposed to know that one of those items is special because that's an implementation detail and so really you'd like to hide that implementation detail it's what you really want to do is you really want to start this(union) by doing a find on each of these two nodes finding the roots of the two trees and then doing the union.

注意这个 union 和 find 操作对解决之前的 minimum spanning tree ,一个 weighted 图的最小生成树问题:

minimum spanning tree:

1. 遍历 E，不断从 E 中选择 weighted 最小的线段(v,w)
2. 如果 v，w 联通(可以通过判断两者各自所属 set 是否是一个 set，find 函数，比如 list-based disjoint data structue,每个 node
   都存了自己的 root-node 索引，就可以直接 find v 和 w 的 root-node 看是否相同，不同则说明两者不是一个 set，也就不联通)
   则忽略，如果不联通，则 union(set(v),set(w))(这个操作在 list-based disjoint 上就是把数目更小的 set 的每个 node 的
   root-node 索引设置成数目更多的 set 的 root-node 即可),然后将 v-w 存入结果中（结果应该是 v-w, g-h, h-w, v-z...）这个样子。
3. 一旦某个 set 包含了所有 node（这在 list-based disjoint 表现为所有 node 的 root-node 的 reference 都一样）就可以停止遍历 E 了。

回忆 graph 问题的两种 traversal 方法 ：

1. DFS： 可以用 recurvise 方式实现，
   1) set all node's 'visited' value false
   2) choose a start-node randomly
   3) visit(start-node)
   4) for every node connected with start-node ---- simply search (v,w) in E
   5) if visited, ignore; else, _recursively_ DFS(this node)
2. BFS: 无法用 recursive，而是用 queue
   1. set all node's visited value to false
   2. choose a start-node randomly
   3. visit(start-node), enqueue(start-node)
   4. _while_ queue is not empty:
      1. current-parent-node = dequeue()
      2. _for_ every node connected with start-node
         1. if visited,ignore; else,visited(this node), and enqueue(this node)

BFS 可以用在 minimum spanning tree 和 shorttest path 问题中;

The find() method is equally simple, but we need one more trick to obtain the best possible speed. Suppose a sequence of union operations creates a tall tree, and we perform find() repeatedly on its deepest leaf. Each time we perform find(), we walk up the tree from leaf to root, perhaps at considerable expense. When we perform find() the first time, why not move the leaf up the tree so that it becomes a child of the root? That way, next time we perform find() on the same leaf, it will run much more quickly. Furthermore, why not do the same for every node we encounter as we walk up to the root?

we do it in a lazy way which is we don't do it until there's a reason, like if no one ever does a find operation on one node,then why waste time fixing its pointer.

      0
     /|\                                      _ 0 _
    1 2 3                                    / /|\ \
   /|\             ==find(7)==>             7 4 1 2 3
  4 5 6                                      /| |\
 /|\                                        8 9 5 6
7 8 9

In the example above, find(7) walks up the tree from 7, discovers that 0 is the root, and then makes 0 be the parent of 4 and 7, so that future find operations on 4, 7, or their descendants will be faster. This technique is called path_compression.

Let x be an item whose set we wish to identify. Here is code for find, which returns the identity of the item at the root of the tree.

public int find(int x) {
  if (array[x] < 0) {
    return x;                         // x is the root of the tree; return it
  } else {
    // Find out who the root is; compress path by making the root x's parent
    array[x] = find(array[x]);        // in tree-based data structure, array[x] store the parent of x
                                      // this will,at last make root store in array[x]
    return array[x];                  // Return the root
  }
}

Union-by-size means that if Microsoft acquires US Air, US Air will be the root of the tree(Microsoft'tree is smaller than US Air's), even though the new conglomorate might still be called Microsoft.

What if we want some control over the names of the sets when we perform union() operations?

The solution is to maintain an additional array that maps root items to set names (and perhaps vice versa, depending on the application's needs). For instance, the array "name" might map 0(where US Air stored) to Microsoft.

这个意思大概是维护另一个数组–name[]，数组下标与 root 节点的在另一数组的下标相同，但存储的是该 set 的名字，比如这里的 microsoft：

_______________________________
| US Air | xxxx | xxxx | xxxx |
-------------------------------
    0       1       2      3
_______________________________
| microsoft |   |   |   |
-------------------------------
    0

We must modify the union() method so that when it unites two sets, it assigns the union an appropriate name.

For many applications, however, we don't care about the name of a set at all; we only want to know if two items x and y are in the same set. This is true in both Homework 9 and Project 3. You only need to run find(x), run find(y), and check if the two roots are the same.

• Union: theta(1)

Union operations obviously take Theta(1) time. (Look at the code–no loops or recursion.)

• Find: theta(log u)

If we use union-by-size, a single find operation can take Theta(log u) worst-case time, where u is the number of union operations that took place prior to the find. The only way to increase the height of the tree by one is to at least double its size from the minimum possible size.

就像之前如果 find()一个叶子节点，需要从叶子->父节点->…->root。所以这又是一个树的深度问题，所以树的深度就是 O(log(n))

• Average running time of find() by path compression: Constant

Path compression does not improve this worst-case time, but it improves the average running time substantially–although a find operation can take Theta(log u) time, path compression will make that operation fast if you do it again. The average running time of find and union operations in the quick-union data structure(注意，对于 disajoint 数据结构：quick-union 就是指 tree-based, quick-find 就是 list-based) is so close to a constant that it's hardly worth mentioning that, in a rigorous asymptotic sense, it's slightly slower.

• quick-Union Total: theta(u+f*alpha(f+u,u)), constant approximately.

The bottom line: a sequence of f find and u union operations (in any order and possibly interleaved) takes Theta(u + f alpha(f + u, u)) time in the worst case. alpha is an extremely slowly-growing function known as the inverse Ackermann_function.

When I say "extremely slowly-growing function", I mean "comically slowly- growing function." The inverse Ackermann function is never larger than 4 for any values of f and u you could ever use (though it does grow arbitrarily large–for unimaginably gigantic values of f and u). Hence, for all practical purposes (but not on the Final Exam), you should think of quick-union as having find operations that run, on average, in constant time.