我正在为联合/查找结构实现快速联合算法。在执行中给出 at the "Algorithms in Java" book site ，普林斯顿实现在实现路径压缩时无法保持树的大小不变(在 find() 方法中)。这不应该对算法产生不利影响吗？还是我错过了什么？另外，如果我是对的，我们将如何修改大小数组？
最佳答案
除非我弄错了，否则我认为这段代码确实维护了每棵树的根存储其子树中节点数的不变性。
创建数据结构时，请注意构造函数为森林中的每个节点设置了 sz[i] = 1。这意味着值一开始是正确的。
在联合 操作期间，数据结构会正确调整合并树根的大小。因此，在任何并集操作之后，所有的树根都具有正确的大小。
虽然您是正确的，在查找步骤中的路径压缩过程中大小没有更新，但数据结构没有理由在此处更改大小。路径压缩只是减少了从某棵树中的节点到树根的路径长度。它不会更改存储在该树中的节点数。因此，进行路径压缩的树的根部的大小信息不需要改变。虽然一些内部子树可能会丢失一些子树，因为它们在树的更高层重新设置父级，但这无关紧要，因为联合/查找结构只需要在其树的根部维护大小信息，而不是在内部节点。
总的来说，这意味着数据结构确实正确地存储了大小信息。对运行时没有不利影响，也不需要更正任何内容。
希望这对您有所帮助!
关于algorithm - 带路径压缩的加权快速联合 - 实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13791680/