union-find结构是一个支持以下操作的数据结构。find(x)，返回节点x的代表值；● union(x，y)，将包含x和y的集合合并成一个集合。
Find(x)的时间复杂度为 O(n) 因此，为了改善这种情况，我们建议使用以下概念 级别
即蚕食大的连接部件，蚕食小的连接部件 这提高了时间复杂度，以 O(logn) 我不明白我们是如何通过合并树的Rank(Depth)来提高时间复杂度的，以及如何实现O(logn)时间复杂度。请帮助我理解我的基于Rank的合并树的概念。
关键是要理解代表集合的树的最大高度是大小为 log(n) + 1因此，从任何一个给定节点到其根节点的后续节点是由 O(log(n)) 步。
我们现在要证明的是，不相集森林中的每一棵树的高度最多就是 log(n) + 1 - 哪儿 n 是这棵树的节点数。我们将用归纳法来证明它，并表明在每个 union(x,y) - 这个属性保持不变。
基础: 当我们开始时，我们有 n 不同的树，大小都是1。log(1) + 1 = 1 - 所以每棵树的高度确实是最大的 log(n) + 1
联盟(x,y): 我们联合了两组。x 大小 n1 和y的大小 n2. 在不失一般性的前提下，让 n1<=n2. 由归纳假设可知，代表树的高度h1．x 至多 log(n2)+1所以，工会操作是通过改变 x的根部指向 y的根。这意味着任何一个节点的最大高度在 x 现在最多
h1+1 = log(n1)+1 + 1 = log(n1) + log(2) + 1 = log(2*n1) + 1 = log(n1 + n1) + 1 <= log(n1 + n2) + 1
所以，我们刚刚发现，对于每一个正式进入的节点，都是在 x，到根的最大距离是 log(n1+n2) + 1和新树的大小(x 和 y 联合起来）现在是 n1+n2因此，我们证明了所需的属性对于任何形式上在 x. 对于 y - 到根部的距离保持不变，而树的大小并没有缩小--所以这个属性在那里也是有效的。 总而言之，对于所有在 x 或 y，现在距离新根的最大深度为 log(n1+n2)+1，根据需要。QED
评论--全部 log 在这个答案中是与基数2。