Эквивалентное поддерево

Question

У меня есть два дерева. Узел дерева определяется как

class Node{
  String treeId; 
  String type;       //Each node has type which has fixed value. For example, its color: RED, BLANK, GREEN
  Set<Node> children;
  String ref;        //The ref is a string and allowed value are "0", "1",..."10". The value is null if it is not leaf. 
};

Для листа набор детей пуст.

Мне интересно, есть ли какая-то существующая эффективная работа, проделанная, как идентифицировать эквивалентное поддерево для двух данных деревьев. Эквивалент определяется как:

1) Both subtree leaves are setsets leaves of original tree. 
2) Both subtrees leaves have same ref value. 
3) for non-leaves node, the equivalent refers to both node have same type and equivalent children. 

Благодарю. Было бы лучше, если бы есть какая-то библиотека Java, решающая эту проблему.

---

Входными данными должны быть два корня дерева, а выходным - это узел, который является корнем эквивалентного поддерева. Высота дерева составляет 100~, и в нем более 500 узлов.

---

Что я сделал сейчас, так это то, что добавил новое поле для класса Node.

class Cache{
   Map<String, Set<String>> map = new LinkedHashMap<String, Set<Str>>();
}

Ключом карты является Node id, в то время как значением является набор ссылок, которого может достичь этот узел этого nodeid. Кэш инициируется при инициализации узла.

Во время фазы сравнения isEquivalent проверьте, существует ли перекрытие между двумя наборами ссылок корня. Вернуть false, если нет.

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

Answer 1

Я не уверен насчет 1) Both subtree leaves are leaves of original tree. Требование, как кажется, противоречит how to identify equivalent substree for two given tree., В противном случае следующий рекурсивный метод должен быть в состоянии охватить два других условия. haveSameOriginalTree(r1, r2) метод может быть реализован, чтобы удовлетворить первое условие, которое я не мог понять. r1 а также r2 являются корнями двух поддеревьев, которые необходимо проверить на эквивалентность.

bool areEquivalent(Node r1, Node r2)
{
    if(r1.children == null && r2.children == null)
    {
        return (haveSameOriginalTree(r1, r2) && (r1.ref == r2.ref));
    }
    if((r1.children == null && r2.children != null) || (r1.children != null && r2.children == null))
    {
        return false;
    }
    // if here then both must be non-leaf nodes
    if(r1.type != r2.type)
    {
        return false;
    }
    if(r1.children.getCount() != r2.children.getCount()) // not sure of correct syntax for Java Sets
    {
        return false;
    }
    for(int i=0; i<r1.children.getCount(); i++)
    {
        if(!areEquivalent(r1.children[i], r2.children[i])) // again please correct the syntax for Sets
        {
            return false;
        }
    }

    return true;
}

Дайте мне знать, что вы думаете.

Обновить

Вот итерационная версия вышеуказанного решения. Он использует структуру данных стека, которая размещается в куче, а не помещается в стек вызовов функций, поэтому не сильно отличается от рекурсивной, но все же лучше. Кроме того, так как мы держим только ссылки на Nodes (вместо того, чтобы копировать весь объект), это не должно быть большим дополнительным расходом памяти, если мы уже загружаем исходное дерево в память.

bool areEquivalent(Node r1, Node r2)
{
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    Node n1, n2;

    s1.Push(r1);
    s2.Push(r2);
    while(true) // Need a better check
    {
        if(s1.getCount() != s2.getCount())
        {
            return false;
        }
        if(s1.getCount() == 0) // if both stacks are empty then we've traversed both trees without failure.
        {
            return true;
        }
        n1 = s1.Pop();
        n2 = s2.Pop();
        if(!areEquivalentNodes(n1, n2))
        {
            return false;
        }
        foreach(Node child in n1.children)
        {
            s1.Push(child);
        }
        foreach(Node child in n2.children)
        {
            s2.Push(child);
        }
    }
}

// only checks the two nodes are equivalent. their childrens' equivalence will be handled by other calls to this method.
bool areEquivalentNodes(Node n1, Node n2)
{
    if(n1.children.getCount() != n2.children.getCount())
    {
        return false;
    }
    if(n1.children.getCount() == 0) // if both are leaf nodes...
    {
        if(n1.ref != n2.ref)
        {
            return false;
        }
    }
    else // both are non-leaf
    {
        if(n1.type != n2.type)
        {
            return false;
        }
        // the condition that children of non-leaf nodes be equivalent will be covered by subsequent calls this method...
    }

    return true;
}

Обратите внимание, что оба решения ожидают children из двух эквивалентных узлов в одном порядке. Если children не упорядочены, тогда нам нужно будет отсортировать их перед вызовом кода выше.

Дайте мне знать, если это лучше.