我正在为联合/查找结构实现快速联合算法。在“Java 中的算法”图书站点给出的实现中，普林斯顿实现在实现路径压缩（在find()方法中）时未能保持树的大小不变。这不应该对算法产生不利影响吗？还是我错过了什么？另外，如果我是对的，我们将如何修改大小数组？
问问题
1546 次
1 回答
3
除非我弄错了，否则我认为这段代码确实保持了每棵树的根存储其子树中节点数的不变量。
创建数据结构时，请注意构造函数sz[i] = 1为林中的每个节点设置。这意味着这些值开始时是正确的。
在联合操作期间，数据结构正确调整合并树的根的大小。因此，在任何联合操作之后，所有的树根都有正确的大小。
虽然您在查找步骤中的路径压缩期间没有更新大小是正确的，但数据结构没有理由在这里改变大小。路径压缩只是减少从某些树中的节点到树根的路径长度。它不会更改存储在该树中的节点数。因此，在进行路径压缩的树的根部的大小信息不需要改变。尽管一些内部子树可能会因为它们在树中更高的位置而失去一些子树，但这无关紧要，因为联合/查找结构只需要在其树的根部维护大小信息，而不是在内部节点处。
总的来说，这意味着数据结构确实正确地存储了大小信息。对运行时没有不利影响，也不需要纠正任何事情。
希望这可以帮助！
于 2012-12-27T19:08:38.033 回答