algorithm - 在 Union-Find 算法中，是否/如何调整路径压缩中节点的等级

Question

路径压缩涉及将根分配为路径上每个节点的新父节点 - 这可能会降低根的等级，并且可能会降低路径上所有节点的等级。有没有办法解决这个问题？有必要处理这个吗？或者也许可以将等级视为树高度的上限而不是确切的高度？

谢谢！

Answer 1

是的，您可以将等级视为高度的上限。它的目的是将路径的长度限制为最多对数，通过强制执行不变量，即具有少于 2^k 个节点的树的高度小于 k。