带路径压缩的加权快速联合-实现

Question

我正在为联合/查找结构实现快速联合算法。在“Java中的算法”一书网站上给出的实现中，普林斯顿实现在实现路径压缩（在find（）方法中）时无法保持树的大小不变。这不应该对算法产生不利影响吗？还是我错过了什么？另外，如果我是对的，我们将如何修改大小数组？

Answer 1

除非我错了，否则我认为这段代码确实保持了每棵树的根存储其子树中节点数的不变量。

创建数据结构时，注意构造函数为森林中的每个节点设置了< code>sz[i] = 1。这意味着这些值开始时是正确的。

在联合操作期间，数据结构正确地调整合并树的根的大小。因此，在任何联合操作之后，所有的树根都具有正确的大小。

虽然在查找步骤中的路径压缩期间大小没有更新是正确的，但这里的数据结构没有理由改变大小。路径压缩只是减少了从某棵树中的节点到树根的路径长度。它不会改变存储在该树中的节点数量。因此，进行路径压缩的树的根部的大小信息不需要改变。尽管一些内部子树可能会丢失一些子树，因为它们在树中的较高位置被重新标记，但这无关紧要，因为联合/查找结构只需要在其树的根部维护大小信息，而不是在内部节点。

总体而言，这意味着数据结构确实正确存储了大小信息。对运行时没有负面影响，也不需要更正任何内容。

希望这有所帮助！