東京大学 情報理工学系研究科 コンピュータ科学専攻 2018年2月実施 問題3

标签：

• Tokyo-University
• Union-Find-Data-Structure

Author

kainoj

Description

Suppose that we have a set of $2^N$ elements and its partition into subsets where every element belongs to one and only one of the subsets. We want to support the following two operations for a partition.

• FIND(x) identifies the subset that element $x$ belongs to.
• MERGE(A, B) merges two subsets, $A$ and $B$.

We use a forest-of-trees structure, where each subset forms a tree. Each tree node corresponds to an element and has a pointer to its parent. The pointer of a root node points to the identity of the subset it belongs to. FIND(x) operation traces pointers from node $x$ to the root. MERGE(A, B) operation changes the pointer of the root node of subset $A$ so that it points to the root of subset $B$.

We initially have $2^N$ subsets, where each subset contains a single element. We then repeatedly merge a pair of subsets until we get a single subset containing all the elements. Height of a tree is defined as the number of edges on the longest path between its root and a leaf.

Answer the following questions:

(1) How many merge operations are required to merge all the subsets?

(2) What is the minimum (best case) tree height after the completion of all the merge operations among all the possible merge sequences? Also explain why.

(3) What is the maximum (worst case) tree height after the completion of all the merge operations among all the possible merge sequences? Also explain why.

(4) One can reduce the maximum (worst case) tree height by slightly modifying the MERGE(A, B) operation. Explain how to modify the operation. Also, give the maximum tree height when using the modified operation, with a brief explanation.

(5) One can reduce the height of a tree without increasing computational complexity by performing an additional procedure when applying the FIND(x) operation to an element $x$ in the tree. Explain how.

Kai

emph{See chapter $21$ of Cormen (3rd edition) for more.}

We have set of $2^N$ elements. MERGE($A, B$) changes $A$'s root's pointer so that it points root of $B$.

(1)

$2^N-1$ merge operations are required to merge all the subsets.

(2)

Minimum tree height: $1$ – one root with $2^N - 1$ leafs. How to: Fix root $r$ and perform MERGE($v, r$) for every other element $v \neq r$.

(3)

Maximum tree height: $2^N -1$. How to: start with a tree consisting of one element. While merging the tree and a node, make the tree point the node. In pseudo-code:

for i in range(1, 2**N):
    merge(v[i-1], v[i])

(4)

New MERGE(A, B): change pointer of the root node of subset with smaller height so that it points to root node of the other subset. This technique is called merge (union) by rank (rank - upper bound on the height of the node). How to get a tree with maximum height? The observation is, merging trees having the same height will result in a taller tree. If $A$ and $B$ have height of $h$, then merged tree is of height $h+1$.

Suppose we had a maximum-height tree with $2^N$ nodes. It must have been obtained by merging of two maximum-height trees with $2^{N-1}$ nodes.

$$H(2^N) = 1 + H(2^{N-1}) = N$$

(5)

During execution of FIND, we make every node on the find-path point directly to the root. This technique is called path compression*.

In details, first we find a path from a node its root. Then, we go through the path again and change pointers of nodes on the path. Original FIND was linear in length of the path. Now we scan the path twice, which still yields linear time.