Проблема при реализации метода Find () для непересекающегося множества

Question

Сейчас пытаюсь решить это некоторое время.Я получил Node в Disjoint Set. Реализация 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

На первую часть вашего вопроса уже ответил Стивен, и я думаю, что этого достаточно.

Что касается второй части вашего вопроса, я предполагаю, что у вас есть все узлы в списке.Итак, у вас есть 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;
}