東京大学 情報理工学系研究科 コンピュータ科学専攻 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.

题目描述

给定 $2^N$ 个元素及其一个划分，每个元素恰属于一个子集。需要支持：

• FIND(x)：确定元素 $x$ 所属的子集；
• MERGE(A, B)：合并两个子集 $A$ 与 $B$。

采用树森林表示，每个子集对应一棵树，每个结点对应一个元素并含父指针；根结点的指针指向其所属子集的标识。FIND(x) 从 $x$ 沿父指针走到根； MERGE(A,B) 将子集 $A$ 的根指针改为指向子集 $B$ 的根。

初始有 $2^N$ 个单元素子集，随后反复合并两个子集，直至得到包含全部元素的一个子集。树高定义为根到叶的最长路径所含边数。回答下列问题。

（1）将所有子集合并成一个集合需要多少次合并操作？

（2）在所有可能的合并顺序中，完成后树高的最小值（最好情况）是多少？说明理由。

（3）完成后树高的最大值（最坏情况）是多少？说明理由。

（4）如何稍微修改 MERGE(A,B) 以降低最坏情况下的树高？给出修改后的最大树高并简述理由。

（5）执行 FIND(x) 时可增加一个不会提高计算复杂度、但能降低树高的步骤。说明这一操作。

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.