Построение максимального повторяющегося поддерева в дереве объектов

Question

Я пытаюсь решить проблему поиска максимального повторяющегося поддерева в дереве объектов.

По дереву объектов я имею в виду дерево, где каждый лист и узел имеют имя. Каждый лист имеет тип и значение этого типа, связанные с этим листом. Каждый узел имеет набор листьев/узлов в определенном порядке.

Учитывая дерево объектов, которое - мы знаем - имеет повторяющееся поддерево в нем.

Повторяя, я имею в виду 2 или более поддерева, которые похожи во всем (имена/типы/порядок подэлементов), но значения листьев. Никакие узлы/листья не могут быть разделены между поддеревами.

Проблема заключается в том, чтобы идентифицировать эти поддеревья максимальной высоты.

Я знаю, что исчерпывающий поиск может сделать трюк. Я скорее ищу более эффективный подход.

Answer 1

вы можете реализовать обход dfs, генерирующий хэш-значение для каждого узла. Сохраните эти значения с высотой узла в простом массиве. Кандидаты суб-деревьев являются повторяющимися значениями, просто проверьте, что кандидаты в порядке, так как два разных подэлемента могут давать одно и то же значение хэш-функции.
Предполагая, лавровый лист и внутренние узлы всех типов узла и стандартный доступ и обход функция:

procedure dfs_update(node : Node, hashmap : Hashmap) 
begin 
    if is_leaf(node) then 
    hashstring = concat("LEAF",'|',get_name_str(node),'|',get_type_str(node)) 
    else // node is an internal node 
    hashstring = concat("NODE",'|',get_name_str(node)) 
    for each child in get_children_sorted(node) 
     dfs_update(child,hashmap) 
     hashstring = concat(hashstring,'|',get_hash_string(hashmap,child)) 
    end for 
    end if 
    // only a ref to node is added to the hashmap, we could also add 
    // the node's height, hashstring, whatever could be useful and inapropriate 
    // to keep in the Node ds 
    add(hashmap, hash(hashstring),node) 
end 

Хитрая часть после dfs_update, мы должен получить список collinding узлов в hasmap по нисходящей высоте и проверить два на два они действительно повторяющийся.