5.10 集合表示

用树来表示集合时,为了简单起见,假设集合中的元素是数字 0,1,2,,n10, 1, 2, \cdots, n-1。在实际中,这些数字可能是符号表的索引,表中存储了元素的实际名字。还假设所表示的集合是两两互不相交的。

例如,将编号为 0099 的 10 个元素,分成三个互不相交的集合,S1={0,6,7,8}S_1 = \{0, 6, 7, 8\}S2={1,4,9}S_2 = \{1, 4, 9\}S3={2,3,5}S_3 = \{2, 3, 5\}。这些集合的一种可能的存储表示如下图。注意,对于每一个集合,每一个儿子结点有一个指向父亲结点的父亲域,而不是通常的父亲结点指向儿子结点的儿子域。

5-31

现研究两种操作的算法方案:

  • 「不相交集合的并 disjoint set union」操作。如果 SiS_iSjS_j 是互不相交的集合,那么它们的并操作 SiSj={0,6,7,8,1,4,9}S_i \cup S_j = \{0, 6, 7, 8, 1, 4, 9\}
  • 查找操作。查找包含元素 ii 的集合。例如,元素 33 在集合 S3S_3 中。
方案一

先考虑 union 操作。假设想得到集合 S1S_1S2S_2 的并集。由于已经把结点从儿子结点链接到父亲结点了,因此,可以简单的让其中一棵树成为另一棵树的子树。S1S2S_1 \cup S_2 可以存储表示成下图中任何一棵。

5-32

此外,如果每一个根结点都有一个指向集合名字的指针,那么就可以通过指向根结点的父链来找到元素所在的集合。

由于树中结点被编号为 00n1n - 1,所以,可以把结点的编号作为下标。这就意味着每一个结点只需要一个链域到其父结点,即父结点的下标。因此,最理想的数据结构就是数组 int parent[MAX_ELEMENTS],其中 MAX_ELEMENTS 是元素的最大目录。集合 S1S_1S2S_2S3S_3 的这种存储表示如下图。注意,根结点的父亲是 -1

i [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
parent -1 4 -1 2 -1 2 0 0 0 4

这时考虑 find 操作,从下标 i 开始,上溯到下标值为负值的父结点,这样就可以实现 find(i) 操作。

方案二

虽然方案一很容易实现,但它们的性能却不是很好。例如,如果开始时有 pp 个元素,每一个元素自成一个集合,即 Si={i}S_i = \{ i\}0i<p0 \leq i < p,那么集合最初的状态是一个有 pp 个结点的森林,且 parent[i] = -10i<p0 \leq i < p。现在执行下列 Union, Find 操作序列:

Union(0, 1); Find(0);
Union(1, 2); Find(0);
...
Union(n-2, n-1); Find(0);

这个操作序列产生了如下图的 「退化树 degenerate tree」。由于 Union 操作的时间开销是常量,因此可以在 O(n)O(n) 时间内执行 n1n - 1Union 操作。然而,对每一个 Find 操作,必须经过从 00 到根结点的父链路径。如果元素在第 ii 层,那么查找其根结点所需的时间就是 O(i)O(i)。因此,执行 n1n - 1Find 操作所需要的总时间就是 i=2ni=O(n2)\sum_{i=2}^n i = O(n^2)

退化树

通过避免产生退化树,可以得到 UnionFind 操作更加有效的实现。为此,采用下面的加权规则来实现 Union(i, j)

  • Union(i, j)「加权规则 weighting rule」 是:如果树 i 的结点树少于树 j 的结点树,则令树 j 是树 i 的父亲;否则,令树 i 是树 j 的父亲。

为了实现加权规则,需要知道每棵树的结点树,于是在每棵树的根结点保留一个计数域。并且因为树中所有结点(根结点除外)在父亲域都有一个非负数,所以,可以把结点的计数值作为负数保存在根结点的父亲域中。下图为上述集合并操作序列的过程。

5-34

TT 为方案二所建立的具有 nn 个结点的树。那么树 TT 中任意结点的层数至多为 log2n+1\lfloor \log_2n \rfloor + 1。那么对于有 nn 个元素的树执行查找操作,所需要的时间为 O(log2n)O(\log_2n)。如果要处理 n1n - 1 个并和 mm 个查找组成的混合操作序列,那么时间开销为 O(n+mlog2n)O(n + m\log_2n)

现考虑下列方案二并操作序列,初始时有 232^3 个元素,每个元素自成一个集合。

Union(0, 1); Union(2, 3); Union(4, 5); Union(6, 7);
Union(0, 2); Union(4, 6); Union(0, 4);

5-35

达到最坏情况上界的树

引入「折叠规则」。

  • 「折叠规则 collapsing rule」 如果 j 是从 i 到其根结点的路径上的一个结点,那么将 j 作为根结点的儿子。

同样考虑上述并操作所建立的树。现进行下面 8 个查找操作:

Find(7); Find(7); ... Find(7);

使用旧版本的查找操作时,每个 Find(7) 需要上溯 3 个父链域,进行所有 8 个查找操作需要移动 24 步。而采用新版本的查找操作时,第一个 Find(7) 需要上溯 3 个链域,并重置两个链(结点 6 和结点 7)。剩下的每 7 个查找操作只需要上溯 1 个链域。因此,总共的移动次数只有 13 步。

  • 「Tarjan」T(m,n)T(m, n) 是处理由 mnm \geq n 个查找操作和 n1n - 1 个并操作组成的混合操作序列执行时间的最大值,那么存在正的常量 k1k_1k2k_2,使得: k1mα(m,n)T(m,n)k2mα(m,n) k_1m\alpha(m, n) \leq T(m, n) \leq k_2m\alpha(m, n) 其中 α(m,n)\alpha(m, n) 是个增长很慢的函数,这个函数与 Ackermann 函数的功能正好相反。其定义为: α(m,n)=min{z1A(z,4m/n)>log2n} \alpha(m, n) = \min\{z \geq 1 | A(z, 4\lceil m/n\rceil) > \log_2n \} 这里所使用的 Ackermann 函数的定义为: A(x,y)={y+1if x=0A(x1,1)if y=0A(x1,A(x,y1))otherwise A(x, y) = \begin{cases} y + 1 & \mathrm{if} \ x = 0 \\ A(x-1, 1) & \mathrm{if} \ y = 0 \\ A(x-1, A(x, y-1)) & \mathrm{otherwise} \end{cases} 本节相关研究 并查集 - Wikipedia Ackermann 函数相关研究 阿克曼函数 - Wikipedia

  • 『等价类』 用 union-find 算法来处理 4.5 等价关系 的等价对。开始时,nn 个元素的每一个自身构成一个等价类。当处理等价对 iji \equiv j 时,查找 iijj 所属集合,若它们是不同的集合,则用这两个集合的并来代替它们。为了处理每一个等价对,要执行两次查找操作和至多一次并操作。因此,如果有 nn 个元素和 mnm \geq n 个等价对,那么总共的处理时间至多为 O(mα(2m,n))O(m\alpha(2m, n))。虽然对于非常大的 nn,这个算法比 4.5 节的算法差一些,但这个算法需要的存储空间较小。

results matching ""

    No results matching ""