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

Question

我正在为联合/查找结构实现快速联合算法。在执行at the "Algorithms in Java" book site时，普林斯顿实现在实现路径压缩时（在find()方法中）未能保持树的大小不变。这不应该对算法产生不利影响吗？或者我错过了什么？另外，如果我是对的，我们将如何去修改大小数组？

Answer 1

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

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

在union操作期间，数据结构正确调整合并树的根的大小。因此，任何工会操作之后，所有的树根有正确的尺寸。

虽然你是正确的路径在压缩过程中发现一步未更新的大小，没有理由认为该数据结构将改变这里的大小。路径压缩只是减少了某些树中的节点到树根的路径长度。它不会更改该树中存储的节点数量。因此，经历路径压缩的树的根部的大小信息不需要改变。虽然一些内部子树可能会失去一些孩子，因为他们重设父爬在树上高，这是无关紧要，因为工会/查找结构只需要在其树的根，以保持大小信息，而不是在内部节点。

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

希望这会有所帮助！