不相交集和联合数据结构 [英] Disjoint Set and Union Data Structure

问题描述

一个工会发现的结构是一种数据结构 支持以下操作：

●发现（X），其返回的重新presentative 节点x，和
●联盟（X，Y），合并含有x套 和y成一个单一的集

A union-find structure is a data structure supporting the following operations:

● find(x), which returns the representative of node x, and
● union(x, y), which merges the sets containing x and y into a single set.

查找（X）是具有 O（N）的时间复杂度，因此改善这一点，我们正在advisied的使用概念的排名

Find(x) is having a time complexity of O(n) , so to improve this we are advisied to used concept of Ranks

即。 较大的连接成分吃掉较小的一个

提高了时间复杂度为 O（LOGN）

我不明白我们是如何改进的时间复杂性上排名（深度）的基础知识融合的树木，以及如何O（LOGN）的时间复杂度实现的。

请帮我了解我自己排名的基础上，合并树的概念。

i.e. the larger connected component eats up the smaller one

Which improves the time complexity to O(logn)

I could not understand How we are improving Time Complexity By merging trees on their basics of Rank(Depth) , and How the O(logn) time complexity is achieved.

Please help me to Understand my concept of merging trees on the basis of their Rank.

推荐答案

关键是要了解树再presenting套的最大高度尺寸的log（n）+ 1 ，至此，继从任何给定的节点到它的根节点是完成O（日志（N））步骤。

The key is to understand the maximal height of the tree representing the sets is of size log(n) + 1, thus, following up nodes from any given node to its root is done by O(log(n)) steps.

我们现在必须证明，在不相交，集森林每棵树至多的log（n）+ 1 的高度索赔 - 其中 Ñ​​是在此树的节点数。我们会证明这一点通过归纳，并显示每个工会（X，Y）后 - 这个属性保持不变

We now have to prove the claim that each tree in the disjoint set forest is at most of height log(n) + 1 - where n is the number of nodes in this tree. We will prove it by induction and show that after each union(x,y) - this property remains unchanged.

基本：当我们开始，我们有 N 不同的树，各种规模的1 日志（1） + 1 = 1 - 所以每棵树确实是最大高度的log（n）+ 1

Base: When we begin, we have n different trees, all of size 1. log(1) + 1 = 1 - so each tree is indeed of maximal height log(n) + 1

联盟（X，Y）：我们团结两套，大小 X N1 尺寸的ŸN2 。不失一般性，让 N1＆LT; = N 。 出租车从归纳假设，高度H1树再presenting X 至多日志（N2）+1 因此，工会运作，通过改变 X 做的根本指向是的根。这意味着，在 X 所有节点的最大高度是现在最

Union(x,y): We unite two sets, x of size n1 and y of size n2. Without loss of generality, let n1<=n2.
From induction hypothesis, the height h1 of the tree representing x is at most log(n2)+1 So, the union operation is done by changing x's root to point to y's root. This means that the maximal height of any node that was in x is now at most

h1+1 = log(n1)+1 + 1 = log(n1) + log(2) + 1 = log(2*n1) + 1 = log(n1 + n1) + 1 <= log(n1 + n2) + 1

所以，我们刚刚发现的每个节点，这是正式的 X ，根的最大距离为日志（N1 + N2）+ 1 ，而新树的大小（ X 和是团结）现在 N1 + N2 ，所以我们证明了所期望的性质仍然是，这是正式的 X 所有节点。
对于是 - 根的距离保持，而树的大小不收缩 - 这样的属性是有效的也有。
结论 - 因为这是在 x中的节点或是，从新的根的最大深度为现在日志（N1 + N2）+1 ，按要求。
QED

So, we have just found out that for every node that was formally in x, the maximal distance to the root is log(n1+n2) + 1, and the size of the new tree (x and y united) is now n1+n2, so we proved that the desired property remains for any node that was formally in x.
For y - the distance to root remains, while the size of the tree does not shrink - so the property is valid there too.
In conclusion - for all node that was in x or y, the maximal depth from the new root is now log(n1+n2)+1, as required.
QED

备注 - 所有的日志在这个答案是与基地2

remark - all log in this answer is with base 2.

这篇关于不相交集和联合数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！