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

Вот например есть дерево номер 1:

                1
                 |\
                 | \
                2  \
                /\   3
               /  \
              4   5

И дерево номер два:


                1
                 |\
                 | \
                2  \
                     3
                      |
                      4

У них наибольшим общим поддеревом будет дерево:


                1
                 |\
                 | \
                2  \
                     3

Подскажите кто знает.

насколько я понимаю, можно применить для этого алгоритм Дж. Эдмонда проверки графов на изоморфность.
описание есть в википедии
я, правда, не уверен, один ли и тот же алгоритм описан по первой ссылке и по второй. лучше посмотри оба источника.

Деревья подвешены заранее? Тогда можно решить за O(N log N) с помощью хеширования. С теоретической точки зрения метод не очень хорош, но на практике работает отлично. Если интересует, могу подробнее.

Интересно, если можно подробнее.

Научимся считать хеш от поддерева (т.е. от вершины вместе со всеми её сыновьями, их сыновьями, и т.д.). Причём хеш сделаем таким образом, чтобы он не зависел от порядка указания сыновей вершины, ну и естественно от их нумерации.

Итак, хеш. От единственной вершины, без сыновей, положим его равным 1. Пусть теперь у вершины есть сыновья. Тогда посчитаем (рекурсивно) хеш от каждого из этих сыновей, отсортируем их (тем самым мы устранили зависимость от порядка указания вершин в списке сыновей), и теперь хеш нашей вершины положим равным:
1 + P * son[1] + P^2 * son[2] + P^3 * son[3] + ...
где son[i] - хеш от i-го сына (в порядке сортировки), P - некоторое число, скажем, 97 (если степени вершин большие, больше этого числа, то имеет смысл поставить побольше).

Ну и собственно всё. Два поддерева совпадают, тогда совпадают и их хеши. Если хеши совпадают, то совпадают и поддеревья, _наверное_ (здесь проявляется ненадёжная природа хешей).


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


P.S. За точность не ручаюсь, вроде бы правильно. Такой метод один раз применял на практике, работал отлично (ни одной коллизии не поймал).