21.3 Disjoint-set forests

21.3-1

Redo Exercise 21.2-2 using a disjoint-set forest with union by rank and path compression.

Text Only
        1
 /    /    \       \
2    3      5       9
     |     / \     / \      \
     4    6   7   10 11     13
              |      |      / \
              8      12    14 15
                              |
                              16

21.3-2

Write a nonrecursive version of \(\text{FIND-SET}\) with path compression.

To implement \(\text{FIND-SET}\) nonrecursively, let \(x\) be the element we call the function on. Create a linked list \(A\) which contains a pointer to \(x\). Each time we most one element up the tree, insert a pointer to that element into \(A\). Once the root \(r\) has been found, use the linked list to find each node on the path from the root to \(x\) and update its parent to \(r\).

21.3-3

Give a sequence of \(m\) \(\text{MAKE-SET}\), \(\text{UNION}\), and \(\text{FIND-SET}\) operations, \(n\) of which are \(\text{MAKE-SET}\) operations, that takes \(\Omega(m\lg n)\) time when we use union by rank only.

Suppose that \(n' = 2k\) is the smallest power of two less than \(n\). To see that this sequences of operations does take the required amount of time, we'll first note that after each iteration of the for loop indexed by \(j\), we have that the elements \(x_1, \dots, x_{n'}\) are in trees of depth \(i\). So, after we finish the outer for loop, we have that \(x_1, \dots, x_{n'}\) all lie in the same set, but are represented by a tree of depth \(k \in \Omega(\lg n)\). Then, since we repeatedly call \(\text{FIND-SET}\) on an item that is \(\lg n\) away from its set representative, we have that each one takes time \(\lg n\). So, the last for loop alltogther takes time \(\Omega(m \lg n)\).

C++
    for i = 1 to n
        MAKE-SET(x[i])
    for i = 1 to k
        for j = 1..n' - 2^{i = 1} by 2^i
            UNION(x[i], x[i + 2^{j - 1}])
    for i = 1 to m
        FIND-SET(x[1])

21.3-4

Suppose that we wish to add the operation \(\text{PRINT-SET}(x)\), which is given a node \(x\) and prints all the members of \(x\)'s set, in any order. Show how we can add just a single attribute to each node in a disjoint-set forest so that \(\text{PRINT-SET}(x)\) takes time linear in the number of members of \(x\)'s set and the asymptotic running times of the other operations are unchanged. Assume that we can print each member of the set in \(O(1)\) time.

In addition to each tree, we'll store a linked list (whose set object contains a single tail pointer) with which keeps track of all the names of elements in the tree. The only additional information we'll store in each node is a pointer \(x.l\) to that element's position in the list.

When we call \(\text{MAKE-SET}(x)\), we'll also create a new linked list, insert the label of \(x\) into the list, and set \(x.l\) to a pointer to that label. This is all done in \(O(1)\).
\(\text{FIND-SET}\) will remain unchanged.
\(\text{UNION}(x, y)\) will work as usual, with the additional requirement that we union the linked lists of \(x\) and \(y\), since we don't need to update pointers to the head, we can link up the lists in constant time, thus preserving the runtime of \(\text{UNION}\).
Finally, \(\text{PRINT-SET}(x)\) works as follows: first, set \(s = \text{FIND-SET}(x)\). Then print the elements in the linked list, starting with the element pointed to by \(x\). (This will be the first element in the list). Since the list contains the same number of elements as the set and printing takes \(O(1)\), this operation takes linear time in the number of set members.

21.3-5 \(\star\)

Show that any sequence of \(m\) \(\text{MAKE-SET}\), \(\text{FIND-SET}\), and \(\text{LINK}\) operations, where all the \(\text{LINK}\) operations appear before any of the \(\text{FIND-SET}\) operations, takes only \(O(m)\) time if we use both path compression and union by rank. What happens in the same situation if we use only the path-compression heuristic?

Clearly each \(\text{MAKE-SET}\) and \(\text{LINK}\) operation only takes time \(O(1)\), so, supposing that \(n\) is the number of \(\text{FIND-SET}\) operations occuring after the making and linking, we need to show that all the \(\text{FIND-SET}\) operations only take time \(O(n)\).

To do this, we will ammortize some of the cost of the \(\text{FIND-SET}\) operations into the cost of the \(\text{MAKE-SET}\) operations. Imagine paying some constant amount extra for each \(\text{MAKE-SET}\) operation. Then, when doing a \(\text{FIND-SET}(x)\) operation, we have three possibilities:

First, we could have that \(x\) is the representative of its own set. In this case, it clearly only takes constant time to run.
Second, we could have that the path from \(x\) to its set's representative is already compressed, so it only takes a single step to find the set representative. In this case also, the time required is constant.
Third, we could have that \(x\) is not the representative and it's path has not been compressed. Then, suppose that there are k nodes between \(x\) and its representative. The time of this \(\text{FIND-SET}\) operation is \(O(k)\), but it also ends up compressing the paths of \(k\) nodes, so we use that extra amount that we paid during the \(\text{MAKE-SET}\) operations for these \(k\) nodes whose paths were compressed. Any subsequent call to find set for these nodes will take only a constant amount of time, so we would never try to use the work that amortization amount twice for a given node.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用