Хеширование корневых деревьев
Содержание
Задача
Хотим научиться сравнивать корневые деревья на изоморфизм (равенство с точностью до перенумерования вершин + корень одного дерева обязательно переходит в корень другого дерева).
Хеш вершины
Заметим, что поскольку мы не можем аппелировать к номерам вершин, единственная информация, которую мы можем оперировать $~-$ это структура нашего дерева. Положим тогда хешем вершины без детей какую-нибудь константу (например, 179), а для вершины с детьми положим в качестве хеша некоторую функцию от отсортированного (поскольку мы не знаем истинного порядка, в котором дети должны идти, нужно привести их к одинаковому виду) списка хешей детей. Хешом корневого дерева будем считать хеш корня. По построению, у изоморфных корневых деревьев хеши совпадают (доказательство индукцией по числу уровней в дереве автор оставляет читателю в качестве упражнения).
Полиномиальный хеш не подходит
Рассмотрим 2 дерева: $T_1 = \{ (1 2), (1 3), (1 4) \}$ и $T_2 = \{ (1 2), (1 3), (3 4), (3 5) \}$. Если мы посчитаем для них в качестве функции от детей взять полиномиальный хеш, то получим:
$$
h(T_1) = 179 + 179p + 179p^2 = 179 + p(179 + 179p) = h(T_2)
$$
Какую же хеш-функцию взять?
В качестве хорошей хеш-функции подойдёт, например
$$ h(v) = 42 + \sum_{u \in sorted\_by\_hash(child(v))} log(h(u)) $$
Для этой хешфункции может показаться, что можно не сортировать хеши детей, однако это не так, потому что при вычислении чисел с плавающей точкой у нас возникает погрешность, и чтобы это результат суммирования был одинаковый для изоморфных деревьев, суммировать детей надо тоже в одинаковом порядке.
Более complicated пример: $$ h(v) = \big[\sum_{u \in sorted\_by\_hash(child(v))} h(u)^2 + h(u) p^i + 42 \big] \mod 2^{64} $$
Асимптотика
Всё что нам нужно делать на каждом уровне $~-$ это сортировка вершин по размеру хеша и суммирование, так что итоговая сложность: $O(|V| log(|V|))$