algorithm - 不相交集和并集数据结构

Question

联合查找结构是一种数据结构支持以下操作:

● find(x)，返回代表节点 x，和
● union(x, y)，合并包含 x 的集合和 y 成一个集合。

Find(x) 的时间复杂度为 O(n) ，因此为了改进这一点，我们建议使用 Ranks

的概念

即较大的连接组件吃掉较小的连接组件

这将时间复杂度提高到O(logn)

我无法理解我们如何通过在 Rank(Depth) 的基础上合并树来提高时间复杂度，以及如何实现 O(logn) 时间复杂度。

请帮助我理解我根据等级合并树的概念。

Answer 1

关键是要了解表示集合的树的最大高度大小为 log(n) + 1 ，因此，从任何给定节点到其根节点的后续节点由 O(log(n)) 完成步骤。

我们现在必须证明不相交集合森林中的每棵树的高度最多为 log(n) + 1。 - 哪里n是这棵树中的节点数。我们将通过归纳法证明它并证明在每个 union(x,y) 之后- 此属性保持不变。

Base:开始时，我们有 n不同的树，大小都是 1。log(1) + 1 = 1 - 所以每棵树确实是最大高度 log(n) + 1

Union(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 为基数。