Какова хорошая структура данных для построения классов эквивалентности на узлах дерева?

Question

Я ищу хорошую структуру данных для построения классов эквивалентности на узлах дерева. В идеальной структуре следующие операции должны быть быстрыми (O (1) / O (n) в зависимости от ситуации) и простыми (без абзацев загадочного кода):

• (A) пройтись по дереву от корня; на каждом узле -> дочерний переход перечисляет все эквивалентные версии дочернего узла
• (B) Объединить два класса эквивалентности
• (C) Создать новые узлы из списка существующих узлов (дочерних) и других данных
• (D) Найти любые узлы, структурно эквивалентные узлу (т.е. они имеют одинаковое количество дочерних элементов, соответствующие дочерние элементы принадлежат к одному и тому же классу эквивалентности, а их «другие данные» равны), так что новые (или вновь модифицированные) узлы может быть помещен в правильный класс эквивалентности (посредством слияния)

До сих пор я думал (некоторые из них могут быть использованы в комбинации):

• Parfait, где дочерние элементы являются ссылками на наборы узлов, а не на узлы. (A) быстро, (B) требует обхода дерева и обновления узлов, чтобы указать на объединенную коллекцию, (C) требует поиска коллекции, содержащей каждого дочернего элемента нового узла, (D) требует обхода дерева
• Ведение хэша узлов по их характеристикам. Это делает (D) намного быстрее, но (B) медленнее (поскольку хеш должен был бы быть обновлен, когда классы эквивалентности были объединены)
• Объединить узлы в круговой связанный список. (A) быстро, (B) было бы быстро, но для того факта, что «слияние» части кругового списка с самим собой фактически разделяет список (C), было бы быстро, (D) потребовало бы обхода дерева
• Как и выше, но с дополнительным указателем «вверх» в каждом узле, который можно использовать для поиска канонического члена кругового списка.

Мне не хватает сладкой альтернативы?

Answer 1

Похоже, у вас есть две формы эквивалентности. Простая эквивалентность (A), отслеживаемая как классы эквивалентности, которые поддерживаются в актуальном состоянии, и структурная эквивалентность (D), для которой иногда нужно создать один класс эквивалентности и затем выбросить его.

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

Answer 2

Я не думаю, что какая-то одна структура решит ваши проблемы, но вы могли бы взглянуть на Несвязанную структуру данных . В конце концов, класс эквивалентности - это то же самое, что и разбиение множества. Он должен уметь быстро выполнять некоторые из этих операций.

Answer 3

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

Причин, по которым было много, но причиной номер один была производительность, мои классы с числом детей до 100 или около того на самом деле работали бы лучше, манипулируя ими как массивом, чем через узлы дерева, в основном из-за аппаратной локализации и логики предварительной выборки процессора и конвейерная обработка процессора.

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