Алгоритм нахождения равных путей в двух деревьях

Question

Есть два дерева. Каждый узел дерева содержит значение, которое можно сравнить со значением из другого узла другого дерева. Если значения равны, то узлы равны.

Каждый узел может содержать от 0 до произвольного количества дочерних элементов.

Необходимо определить, можно ли построить равные пути в этих двух деревьях? Узлы на этих путях должны быть равными. Оба пути должны go сверху до узла, содержащего 0 детей. Количество узлов на путях, конечно, также должно быть одинаковым.

Пример:

  a           a        a
 /|\         /|\      / \
b c d       1 d z    x   y
| | |\      | |      |
e f g h     x g      s

Первые два дерева имеют равные пути «adg». У третьего дерева нет равных путей с первыми двумя деревьями.

Есть ли готовый алгоритм решения такой задачи? Если он есть, то как его назвать и где про него прочитать?

Answer 1

Как утверждали другие, вам нужно будет пересечь данные деревья, но с дополнительным условием, что пересекающиеся пути должны заканчиваться листом в обоих деревьях.

Вы можете сделать это, пройдя оба дерева в тандеме. Это может быть обход в глубину.

Я предполагаю, что значения узлов не обязательно должны быть уникальными. Чтобы избежать того, что дочерние элементы одного узла должны сравниваться со всеми дочерними элементами другого узла, элементы одного уровня могут быть отсортированы по их значению. Таким образом, дочерние элементы двух узлов можно сравнивать за линейное время. Из-за сортировки весь алгоритм выполняется в O (nlogn) . Если значения уникальны в одном дереве, то потомки могут быть хешированы по их значениям, что делает алгоритм O (n) . Но, как указано, я буду использовать go для варианта, в котором разрешены повторяющиеся значения:

Вот реализация в JavaScript:

class Node {
    constructor(value, ...children) {
        this.value = value;
        // sort the children by their value
        this.children = children.sort();
    }
    
    commonPaths(node) {
        if (this.value !== node.value) return [];
        if (this.children.length + node.children.length == 0) return [this.value];
        let result = [], i = 0, j = 0;
        while (i < this.children.length && j < node.children.length) {
            let a = this.children[i], b = node.children[j];
            for (let path of a.commonPaths(b)) result.push([this.value, ...path]);
            i += (a.value <= b.value); // boolean converts to 0 or 1
            j += (a.value >= b.value);
        }
        return result;
    }
    toString() { return this.value }
}

// Create the trees given in the question
let tree1 = new Node("a",
    new Node("b", new Node("e")),
    new Node("c", new Node("f")),
    new Node("d", new Node("g"), new Node("h"))
);

let tree2 = new Node("a",
    new Node("1", new Node("x")),
    new Node("d", new Node("g")),
    new Node("z")
);

let tree3 = new Node("a", 
    new Node("x", new Node("s")),
    new Node("y")
);

// Get common paths of pairs of these trees
console.log(tree1.commonPaths(tree2));
console.log(tree1.commonPaths(tree3));

Answer 2

Решение включает поиск дерева пересечений .

Чтобы выяснить дерево пересечений между двумя деревьями, нам нужно пересечь дочерние элементы каждого узла обоих деревьев.

Предположим, у вас есть деревья A и B с корнями a и b. Наша цель - построить дерево пересечений C.

Если a ≠ b, то C пусто.

В противном случае пусть root c из C быть a.

Потомки c будут children(a) ∩ children(b).

Теперь для каждого ребенка cᵢ из c, потомки cᵢ будут пересечение дочерних элементов cᵢ в A и B. Просто повторяйте это, пока не будет создано дерево пересечений.

Хороший способ представить дерево - это unordered_map<char, node> и использовать unordered_set для представления дочерних узлов узла и быстрого поиска общих дочерних элементов.

Вот рабочий пример:

#include <bits/stdc++.h>
using namespace std;

/*

  a           a   
 /|\         /|\   
b c d       1 d z  
| | |\      | |      
e f g h     x g     

*/


struct node{
    char value;
    unordered_set<char> children;
    node(){}
    node(char v){value = v; children.clear();}
    void add(char c){children.insert(c);}
};

unordered_map<char, node> A, B, C; //trees

void intersection_tree(char ra){  //method that generates C recursively
    
    auto ita = A.find(ra);
    auto itb = B.find(ra);
    
    if(ita == A.end() || itb == B.end()) return;
    
    node a = ita->second, b = itb->second;
    
    if(a.value == b.value){
        node n(a.value);
        
        vector<char> intersection;
        for (const char& elem: a.children) {
            if(b.children.find(elem) != b.children.end()){
                intersection.push_back(elem);
                n.add(elem);
            }
            C[a.value] = n;
        }
        for(int i = 0; i < intersection.size(); i++){
            intersection_tree(intersection[i]);
        }
    }
}

void dfs(char c, string s = ""){  //dfs to print common paths
    node n = C[c];
    if(n.children.size() == 0) cout<<(s + c)<<endl;
    for (const char& elem: n.children) {
        dfs(elem, s + n.value);        
    }
}


int main(){
    //fill A
    node Aa('a'); Aa.add('b'); Aa.add('c'); Aa.add('d');
    node Ab('b'); Ab.add('e');
    node Ac('c'); Ac.add('f');
    node Ad('d'); Ad.add('g'); Ad.add('h'); 
    node Ae('e'); 
    node Af('f'); 
    node Ag('g'); 
    node Ah('h');
    A['a'] = Aa; A['b'] = Ab; A['c'] = Ac; A['d'] = Ad; A['e'] = Ae; A['f'] = Af; A['g'] = Ag; A['h'] = Ah;
   
    //fill B 
    node Ba('a'); Ba.add('1'); Ba.add('d'); Ba.add('z');
    node B1('1'); B1.add('x');
    node Bd('d'); Bd.add('g');
    node Bz('1');
    node Bx('x');
    node Bg('g');
    B['a'] = Ba; B['1'] = B1; B['d'] = Bd; B['z'] = Bz; B['x'] = Bx; B['g'] = Bg; 
    
    intersection_tree('a');   //generate C
    
    dfs('a');                 //print common paths

    return 0;
}

вывод: adg

Сложность этого метода - O (n).