1

我说的是union-find-disjoint 数据结构。互联网上有很多关于如何实现这一点的资源。到目前为止，我已经了解了两种联合优化技术。第一个是通过变量 Rank 来“平衡”树，它表示最深节点的深度，因此是 find() 的上限。第二个优化是：设置一个对象的父节点为头节点，同时调用find()（设置中还包含了对象的父节点，所以变成了级联优化）。

但是，当实现同时使用它们两者时，它们通常会不加思索地将两者合并在一起。具体来说，GeeksforGeeks（仅作为示例，没有任何个人内容）这样做。这不会导致排名“损坏”和 O(log n) 复杂性吗？

例如，如果我有一长串节点（5 到 4 到 3 到 2 到 1 到 0，这是头部）并且我调用 find() 到 2，则排名保持 5，即使它应该是 3。

4

2 回答 2

2

在这样的实现中，等级仍然是树高度的上限。它们确实可能成为不精确的上限。

log* 证明似乎并不依赖于该上限的准确性。

在上页底部链接的 Tarjan 1975 年的文章“良好但非线性集合联合算法的效率”中，他似乎使用了 union-by-size 而不是 union-by-rank。大小（顶点数）与精确等级不同，在每个联合的 O(1) 操作中很容易维护。

于 2015-04-12T08:59:34.433 回答
0

排名不是深度的严格衡量标准。来自维基百科：

使用术语等级而不是深度，因为如果还使用路径压缩 (...)，它不再等于深度

另请注意，您给出的示例不会发生。在按等级使用联合时，没有联合的顺序会导致一串单个节点。事实上，秩为 r 的树至少有 2 r个节点（用归纳法很容易证明）。我也不清楚您如何得出“太大”的等级会导致对数复杂性的结论。

于 2015-04-12T09:01:18.203 回答