为不相交集实现Find()方法时出现问题

Question

我已经尝试解决这个问题一段时间了。我在一个Disjoint集合中得到了一个Node。Node的实现是作为一个类，它要么有一个不同的父节点，要么是它自己的

class Node {
Node parent;
int rank;
//...constructor and method declarations}

现在，我必须用路径压缩来实现这个类的Find方法，称为getParent((方法。我写了以下代码：

Node getParent(){
while(parent != this)
{
parent = parent.getParent();  
}
return parent;

我用这段代码得到了无限递归。我知道它有问题，但我不知道如何修复它。我尝试使用this关键字，但它导致了同样的错误。请帮忙。此外，深入了解如何以迭代方式编写此代码将是一大优势。此外，我想重组树，使调用getParent((的节点和根之间的所有中间节点都有一个公共的父节点，即根节点。

Answer 1

Stephen已经回答了您问题的第一部分，我认为这已经足够完整了。

关于你问题的第二部分，我假设你有一个列表中的所有节点。所以你有List<Node> allNodes。重组树所需的方法是：

public void reStructureTree(List<Node> allNodes){
for(Node item: allNodes){
Node p = item.parent;
List<Node> branch = new ArrayList<>();
while (p.parent != p){
branch.add(p);
p = p.parent;
}
for(Node branchItem : branch){
branchItem.parent = p;
}
}
}

在最坏的情况下，这种方法的顺序是O(n^2)，我没有寻找更好的方法，因为你没有提到它的重要性

Answer 2

Node getParent() {
while (parent != this) {
parent = parent.getParent();  
}
return parent;
}

问题：

1. 您正在更改parent字段
2. 你应该测试父母的父母是否是自己。。。不是这个

您的代码可能应该是：

Node getParent() {
Node p = parent;
while(p.parent != p) {
p = p.parent;  
}
return p;
}

或者递归：

Node getParent() {
return (parent == this) ? this : parent.getParent();
}

(在这种情况下，迭代版本更安全。你不应该得到"无限"递归，但仍然有可能递归得太深，具有病态的深层数据结构。(

---

更新-显然，您的意图是getParent应该(逐步(折叠它访问的每个Node的父链。在这种情况下，递归解决方案是：

Node getParentAndCollapse() {
if (parent == this) {
return this;
} else {
parent = parent.getParentAndCollapse();
return parent;
}
}

折叠整个链的迭代解决方案需要链的两个遍历：

1. 遍历链，找到最终父级
2. 再次遍历链，更新所有parent字段以引用最终父级
3. 返回最终的父对象

类似的东西

Node getParentAndCollapse() {
Node p = getParent();  // iterative version
Node n = this;
while (n.parent != p) {
Node np = n.parent;
n.parent = p;
n = np;
}
return p;
}