问题描述
一个工会发现的结构是一种数据结构支持以下操作：
●发现（X），其返回的重新presentative节点x，和
●联盟（X，Y），合并含有x套和y成一个单一的集
A union-find structure is a data structuresupporting the following operations:
● find(x), which returns the representative ofnode x, and
● union(x, y), which merges the sets containing xand 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)+1So, 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.
这篇关于不相交集和联合数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！